泛型堆栈的简单实现

Question

我对C++编程相当陌生。为了帮助我，我一直在为实践写我自己的数据结构。我希望这是一个专业人士写的，并得到诚实的反馈意见。我已经有点担心了。

1. 我是否正确地管理了内存？我不相信我有任何泄密。我在使用指针时得到的很多建议是使用智能指针，但是当类封装所有指针时，原始指针就可以了，对吗？
2. 我很不高兴，我的<<操作符重载不得不在类内调用peekAll。我觉得我走错路了。除此之外，我还应该让其他运营商超载吗？我不觉得算术运算符有什么意义。

#include <ostream>

template <typename T>
class BBStack {
public:
BBStack(T type) {
    head = new Node(type);
}

virtual ~ BBStack() {
    Node* temp = head;
    while (head != nullptr) {
        temp = head->next;
        delete head;
        head = temp;
    }
    delete temp;
}

void push(T type) {
    Node *newNode = new Node(type, head);
    head = newNode;
}

T peek() const {
    return head->data;
}

T pop() {
    if (head == nullptr) {
        std::cout<<"Error stack is empty"<<std::endl;
        return NULL;
    } else {
        Node *temp = head;
        T result = temp->data;
        head = head->next;
        delete temp;
        return result;
    }
}

std::ostream& peekAll(std::ostream& out) const {
    if (head == nullptr) return out << "Stack is empty";
    Node* temp = head;

    while (temp != nullptr) {
        out << temp->data << " ";
        temp = temp->next;
    }

    delete temp;
    return out;
}

private:
    struct Node {
        Node(T type, Node* _next = nullptr) : data(type), next(_next) {}
        Node(Node* node) : data (node->data), next (node->next) {}

        T data;
        Node* next;
    };
    Node* head;

};

template <typename T>
std::ostream& operator<< (std::ostream& out, const BBStack<T>& stack) {
    return stack.peekAll(out);
}

Answer 1

所有权

是的，如果不转移所有权(是删除它们的类责任)，那么原始指针是可以的。

Pop函数

此外，我也不确定这是否会编译除指针和类型之外的任何数据，因为您返回NULL。(同样更好的做法是一致使用nullptr )。

 T pop() {
    if (head == nullptr) {
        std::cout<<"Error stack is empty"<<std::endl;
        return NULL;
    } else {
        Node *temp = head;
        T result = temp->data;
        head = head->next;
        delete temp;
        return result;
    }
}

海事组织最好是抛出一个底流异常，因为客户有责任检查之前不是空的。还要避免返回数据，因为我们将抛出一个异常(有关这篇文章http://ptgmedia.pearsoncmg.com/images/020163371x/supplements/Exception_处理_Article.html的更多信息)

 void pop() {
    if (head == nullptr) 
        throw std::underflow_error("underflow");

    Node *temp = head;
    head = head->next;
    delete temp;   
 }

因此，客户必须在pop之前调用peek才能获得相同的效果。

参数：

在大多数像这样的参数(T类型)中，您应该将其更改为(const & type)，以避免复制。更好的做法是为这样的rvalue引用提供重载(T&&)

peekAll函数

这个功能接缝有点奇怪。你为什么要删除临时工？它接缝在while循环之后的temp应该始终是nullptr。你不是只是在溪流上写堆栈吗。我只是省略了这个函数，并将其移动到<<操作符重载。

此外，您还应该实现一个空函数。

Answer 2

在专业环境中，建议是：“废弃整个代码并使用std::stack”。

但是，假设标准库中不存在std::stack<T>，或者假设您想要编写其他一些尚未发明的类似容器的实体。专业的建议是：“尽量利用现有的代码”。例如，根据现有容器实现std::stack<T>，如std::list<T>、std::vector<T>或std::deque<T>。

这将自动从您的考虑中删除所有内存管理问题。在专业代码中，除非仔细记录为什么这是绝对必要的，否则我不会期望看到原始的new或delete，而是看到unique_ptr和make_unique，或者像std::vector或std::string这样的内存管理容器。

顺便说一句，这也是标准库实现std::stack<T>的方式，因为它是一个容器适配器，而不是容器。精确的类模板是：

template<
    class T,
    class Container = std::deque<T>
> class stack;

根据底层容器的emplace()、push_back()和pop_back()实现堆栈成员函数pop()、push()和emplace_back()是一个很好的练习。它仍然不是完全琐碎的，因为你必须小心完美的转发和移动语义。链接的文档应该为您提供足够的提示来说明这一点。

请注意，std::stack没有提供operator<<，也没有提供迭代器来查看其元素。但是，它确实有一个受保护的成员c，它提供对底层容器的访问。然后，您可以编写一个适配器，该适配器使用容器迭代器显示底层元素：

#include <iostream>
#include <iterator>
#include <stack>
#include <vector>

template<class Adaptor>
struct container_view
:
    public Adaptor
{
    container_view() = default;
    using Adaptor::Adaptor;
    auto begin() const { return this->c.begin(); }
    auto end() const { return this->c.end(); }
};

int main()
{
    std::vector<int> v = { 1, 2, 3, 4 };
    container_view<std::stack<int, std::vector<int>>> const c(v);
    std::copy(begin(c), end(c), std::ostream_iterator<int>(std::cout, ","));
}

实例化。

注意，他的适配器也适用于另外两个标准库容器适配器std::priority_queue和std::queue。