C++中，标准库中的容器

C++ 标准库（std）中的 容器（Containers） 是 STL（Standard Template Library）的核心组成部分，它们为你提供了各种高效、通用的数据结构，让你无需“重复造轮子”。

---

🧭 一、std 容器分类总览

C++ 标准容器主要分为三大类：

类型	特点	常见容器
✅ 序列容器（Sequence Containers）	元素按线性顺序存储，位置决定含义	vector, list, deque, array, forward_list
✅ 关联容器（Associative Containers）	元素按键排序，支持快速查找	set, map, multiset, multimap
✅ 无序关联容器（Unordered Associative Containers）	哈希表实现，查找更快，不排序	unordered_set, unordered_map, unordered_multiset, unordered_multimap
✅ 容器适配器（Container Adapters）	基于其他容器封装的“受限接口”容器	stack, queue, priority_queue

✅ 容器所在头文件

容器	对应的头文件	include格式
std::vector	<vector>	#include <vector>
std::map	<map>	#include <map>
std::list	<list>	#include <list>
std::stack	<stack>	#include <stack>
std::unordered_set	<unordered_set>	#include <unordered_set>

📌 所有容器都在 <xxx> 头文件中，使用前需 #include <xxx>，并位于 std 命名空间下。

---

📦 二、详细容器介绍 + 示例

1️⃣ 序列容器（Sequence Containers）

➤ std::vector<T> —— 动态数组（最常用）

#include <vector>
std::vector<int> v = {1, 2, 3};
v.push_back(4); // [1,2,3,4]

✅ 随机访问 O(1)，尾部增删快，中间插入慢

➤ std::list<T> —— 双向链表

#include <list>
std::list<int> lst = {1, 2, 3};
lst.push_front(0); // [0,1,2,3]
lst.push_back(4);  // [0,1,2,3,4]
lst.splice(lst.begin(), lst, --lst.end()); // 移动元素，高效！

✅ 任意位置插入/删除 O(1)，不支持随机访问，内存开销大

➤ std::deque<T> —— 双端队列（double-ended queue）

#include <deque>
std::deque<int> dq = {1, 2, 3};
dq.push_front(0); // [0,1,2,3]
dq.push_back(4);  // [0,1,2,3,4]
int x = dq[2];    // 支持随机访问！

✅ 头尾插入删除都快 O(1)，支持随机访问（但不如 vector 快）

➤ std::array<T, N> —— 固定大小数组（C++11）

#include <array>
std::array<int, 5> arr = {1, 2, 3, 4, 5};
arr[0] = 10;
std::cout << arr.size(); // 5

✅ 替代 C 风格数组，支持 STL 算法，栈上分配，零开销

➤ std::forward_list<T> —— 单向链表（C++11）

#include <forward_list>
std::forward_list<int> fl = {1, 2, 3};
fl.push_front(0);

✅ 比 list 更省内存，只支持单向遍历，无 size()

2️⃣ 关联容器（Associative Containers）—— 基于红黑树，自动排序

➤ std::set<T> —— 有序、唯一元素集合

#include <set>
std::set<int> s = {3, 1, 4, 1, 5}; // 自动去重+排序 → {1,3,4,5}
s.insert(2);
auto it = s.find(3); // O(log n)

✅ 不能修改元素值（因为排序依赖值），可删+插

➤ std::map<Key, Value> —— 有序键值对

#include <map>
std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;

for (const auto& p : ages) {
    std::cout << p.first << ": " << p.second << "\n"; // 按 key 排序输出
}

✅ key 唯一，自动按 key 排序，支持 [] 访问（不存在则插入默认值）

➤ std::multiset<T> / std::multimap<Key, Value> —— 允许重复元素/键

std::multiset<int> ms = {1, 1, 2, 2, 3};
std::multimap<std::string, std::string> mm;
mm.insert({"tag", "C++"});
mm.insert({"tag", "STL"});

✅ 用于需要“一对多”或“允许重复”的场景

3️⃣ 无序关联容器（哈希表实现）—— C++11 引入，查找更快

➤ std::unordered_set<T> —— 无序唯一集合

#include <unordered_set>
std::unordered_set<std::string> us = {"apple", "banana", "cherry"};
if (us.count("apple")) { ... } // O(1) 平均

✅ 查找/插入/删除平均 O(1)，最坏 O(n)，不保证顺序

➤ std::unordered_map<Key, Value> —— 无序键值对（最常用 map 替代）

#include <unordered_map>
std::unordered_map<std::string, int> word_count;
word_count["hello"]++; // 自动初始化为0再加1

✅ 性能通常优于 map，除非你需要排序

➤ std::unordered_multiset<T> / std::unordered_multimap<K,V> —— 允许重复，无序

4️⃣ 容器适配器（Container Adapters）—— 封装其他容器，提供受限接口

➤ std::stack<T> —— 栈（LIFO）

#include <stack>
std::stack<int> stk;
stk.push(1);
stk.push(2);
std::cout << stk.top(); // 2
stk.pop(); // 删除2

✅ 默认基于 deque，也可指定：stack<int, vector<int>>

➤ std::queue<T> —— 队列（FIFO）

#include <queue>
std::queue<int> q;
q.push(1);
q.push(2);
std::cout << q.front(); // 1
q.pop();

✅ 默认基于 deque

➤ std::priority_queue<T> —— 优先队列（默认最大堆）

#include <queue>
std::priority_queue<int> pq; // 最大堆
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << pq.top(); // 4（最大值）
pq.pop();

✅ 可自定义比较器实现最小堆：

std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

🆚 三、如何选择容器？速查表

需求	推荐容器
需要随机访问 + 动态大小	vector
频繁在中间插入/删除	list 或 forward_list
需要头尾高效操作	deque
固定大小数组	array
需要排序 + 快速查找	set / map
只需快速查找，不关心顺序	unordered_set / unordered_map
栈结构（LIFO）	stack
队列结构（FIFO）	queue
需要按优先级取元素	priority_queue

---

🧩 四、所有容器共有的常用操作

container.empty()     // 是否为空
container.size()      // 元素个数
container.clear()     // 清空
container.begin()/end() // 迭代器

✅ 几乎所有容器都支持范围 for 循环：

for (const auto& item : my_container) { ... }

---

🎯 五、举个综合例子：统计单词频率

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

int main() {
    std::vector<std::string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};

    // 用 unordered_map 统计词频
    std::unordered_map<std::string, int> freq;
    for (const auto& word : words) {
        freq[word]++;
    }

    // 输出结果
    for (const auto& [word, count] : freq) { // C++17 结构化绑定
        std::cout << word << ": " << count << "\n";
    }

    return 0;
}

输出：

apple: 3
banana: 2
cherry: 1

---

✅ 总结

std 命名空间下提供了丰富、高效、安全的容器，覆盖几乎所有数据结构需求：

• vector, list, deque, array, forward_list
• set, map, multiset, multimap
• unordered_set, unordered_map, unordered_multiset, unordered_multimap
• stack, queue, priority_queue

💡 现代 C++ 编程建议：优先使用标准容器，而不是手写数组或链表 —— 更安全、更高效、更易维护！