c++ - 如何使堆栈动态增长？

Question

这是我的 Stack 类的一个小程序:

 #include <iostream>

using namespace std;

#include <iomanip>

template <typename T>
class Stack
{
private:
    T *stackPtr; 
    int size; 
    T top; 
public:
    Stack(int = 10);
    ~Stack(); 
    bool push(const T  );
    bool pop(); 
    void printStack();
};

int main()
{
    Stack <int> myStack(5);


    cout << "Push 5 elements to stack: ";
    int ct = 0;
    while (ct++ != 5)
    {
        int temp;
        cin >> temp;
        myStack.push(temp);
    }

    myStack.printStack(); 

    cout << "\nErasing two elements:\n";

    myStack.pop(); 
    myStack.pop(); 
    myStack.printStack(); 

    return 0;
}


template <typename T>
Stack<T>::Stack(int s)
{
    size = s > 0 ? s: 10;   
    stackPtr = new T[size]; 
    top = -1; 
}


template <typename T>
Stack<T>::~Stack()
{
    delete [] stackPtr; 
}


template <typename T>
bool Stack<T>::push(const T value)
{
    if (top == size - 1)
        return false; 

    top++;
    stackPtr[top] = value; 

    return true; 
}


template <typename T>
bool Stack<T>::pop()
{
    if (top == - 1)
        return false; 

    stackPtr[top] = 0; 
    top--;

    return true; 
}


template <typename T>
void Stack<T>::printStack()
{
    for (int ix = size -1; ix >= 0; ix--)
        cout << "|" << setw(4) << stackPtr[ix] << endl;
}

所以，为了使用这样的堆栈，我应该在使用前在构造函数中声明它的大小，就像Stack<int> newstack(10)一样。 ，如果我需要 10 个元素。那么，如果我不知道堆栈的最终大小怎么办？如何让它动态增长，仅仅通过向它推送元素？我一直在寻找解决方案，但我的所有想法仍然是计算元素数量，然后声明一个堆栈以适应元素数量。

Answer 1

首先，您知道 C++ 有 std::stack内置，不是吗？对于其余的答案，我假设您有某种理由不使用它(也许这是一种学习练习)。

---

实现您想要的目标的一种非常天真的方法是:

1. 每次添加元素时，使用 new[] 分配一个 size + 1 的新数组。
2. 将旧数组的所有元素和新元素复制到新数组。
3. delete[] 旧数组。
4. 使stackPtr指向新数组。

撇开此解决方案的所有性能和异常安全缺陷不谈，如果您的元素类型 T 没有默认构造函数，它怎么可能工作？它甚至不会编译。事实上，您的类(class)失败了，因为它针对以下 T:

struct CannotUseInThisStack
{
    CannotUseInThisStack(int) {} // no default constructor
};

Stack<CannotUseInThisStack> s; // error

真正的解决方案是:不要使用new[] 和delete[]。根据 std::vector(或根据 std::deque，这正是 std::stack 的作用)实现您的堆栈默认情况下!)。 std::vector 以更好的方式支持开箱即用的动态增长，无需在每次添加元素时连续重新分配，也无需能够默认构造 T.

当然，这理所当然地引出了一个问题，即 std::vector 是如何做到这一切的。

答案是 std::vector，或者说它的标准分配器 std::allocator , 不是根据 new[] 和 delete[] 而是根据新的放置来实现的。内存分配和元素构造是分开的。参见 std::allocator:allocate .这解决了缺少默认构造函数的问题。首先分配原始内存，然后使用复制构造函数在该原始内存位置构造新元素(在 C++11 中，您还可以使用完美转发来就地构造 T，但那是有点跑题了)。

使用 placement new 还允许 std::vector 的容量呈指数级增长。每次添加元素时，容器都不需要重新分配内存；它提前为更多元素分配原始内存(类似于 Christophe 在他的回答中所做的)。仅当超过当前容量时才会重新分配。

有了 new[] 和 delete[]，这样一个复杂的机制是不可能的。

---

通常，如果您想了解严肃的容器设计，请查看您的编译器如何实现所有 C++ 标准容器。