前言

栈（stack）是后进先出（last in, first out, LIFO）的线性结构，只允许在一端插入和删除。C++ 标准库已经提供了std::stack，但它是容器适配器而不是独立容器：默认用std::deque<T>作为底层存储，只暴露push、pop、top、empty、size五个操作，不提供迭代器。自己动手写一个模板栈，是理解模板、动态内存管理、异常安全和拷贝/移动语义的经典练习。

写这个练习时有两个常见误区。第一，把栈写成"只能存int"的普通类，然后再复制粘贴改成double版本，完全没有体会到模板的价值。第二，只实现push/pop就结束，忽略了拷贝构造、赋值、析构——一旦类里出现裸指针，默认生成的拷贝操作只会复制指针，导致两个对象释放同一块内存，这是典型的重复释放（double free），属于未定义行为。

本文实现一个基于动态数组的Stack<T>：支持push、pop、top、empty、size，正确处理拷贝、移动和异常安全，并说明它与std::stack的差异。代码以 C++17 为基准。需要提前说明的是，为了突出主线，这个实现使用new T[]分配数组，因此要求T可默认构造；生产级容器会用分配器加 placement new 分离"分配内存"和"构造对象"两件事，std::vector就是这么做的。

一、接口设计与复杂度

一个最小可用的栈需要以下操作：

std::stack的pop()返回void，这是有意为之：如果pop同时返回值，在元素拷贝构造抛出异常时，元素已经被弹出，调用方却拿不到值，无法提供强异常保证。需要"取出并删除"时，标准做法是先top()拷贝或移动，再pop()：

// 适用于 C++17
T value = std::move(s.top());
s.pop();

自己实现时也应保持这个约定，不要设计成T pop()。

底层存储选择动态数组的好处是内存连续、常数因子小、实现直观。缺点是扩容时要重新分配并搬移全部元素，而且push可能导致已有的top()引用失效。另一个常见选择是链表，扩容没有搬移成本，但每个节点都要额外存储指针，缓存局部性较差。标准库的std::stack默认选std::deque，是在两端操作和内存碎片之间做的折中。

二、核心实现：容量管理与强异常安全

动态数组栈的内部状态由三部分组成：指向数组的指针、当前元素个数、当前容量。压入元素前先确认容量足够，不够就按倍数扩容。

扩容的实现有几个细节决定成败。第一，新容量必须能容纳"当前元素数加一"，不能简单地把容量翻倍后就假定够用；如果一次要加入很多元素（例如批量构造），循环倍增直到满足需求更稳妥。第二，扩容时搬移元素要用std::move_if_noexcept：如果元素的移动构造可能抛异常且它可拷贝，就退回拷贝，这样搬移过程中抛异常时原数组仍然完好，可以实现强异常保证；如果移动构造是noexcept，则直接移动，效率更好。第三，新数组的所有权必须先交给一个 RAII 对象，等搬移成功后再替换旧数组，否则中途抛异常会泄漏。

下面先看扩容函数的核心逻辑：

// 适用于 C++17
void ensureCapacity(std::size_t needed) {
if (needed <= capacity_) {
return;
}
std::size_t newCapacity = capacity_ == 0 ? 4 : capacity_ * 2;
while (newCapacity < needed) {
newCapacity *= 2;
}

std::unique_ptr<T[]> newData(new T[newCapacity]);
std::move_if_noexcept(data_.get(), data_.get() + size_, newData.get());

data_ = std::move(newData);
capacity_ = newCapacity;
}

new T[newCapacity]会默认构造全部newCapacity个元素，这是本实现要求T可默认构造的原因，也是它与工业级容器的主要差距。std::unique_ptr<T[]>负责在异常路径上释放新数组，data_ = std::move(newData)之后旧数组由unique_ptr的移动赋值自动delete[]。

容量增长采用倍增。标准并不规定std::vector的扩容因子，各实现可能不同；这里选 2 倍只是为了实现简单。倍增策略保证n次连续push的总搬移次数与n成正比，因此单次push是均摊 O(1)。注意"均摊"不等于"每次都快"：个别一次push会触发 O(n) 的搬移。

三、拷贝、移动与析构：规则五

类里持有裸指针（或unique_ptr数组成员）时，编译器默认生成的拷贝构造和拷贝赋值会逐成员复制，导致两个栈指向同一块数组。析构时两次delete[]，就是未定义行为。因此必须自己定义这些特殊成员函数，或者用能正确表达所有权的成员让编译器生成。

本实现选择std::unique_ptr<T[]>作为存储，它本身不可拷贝、可移动。这样：

• 
  
• 析构函数用= default，unique_ptr自动释放数组。
• 
  
• 移动构造和移动赋值需要手写，因为默认版本只搬移指针，不会把源对象的size_、capacity_清零。虽然标准允许"有效但未指定"的移动后状态，但让size()返回一个非零值而data_为空，会让后续误用直接崩溃；清零更安全。
• 
  
• 拷贝构造手写，先按源大小分配，再std::copy。分配结果由unique_ptr成员持有，拷贝过程中抛异常也不会泄漏。
• 
  
• 拷贝赋值采用拷贝并交换（copy-and-swap），天然处理自赋值并提供强异常保证。
• 
  

// 适用于 C++17
Stack(const Stack& other) {
if (other.size_ != 0) {
data_ = std::make_unique<T[]>(other.size_);
std::copy(other.data_.get(), other.data_.get() + other.size_, data_.get());
size_ = other.size_;
capacity_ = other.size_;
}
}

Stack(Stack&& other) noexcept
: data_(std::move(other.data_)),
size_(other.size_),
capacity_(other.capacity_) {
other.size_ = 0;
other.capacity_ = 0;
}

Stack& operator=(const Stack& other) {
if (this != &other) {
Stack tmp(other);
swap(tmp);
}
return *this;
}

Stack& operator=(Stack&& other) noexcept {
if (this != &other) {
data_ = std::move(other.data_);
size_ = other.size_;
capacity_ = other.capacity_;
other.size_ = 0;
other.capacity_ = 0;
}
return *this;
}

~Stack() = default;

移动构造标记noexcept很重要：std::vector<Stack<T>>在扩容时会优先使用noexcept的移动构造，否则可能退回拷贝。unique_ptr的移动是noexcept的，std::size_t的复制也不会抛，因此这里的noexcept名副其实。

四、完整实现与使用示例

把上面的片段拼起来，得到完整的类：

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <memory>
#include <stdexcept>
#include <utility>

template <typename T>
class Stack {
public:
Stack() = default;

Stack(const Stack& other) {
if (other.size_ != 0) {
data_ = std::make_unique<T[]>(other.size_);
std::copy(other.data_.get(),
other.data_.get() + other.size_,
data_.get());
size_ = other.size_;
capacity_ = other.size_;
}
}

Stack(Stack&& other) noexcept
: data_(std::move(other.data_)),
size_(other.size_),
capacity_(other.capacity_) {
other.size_ = 0;
other.capacity_ = 0;
}

Stack& operator=(const Stack& other) {
if (this != &other) {
Stack tmp(other);
swap(tmp);
}
return *this;
}

Stack& operator=(Stack&& other) noexcept {
if (this != &other) {
data_ = std::move(other.data_);
size_ = other.size_;
capacity_ = other.capacity_;
other.size_ = 0;
other.capacity_ = 0;
}
return *this;
}

~Stack() = default;

void push(const T& value) {
ensureCapacity(size_ + 1);
data_[size_] = value;
++size_;
}

void push(T&& value) {
ensureCapacity(size_ + 1);
data_[size_] = std::move(value);
++size_;
}

void pop() {
if (empty()) {
throw std::underflow_error("pop on empty stack");
}
--size_;
}

T& top() {
checkNotEmpty();
return data_[size_ - 1];
}

const T& top() const {
checkNotEmpty();
return data_[size_ - 1];
}

bool empty() const noexcept { return size_ == 0; }
std::size_t size() const noexcept { return size_; }

void swap(Stack& other) noexcept {
data_.swap(other.data_);
std::swap(size_, other.size_);
std::swap(capacity_, other.capacity_);
}

private:
void checkNotEmpty() const {
if (empty()) {
throw std::underflow_error("access on empty stack");
}
}

void ensureCapacity(std::size_t needed) {
if (needed <= capacity_) {
return;
}
std::size_t newCapacity = capacity_ == 0 ? 4 : capacity_ * 2;
while (newCapacity < needed) {
newCapacity *= 2;
}

std::unique_ptr<T[]> newData(new T[newCapacity]);
std::move_if_noexcept(data_.get(), data_.get() + size_, newData.get());

data_ = std::move(newData);
capacity_ = newCapacity;
}

std::unique_ptr<T[]> data_;
std::size_t size_ = 0;
std::size_t capacity_ = 0;
};

使用方式：

// 适用于 C++17
#include <iostream>
#include <string>

int main() {
Stack<std::string> stack;
stack.push("first");
stack.push("second");
stack.push("third");

std::cout << stack.top() << ' ' << stack.size() << '\n'; // third 3

stack.pop();
std::cout << stack.top() << '\n'; // second

Stack<std::string> copy = stack;
copy.push("fourth");

std::cout << stack.size() << ' ' << copy.size() << '\n'; // 1 2

Stack<std::string> moved = std::move(copy);
std::cout << moved.size() << ' ' << copy.size() << '\n'; // 2 0
return 0;
}

按标准语义，输出依次为third 3、second、1 2、2 0。最后一行体现了移动构造后源对象被清零：copy.size()返回 0，copy处于有效但未指定的状态，只应销毁或重新赋值，不要继续读取它的元素。

top()返回引用，这带来一个必须注意的生命周期问题：后续的push可能触发扩容，数组被重新分配，之前保存的引用立即悬垂。

// 适用于 C++17
const std::string& ref = stack.top();
stack.push("another"); // 可能扩容
// 此后使用 ref 可能是悬垂引用

需要跨push保存值时，请按值拷贝一份，或者改用能提供稳定引用的容器（如std::deque）。

五、与 std::stack 的对比

如果只是需要一个栈，直接用std::stack更省事，也更可靠。自己实现的价值在于理解容器如何管理内存、如何处理拷贝与移动，以及"均摊 O(1)"背后的代价。若确实需要自定义行为，通常更好的做法是给std::stack指定底层容器，例如std::stack<T, std::vector<T>>，而不是从头造一个。

常见坑点

❌ 只写push/pop，让编译器生成拷贝构造，两个栈共享同一块数组。 ✅ 用unique_ptr<T[]>管理存储，并手写拷贝构造、拷贝赋值、移动操作和析构。

❌ 在类里new[]，析构里写delete。 ✅new[]必须配delete[]；用unique_ptr<T[]>可以避免手工配对。

❌ 拷贝赋值不检查自赋值，先释放自己的数组再读源对象，读到的已是释放后的内存。 ✅ 用拷贝并交换，或先判断this != &other。

❌ 扩容时先用delete[]释放旧数组，再逐元素搬移。 ✅ 先分配新数组、搬移成功后再替换并释放旧数组，保证异常安全。

❌pop()设计成返回T，元素拷贝构造抛出时数据已经丢失。 ✅ 保持pop()返回void，需要值时先top()再pop()。

❌ 保存top()返回的引用后继续push，扩容导致引用悬垂。 ✅ 需要跨操作保存就按值复制，或换用引用稳定的容器。

❌ 认为扩容因子一定是 2 倍，或认为push每次都是 O(1)。 ✅ 扩容因子由实现决定；push是均摊 O(1)，个别次数是 O(n)。

❌ 移动之后继续读取源对象的元素。 ✅ 被移动对象处于有效但未指定状态，只能销毁或重新赋值。

总结

写模板容器真正的难点不是模板语法，而是所有权与异常安全：谁分配、谁释放、抛异常时谁兜底。把这三个问题回答清楚，代码自然就稳了。