C++ STL容器适配器：从零实现stack与queue

1. 为什么需要自己实现STL容器

作为C++开发者，STL（Standard Template Library）是我们日常工作中最常用的工具之一。其中stack和queue作为容器适配器，虽然使用简单，但理解其底层实现原理对于深入掌握STL至关重要。我在实际项目开发中发现，很多开发者只是停留在"会使用"的层面，当遇到性能瓶颈或需要定制功能时往往束手无策。

自己动手实现STL容器有以下几个核心价值：

• 深入理解容器底层数据结构和算法
• 掌握模板编程和迭代器设计模式
• 提升内存管理和异常安全编程能力
• 为定制化开发特殊容器打下基础

2. 容器适配器设计原理

2.1 什么是容器适配器

容器适配器(Container Adaptor)是STL中一类特殊的容器，它们基于现有容器进行封装，提供特定的接口。stack和queue就是典型的容器适配器，它们默认使用deque作为底层容器，但也可以指定其他序列容器如vector或list。

关键点：适配器模式的核心是通过组合已有功能来实现新接口，而不是从头实现

2.2 stack的LIFO特性实现

栈(Stack)遵循后进先出(LIFO)原则，其核心操作包括：

• push：元素入栈
• pop：栈顶元素出栈
• top：访问栈顶元素
• empty：判断栈是否为空
• size：获取栈中元素数量

这些操作都可以通过底层容器的相应操作实现。例如push对应底层容器的push_back，pop对应pop_back。

2.3 queue的FIFO特性实现

队列(Queue)遵循先进先出(FIFO)原则，其核心操作包括：

• push：元素入队
• pop：队首元素出队
• front：访问队首元素
• back：访问队尾元素
• empty：判断队列是否为空
• size：获取队列中元素数量

与stack不同，queue需要同时操作序列的两端，push对应push_back，pop对应pop_front。

3. 从零实现stack

3.1 类模板定义

我们先定义stack的类模板框架：

cpp复制template <typename T, typename Container = std::deque<T>>
class Stack {
public:
    // 类型别名
    using value_type = typename Container::value_type;
    using reference = typename Container::reference;
    using const_reference = typename Container::const_reference;
    using size_type = typename Container::size_type;
    
    // 构造函数
    Stack() = default;
    explicit Stack(const Container& cont) : c(cont) {}
    explicit Stack(Container&& cont) : c(std::move(cont)) {}
    
    // 核心接口实现
    reference top() { return c.back(); }
    const_reference top() const { return c.back(); }
    
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    
    void push(const value_type& value) { c.push_back(value); }
    void push(value_type&& value) { c.push_back(std::move(value)); }
    
    template <typename... Args>
    void emplace(Args&&... args) { c.emplace_back(std::forward<Args>(args)...); }
    
    void pop() { c.pop_back(); }
    
    void swap(Stack& other) noexcept { std::swap(c, other.c); }
    
private:
    Container c;
};

3.2 关键实现细节

1. 模板参数设计：

   • T：元素类型
   • Container：底层容器类型，默认为deque

2. 完美转发应用：

   • 使用std::forward实现参数的完美转发
   • 支持移动语义提高性能

3. 异常安全保证：

   • 所有操作都依赖底层容器的异常安全保证
   • swap操作保证不抛出异常

4. 类型萃取：

   • 使用typename从容器类型中提取相关类型
   • 确保类型系统的正确性

3.3 测试用例

编写测试代码验证我们的实现：

cpp复制void testStack() {
    Stack<int> s;
    
    // 测试push和top
    s.push(1);
    assert(s.top() == 1);
    
    s.push(2);
    assert(s.top() == 2);
    
    // 测试size
    assert(s.size() == 2);
    
    // 测试pop
    s.pop();
    assert(s.top() == 1);
    
    // 测试empty
    assert(!s.empty());
    s.pop();
    assert(s.empty());
    
    // 测试emplace
    s.emplace(3);
    assert(s.top() == 3);
    
    // 测试移动语义
    Stack<std::string> strStack;
    std::string str = "hello";
    strStack.push(std::move(str));
    assert(str.empty());  // str已被移动
    assert(strStack.top() == "hello");
}

4. 从零实现queue

4.1 类模板定义

queue的实现与stack类似，但操作两端：

cpp复制template <typename T, typename Container = std::deque<T>>
class Queue {
public:
    // 类型别名
    using value_type = typename Container::value_type;
    using reference = typename Container::reference;
    using const_reference = typename Container::const_reference;
    using size_type = typename Container::size_type;
    
    // 构造函数
    Queue() = default;
    explicit Queue(const Container& cont) : c(cont) {}
    explicit Queue(Container&& cont) : c(std::move(cont)) {}
    
    // 核心接口实现
    reference front() { return c.front(); }
    const_reference front() const { return c.front(); }
    
    reference back() { return c.back(); }
    const_reference back() const { return c.back(); }
    
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    
    void push(const value_type& value) { c.push_back(value); }
    void push(value_type&& value) { c.push_back(st