适配器与有序容器
stack/queue/priority_queue 适配器、set/map 红黑树原理、自定义比较器
适配器与有序容器
stack、queue、priority_queue 是容器适配器——它们包装底层容器，提供特定接口。set/map 底层是红黑树。
学完本章你将： 掌握 stack/queue/priority_queue、有序容器原理、自定义比较器。
stack —— 后进先出
cpp
#include <stack>
std::stack<int> s;
s.push(1); s.push(2); s.push(3);
while (!s.empty()) {
std::cout << s.top() << " "; // 3 2 1
s.pop();
}queue / priority_queue
cpp
#include <queue>
// queue —— 先进先出
std::queue<int> q;
q.push(1); q.push(2); q.push(3);
std::cout << q.front(); // 1
// priority_queue —— 最大堆（默认）
std::priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(5);
std::cout << pq.top(); // 5（最大的在顶部）
// 最小堆——自定义比较器
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3); min_pq.push(1); min_pq.push(5);
std::cout << min_pq.top(); // 1自定义 set/map 比较器
cpp
// 按长度排序的 set
struct ByLength {
bool operator()(const std::string& a, const std::string& b) const {
return a.length() < b.length();
}
};
std::set<std::string, ByLength> words;
words.insert("apple");
words.insert("pie");
words.insert("banana");
// 顺序: pie, apple, banana