全面掌握C++标准模板库中的容器类型，了解其特点、适用场景和最佳实践
STL容器是用于存储和管理数据集合的模板类，提供了数据组织、访问和操作的统一接口。C++标准库提供了多种容器类型，每种针对特定使用场景进行了优化。
vector, list, deque, array
set, multiset, map, multimap
unordered_set, unordered_multiset, unordered_map, unordered_multimap
stack, queue, priority_queue
#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
int main() {
// 序列容器 - vector
std::vector<int> vec = {1, 2, 3};
vec.push_back(4);
std::cout << "Vector: ";
for (int n : vec) std::cout << n << " ";
// 关联容器 - set
std::set<int> s = {3, 1, 4, 1, 5};
std::cout << "\nSet: ";
for (int n : s) std::cout << n << " ";
// 无序容器 - unordered_map
std::unordered_map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
std::cout << "\nAlice's age: " << ages["Alice"];
return 0;
}
序列容器按线性顺序存储元素，保留了元素的插入顺序。
动态数组，在内存中连续存储元素。支持快速随机访问，尾部插入/删除高效，但中间插入/删除较慢。
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
// 创建vector
std::vector<int> nums = {3, 1, 4, 1, 5, 9};
// 添加元素
nums.push_back(2);
nums.insert(nums.begin() + 2, 7); // 在索引2处插入
// 排序
std::sort(nums.begin(), nums.end());
// 遍历
std::cout << "Vector: ";
for (int n : nums) std::cout << n << " ";
// 容量操作
std::cout << "\nSize: " << nums.size();
std::cout << "\nCapacity: " << nums.capacity();
// 删除元素
nums.pop_back();
nums.erase(nums.begin() + 3);
return 0;
}
双向链表实现。在任何位置插入/删除高效，但不支持随机访问。内存占用较高（每个元素需要额外指针空间）。
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {1, 2, 3};
// 添加元素
lst.push_front(0); // 头部插入
lst.push_back(4); // 尾部插入
// 中间插入
auto it = lst.begin();
std::advance(it, 2);
lst.insert(it, 10);
// 删除元素
lst.pop_front();
lst.remove(3); // 删除所有值为3的元素
// 遍历
std::cout << "List: ";
for (int n : lst) std::cout << n << " ";
// 排序
lst.sort();
// 合并
std::list<int> lst2 = {5, 6, 7};
lst.merge(lst2);
return 0;
}
双端队列，支持在头部和尾部高效插入/删除。由多个固定大小的数组块组成，不是完全连续存储。
#include <iostream>
#include <deque>
int main() {
std::deque<int> dq = {2, 3, 4};
// 双端操作
dq.push_front(1);
dq.push_back(5);
// 访问元素
std::cout << "Front: " << dq.front();
std::cout << "\nBack: " << dq.back();
std::cout << "\nElement at index 2: " << dq[2];
// 中间插入
dq.insert(dq.begin() + 2, 10);
// 删除
dq.pop_front();
dq.pop_back();
return 0;
}
关联容器基于键自动排序元素，通常使用红黑树实现。
存储唯一键的有序集合。自动排序，不允许重复元素。
#include <iostream>
#include <set>
int main() {
std::set<int> s;
// 插入元素
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(1); // 重复元素，不会被插入
// 遍历（自动排序）
std::cout << "Set: ";
for (int n : s) std::cout << n << " "; // 1 3 4
// 查找
auto it = s.find(3);
if (it != s.end()) {
std::cout << "\nFound 3";
}
// 删除
s.erase(3);
return 0;
}
存储键值对的有序映射。键唯一，自动按键排序。
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> ages;
// 插入元素
ages["Alice"] = 30;
ages["Bob"] = 25;
ages["Charlie"] = 35;
// 插入方式2
ages.insert(std::make_pair("David", 28));
// 遍历（按键排序）
std::cout << "Ages:\n";
for (const auto& pair : ages) {
std::cout << pair.first << ": " << pair.second << "\n";
}
// 查找
auto it = ages.find("Bob");
if (it != ages.end()) {
std::cout << "Bob's age: " << it->second;
}
// 删除
ages.erase("Alice");
return 0;
}
无序容器使用哈希表实现，提供平均常数时间复杂度的操作。
基于哈希表的集合实现，元素无序存储，不允许重复。
#include <iostream>
#include <unordered_set>
#include <string>
int main() {
std::unordered_set<std::string> us;
// 插入元素
us.insert("apple");
us.insert("banana");
us.insert("orange");
us.insert("apple"); // 重复，不会被插入
// 遍历（无序）
std::cout << "Fruits: ";
for (const auto& fruit : us) {
std::cout << fruit << " ";
}
// 查找
if (us.find("banana") != us.end()) {
std::cout << "\nFound banana";
}
// 桶接口
std::cout << "\nBucket count: " << us.bucket_count();
std::cout << "\nLoad factor: " << us.load_factor();
return 0;
}
基于哈希表的键值对映射，元素无序存储，键唯一。
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> wordCount;
// 插入元素
wordCount["apple"] = 5;
wordCount["banana"] = 3;
wordCount["orange"] = 2;
// 插入方式2
wordCount.insert({"grape", 4});
// 更新值
wordCount["apple"]++;
// 遍历
std::cout << "Word counts:\n";
for (const auto& pair : wordCount) {
std::cout << pair.first << ": " << pair.second << "\n";
}
// 查找
if (wordCount.find("banana") != wordCount.end()) {
std::cout << "Banana count: " << wordCount["banana"];
}
// 桶操作
std::cout << "\nBucket for 'apple': " << wordCount.bucket("apple");
return 0;
}
容器适配器提供特定数据结构的接口，基于其他容器实现。
后进先出(LIFO)数据结构，默认基于deque实现。
#include <iostream>
#include <stack>
int main() {
std::stack<int> stk;
// 压入元素
stk.push(10);
stk.push(20);
stk.push(30);
std::cout << "Stack size: " << stk.size() << "\n";
std::cout << "Top element: " << stk.top() << "\n";
// 弹出元素
stk.pop();
std::cout << "After pop, top element: " << stk.top() << "\n";
// 检查是否为空
while (!stk.empty()) {
std::cout << "Popping: " << stk.top() << "\n";
stk.pop();
}
return 0;
}
先进先出(FIFO)数据结构，默认基于deque实现。
#include <iostream>
#include <queue>
int main() {
std::queue<std::string> q;
// 入队
q.push("Alice");
q.push("Bob");
q.push("Charlie");
std::cout << "Queue size: " << q.size() << "\n";
std::cout << "Front: " << q.front() << "\n";
std::cout << "Back: " << q.back() << "\n";
// 出队
q.pop();
std::cout << "After pop, front: " << q.front() << "\n";
// 遍历队列
std::cout << "Queue elements: ";
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
return 0;
}
优先级队列，元素按优先级排序，默认基于vector实现（大顶堆）。
#include <iostream>
#include <queue>
#include <vector>
#include <functional> // 用于greater
int main() {
// 最大堆（默认）
std::priority_queue<int> maxHeap;
maxHeap.push(30);
maxHeap.push(10);
maxHeap.push(50);
maxHeap.push(20);
std::cout << "Max Heap: ";
while (!maxHeap.empty()) {
std::cout << maxHeap.top() << " ";
maxHeap.pop();
}
// 最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(30);
minHeap.push(10);
minHeap.push(50);
minHeap.push(20);
std::cout << "\nMin Heap: ";
while (!minHeap.empty()) {
std::cout << minHeap.top() << " ";
minHeap.pop();
}
// 自定义优先级
auto cmp = [](int left, int right) {
return (left % 10) > (right % 10); // 按个位数从大到小
};
std::priority_queue<int, std::vector<int>, decltype(cmp)> customHeap(cmp);
customHeap.push(25);
customHeap.push(17);
customHeap.push(36);
customHeap.push(42);
std::cout << "\nCustom Heap: ";
while (!customHeap.empty()) {
std::cout << customHeap.top() << " ";
customHeap.pop();
}
return 0;
}
不同容器在不同场景下有各自的优势，选择合适的容器可以显著提高程序性能。
| 容器 | 内部结构 | 随机访问 | 插入/删除效率 | 内存占用 | 元素顺序 | 重复元素 | 最佳使用场景 |
|---|---|---|---|---|---|---|---|
| vector | 动态数组 | O(1) | 尾部: O(1) 中间: O(n) |
低 | 插入顺序 | 允许 | 随机访问频繁，尾部操作多 |
| list | 双向链表 | O(n) | 任意位置 O(1) | 高 | 插入顺序 | 允许 | 频繁在任意位置插入/删除 |
| deque | 分块数组 | O(1) | 头尾: O(1) 中间: O(n) |
中 | 插入顺序 | 允许 | 双端队列操作 |
| set | 红黑树 | 不支持 | O(log n) | 中 | 排序顺序 | 不允许 | 有序唯一元素集合 |
| map | 红黑树 | 不支持 | O(log n) | 中 | 按键排序 | 键唯一 | 键值对映射，需有序 |
| unordered_set | 哈希表 | 不支持 | 平均: O(1) 最差: O(n) |
中 | 无序 | 不允许 | 快速查找，不关心顺序 |
| unordered_map | 哈希表 | 不支持 | 平均: O(1) 最差: O(n) |
中 | 无序 | 键唯一 | 键值对快速查找 |
| stack | 适配器(deque) | 不支持 | 顶部 O(1) | 中 | LIFO | 允许 | 后进先出场景 |
| queue | 适配器(deque) | 不支持 | 尾部入队 O(1) 头部出队 O(1) |
中 | FIFO | 允许 | 先进先出场景 |
| priority_queue | 适配器(vector) | 不支持 | 插入: O(log n) 删除: O(log n) |
低 | 优先级顺序 | 允许 | 优先级调度，堆操作 |
| 操作 | vector | list | deque | set/map | unordered_set/map |
|---|---|---|---|---|---|
| 随机访问 | O(1) | O(n) | O(1) | O(n) | O(n) |
| 头部插入 | O(n) | O(1) | O(1) | O(log n) | 平均 O(1) |
| 尾部插入 | 平均 O(1) | O(1) | O(1) | O(log n) | 平均 O(1) |
| 中间插入 | O(n) | O(1) | O(n) | O(log n) | 平均 O(1) |
| 查找元素 | O(n) | O(n) | O(n) | O(log n) | 平均 O(1) |
| 删除元素 | O(n) | O(1) | O(n) | O(log n) | 平均 O(1) |