c++ - 模板类和 vector

Question

实现一个名为 MyStack 的模板类，它使用 STL 类 vector 创建一个堆栈。 MyStack 类将有两个函数——push() 和 pop()。由于 MyStack 是一个模板类，因此必须以可用于创建任何类型数据(内置和自定义类型)的堆栈的方式编写它。当堆栈的一个元素被弹出时，它应该从 vector 中删除，这样弹出的数据就不再使用内存。在 main() 中，创建多个这样的不同数据类型的堆栈，压入一些示例数据，并在从相应堆栈中弹出数据时显示数据。

Answer 1

获得 std::vector 的唯一方法收缩就是swap它有一个较小的 vector 。因此，在弹出每个对象时释放其内存需要为每个 pop 复制(几乎)整个 vector 。 , 使其成为 O(n)操作。

所以，我建议你不要那样做，或者如果这是家庭作业，要么清楚地说明为什么实现如此糟糕，要么注意 vector::pop_back实际上并没有释放任何东西。

顺便说一下，std::stack在 <stack>工具 O(1) push()和 pop()使用 std::vector处理分配。