C++ 容器适配器

C++容器适配器

简介

容器适配器（Container Adapters）是C++标准模板库(STL)中的特殊容器，它们基于现有的STL容器（如vector、deque或list）提供修改后的接口，以实现特定的数据结构行为。与常规容器不同，适配器不直接存储元素，而是通过封装底层容器来提供受限的功能。

C++标准库提供了三种主要的容器适配器：

• stack - 后进先出(LIFO)结构
• queue - 先进先出(FIFO)结构
• priority_queue - 带优先级的队列

底层容器选择

容器适配器默认使用以下底层容器：

• stack和queue默认使用deque
• priority_queue默认使用vector

开发者可以通过模板参数指定不同的底层容器：

#include <stack>
#include <vector>
#include <list>

std::stack<int, std::vector<int>> vec_stack;  // 使用vector作为底层容器
std::queue<int, std::list<int>> list_queue;   // 使用list作为底层容器

stack适配器

stack提供LIFO（后进先出）操作，主要方法包括：

• push() - 压入元素
• pop() - 弹出元素
• top() - 访问顶部元素
• empty() - 检查是否为空
• size() - 获取元素数量

示例代码

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    
    // 压入元素
    s.push(10);
    s.push(20);
    s.push(30);
    
    // 输出栈顶元素
    std::cout << "Top element: " << s.top() << std::endl;  // 输出30
    
    // 弹出元素
    s.pop();
    std::cout << "After pop, top element: " << s.top() << std::endl;  // 输出20
    
    // 检查栈大小
    std::cout << "Stack size: " << s.size() << std::endl;  // 输出2
    
    return 0;
}

queue适配器

queue提供FIFO（先进先出）操作，主要方法包括：

• push() - 在队尾添加元素
• pop() - 从队首移除元素
• front() - 访问队首元素
• back() - 访问队尾元素
• empty() - 检查是否为空
• size() - 获取元素数量

示例代码

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    
    // 入队
    q.push(10);
    q.push(20);
    q.push(30);
    
    // 输出队首和队尾元素
    std::cout << "Front: " << q.front() << ", Back: " << q.back() << std::endl;  // 输出Front: 10, Back: 30
    
    // 出队
    q.pop();
    std::cout << "After pop, Front: " << q.front() << std::endl;  // 输出20
    
    return 0;
}

priority_queue适配器

priority_queue提供带优先级的队列，默认是最大堆实现（最大元素总是位于队首），主要方法包括：

• push() - 添加元素
• pop() - 移除最高优先级元素
• top() - 访问最高优先级元素
• empty() - 检查是否为空
• size() - 获取元素数量

示例代码

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    
    // 插入元素
    pq.push(30);
    pq.push(10);
    pq.push(20);
    
    // 输出优先级最高的元素
    std::cout << "Top element: " << pq.top() << std::endl;  // 输出30
    
    // 弹出元素
    pq.pop();
    std::cout << "After pop, top element: " << pq.top() << std::endl;  // 输出20
    
    return 0;
}

自定义比较函数

可以通过提供比较函数来改变优先级：

#include <iostream>
#include <queue>
#include <vector>
#include <functional>  // 用于std::greater

int main() {
    // 最小堆实现
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    
    min_pq.push(30);
    min_pq.push(10);
    min_pq.push(20);
    
    std::cout << "Top element: " << min_pq.top() << std::endl;  // 输出10
    
    return 0;
}

性能考虑

不同底层容器的性能特点：

适配器	默认容器	可选容器	时间复杂度
stack	deque	vector, list	大部分操作O(1)
queue	deque	list	大部分操作O(1)
priority_queue	vector	deque	push/pop: O(log n), top: O(1)

实际应用案例

浏览器历史记录 (stack)

浏览器使用stack实现后退功能：

#include <stack>
#include <string>
#include <iostream>

class BrowserHistory {
    std::stack<std::string> back_stack;
    std::stack<std::string> forward_stack;
    
public:
    void visit(const std::string& url) {
        back_stack.push(url);
        // 清空forward栈
        while (!forward_stack.empty()) forward_stack.pop();
    }
    
    std::string back() {
        if (back_stack.size() <= 1) return "";
        forward_stack.push(back_stack.top());
        back_stack.pop();
        return back_stack.top();
    }
    
    std::string forward() {
        if (forward_stack.empty()) return "";
        back_stack.push(forward_stack.top());
        forward_stack.pop();
        return back_stack.top();
    }
};

任务调度 (priority_queue)

操作系统使用priority_queue实现任务调度：

#include <queue>
#include <iostream>
#include <string>

struct Task {
    int priority;
    std::string name;
    
    // 重载<运算符用于比较
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 更高优先级的值更大
    }
};

int main() {
    std::priority_queue<Task> scheduler;
    
    scheduler.push({3, "Low priority task"});
    scheduler.push({9, "High priority task"});
    scheduler.push({6, "Medium priority task"});
    
    while (!scheduler.empty()) {
        auto task = scheduler.top();
        std::cout << "Executing: " << task.name << std::endl;
        scheduler.pop();
    }
    
    return 0;
}

比较总结

graph TD A[容器适配器] --> B[stack] A --> C[queue] A --> D[priority_queue] B --> E[LIFO] C --> F[FIFO] D --> G[优先级排序]

常见问题

1. 为什么容器适配器不称为容器？

因为它们不提供完整的容器接口（如迭代器），而是专注于特定数据结构的操作。

2. 何时使用容器适配器而不是底层容器？

当需要特定数据结构行为（如LIFO或FIFO）且不需要底层容器的全部功能时。

3. 如何遍历容器适配器中的元素？

标准容器适配器不直接支持迭代器。如果需要遍历，可以：

• 临时复制适配器并逐个弹出元素
• 直接使用底层容器（如果可访问）

进阶主题

自定义容器适配器

可以通过继承或组合现有容器来创建自定义适配器：

template <typename T, typename Container = std::deque<T>>
class CustomStack {
protected:
    Container c;
    
public:
    void push(const T& value) { c.push_back(value); }
    void pop() { c.pop_back(); }
    T& top() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

线程安全考虑

标准容器适配器不是线程安全的。在多线程环境中使用时需要额外的同步机制，如互斥锁。

总结

C++容器适配器提供了特定数据结构的高层抽象，简化了常见模式（如堆栈和队列）的实现。理解它们的底层容器选择和性能特征对于编写高效代码至关重要。虽然它们比完整容器功能受限，但在需要特定行为时提供了简洁、类型安全的解决方案。