1. 容器适配器基础概念

在C++标准库中，容器适配器（Container Adapters）是一种特殊类型的容器，它们基于现有的序列容器（如vector、deque或list）进行封装，提供特定的接口和行为。与普通容器不同，适配器不直接管理内存，而是通过调整底层容器的接口来实现特定的数据结构行为。

容器适配器主要有三种：

• stack（栈）
• queue（队列）
• priority_queue（优先队列）

这些适配器之所以被称为"适配器"，是因为它们"适配"了现有容器的接口，使其表现出不同的行为模式。例如，stack适配器限制了底层容器的访问方式，使其遵循后进先出（LIFO）原则。

2. 标准容器适配器详解

2.1 stack适配器

stack是一种后进先出（LIFO）的数据结构，它提供以下核心操作：

• push：将元素压入栈顶
• pop：移除栈顶元素
• top：访问栈顶元素
• empty：检查栈是否为空
• size：获取栈中元素数量

stack默认使用deque作为底层容器，但也可以指定其他容器：

#include <stack>
#include <vector>

std::stack<int> s1; // 默认使用deque
std::stack<int, std::vector<int>> s2; // 使用vector作为底层容器

选择底层容器时的考虑因素：

• 如果频繁进行push/pop操作，deque通常是最佳选择
• 如果需要连续内存（如与C API交互），vector可能更合适
• list在大多数stack场景中性能较差，不推荐使用

2.2 queue适配器

queue是一种先进先出（FIFO）的数据结构，提供以下操作：

• push：在队尾添加元素
• pop：移除队首元素
• front：访问队首元素
• back：访问队尾元素
• empty/size：同stack

queue默认也使用deque作为底层容器：

#include <queue>

std::queue<int> q1; // 默认deque
std::queue<int, std::list<int>> q2; // 使用list

底层容器选择建议：

• deque是queue的最佳默认选择
• list在某些特殊场景下可能有优势（如频繁在中间插入）
• vector不适合作为queue底层容器，因为pop_front效率低

2.3 priority_queue适配器

priority_queue是一种按优先级排序的队列，总是返回优先级最高的元素。它基于堆数据结构实现，提供：

• push：插入元素
• pop：移除顶部元素（最高优先级）
• top：访问顶部元素
• empty/size：同前

priority_queue默认使用vector作为底层容器：

#include <queue>

std::priority_queue<int> pq1; // 默认vector
std::priority_queue<int, std::deque<int>> pq2; // 使用deque

底层容器选择考虑：

• vector通常是最佳选择，因为堆操作需要随机访问
• deque也可以使用，但性能可能略差
• 必须提供随机访问迭代器，因此list不能用作priority_queue的底层容器

3. 容器适配器的底层实现原理

3.1 适配器模式的应用

容器适配器是适配器设计模式的典型应用。它们不自己实现数据存储，而是通过组合方式使用现有容器，并限制其接口：

template<typename T, typename Container = std::deque<T>>
class stack {
protected:
    Container c; // 底层容器
public:
    void push(const T& value) { c.push_back(value); }
    void pop() { c.pop_back(); }
    // 其他接口...
};

3.2 不同适配器的内部机制

• stack：通常使用push_back/pop_back实现push/pop
• queue：使用push_back/pop_front实现push/pop
• priority_queue：使用make_heap/push_heap/pop_heap算法维护堆结构

3.3 性能特点对比

操作	stack (deque)	queue (deque)	priority_queue (vector)
push	O(1)	O(1)	O(log n)
pop	O(1)	O(1)	O(log n)
top/front	O(1)	O(1)	O(1)
内存局部性	中等	中等	高

4. 容器适配器的高级用法

4.1 自定义比较函数

priority_queue允许自定义比较函数来改变元素优先级：

auto cmp = [](int a, int b) { return a > b; }; // 小顶堆
std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);

4.2 适配器与算法协同工作

虽然适配器本身不提供迭代器，但可以通过底层容器使用算法：

std::stack<int> s;
// 填充stack...

// 通过底层容器使用算法
auto& c = s.*(&std::stack<int>::c); // 获取底层容器(C++17)
std::sort(c.begin(), c.end()); // 排序底层容器

4.3 实现特殊数据结构

通过组合适配器可以实现更复杂的数据结构，如：

• 用两个stack实现queue
• 用priority_queue实现Dijkstra算法
• 用stack实现表达式求值

5. 容器适配器的常见问题与解决方案

5.1 底层容器访问问题

问题：标准方法无法直接访问适配器的底层容器 解决方案：

• C++11前：使用继承方式（不推荐）
• C++17后：使用 std::stack<int>::c 成员（实现定义）
• 通用方案：封装自定义适配器类

5.2 迭代器失效问题

问题：priority_queue的堆操作可能导致迭代器失效 解决方案：

• 避免保存底层容器的迭代器
• 如需遍历，先复制到临时容器

5.3 性能调优技巧

1. 对于大量微小元素的stack，考虑使用自定义分配器
2. 频繁push/pop的queue，deque比vector更合适
3. priority_queue的reserve可以避免重新分配

6. 自定义容器适配器实现

6.1 基本实现框架

自定义stack适配器示例：

template<typename T, typename Container = std::deque<T>>
class MyStack {
protected:
    Container c;
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;
    
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    reference top() { return c.back(); }
    const_reference top() const { return c.back(); }
    void push(const value_type& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
};

6.2 线程安全适配器

通过互斥锁实现线程安全stack：

#include <mutex>

template<typename T>
class ThreadSafeStack {
private:
    std::stack<T> s;
    mutable std::mutex m;
public:
    void push(T value) {
        std::lock_guard<std::mutex> lock(m);
        s.push(std::move(value));
    }
    
    bool try_pop(T& value) {
        std::lock_guard<std::mutex> lock(m);
        if(s.empty()) return false;
        value = std::move(s.top());
        s.pop();
        return true;
    }
    // 其他接口...
};

7. 容器适配器的实际应用案例

7.1 使用stack实现括号匹配

bool isBalanced(const std::string& s) {
    std::stack<char> st;
    for(char c : s) {
        if(c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if(st.empty()) return false;
            char top = st.top();
            if((c == ')' && top != '(') ||
               (c == ']' && top != '[') ||
               (c == '}' && top != '{')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

7.2 使用queue实现BFS

void bfs(const Graph& g, Node start) {
    std::queue<Node> q;
    std::unordered_set<Node> visited;
    
    q.push(start);
    visited.insert(start);
    
    while(!q.empty()) {
        Node current = q.front();
        q.pop();
        
        // 处理当前节点
        
        for(Node neighbor : g.neighbors(current)) {
            if(visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

7.3 使用priority_queue实现Top K问题

std::vector<int> topKFrequent(const std::vector<int>& nums, int k) {
    std::unordered_map<int, int> freq;
    for(int num : nums) freq[num]++;
    
    using Pair = std::pair<int, int>;
    auto cmp = [](const Pair& a, const Pair& b) { return a.second > b.second; };
    std::priority_queue<Pair, std::vector<Pair>, decltype(cmp)> pq(cmp);
    
    for(const auto& p : freq) {
        pq.push(p);
        if(pq.size() > k) pq.pop();
    }
    
    std::vector<int> result;
    while(!pq.empty()) {
        result.push_back(pq.top().first);
        pq.pop();
    }
    return result;
}

8. 容器适配器的性能优化

8.1 内存分配优化

对于性能关键的stack，可以预分配内存：

std::stack<int, std::vector<int>> s;
s.c.reserve(1000); // 预分配内存(C++17)

8.2 移动语义支持

现代C++适配器支持移动操作：

std::stack<std::string> s1;
std::string str = "hello";
s1.push(std::move(str)); // 移动而非复制

8.3 批量操作优化

虽然适配器不直接支持批量操作，但可以通过底层容器实现：

std::stack<int> s;
// 批量插入
auto& c = s.*(&std::stack<int>::c);
c.insert(c.end(), {1, 2, 3, 4, 5});

9. C++标准演进对容器适配器的影响

9.1 C++11新增特性

• 移动语义支持
• emplace操作（直接构造元素）

std::stack<std::pair<int, std::string>> s;
s.emplace(1, "hello"); // 直接构造元素

9.2 C++17新增特性

• 结构化绑定支持（通过底层容器）
• 更规范的底层容器访问方式

9.3 C++20新增特性

• 概念约束（明确容器要求）
• 三路比较运算符支持

10. 容器适配器的最佳实践

1. 默认选择 ：

   • stack/queue：默认使用deque
   • priority_queue：默认使用vector

2. 接口使用 ：

   • 总是检查empty()后再调用top()/front()
   • 优先使用emplace而非push（对于非平凡类型）

3. 性能考虑 ：

   • 避免频繁的小规模push/pop
   • 对于已知大小的priority_queue，预先reserve

4. 线程安全 ：

   • 标准适配器不是线程安全的
   • 需要线程安全时使用自定义实现或外部同步

5. 异常安全 ：

   • 基本操作提供强异常保证
   • 自定义类型应确保移动操作不抛出异常