C++:STL—容器

---

代码链接：https://gitee.com/hu_yuchen/code/tree/master/C+±Review/4.STL

STL 容器概述

STL（标准模板库）容器是 C++ 标准库的核心组件，用于高效存储和操作数据。它们分为以下几类：

• 序列容器：vector、list、deque、array、forward_list，适合线性数据存储。
• 关联容器：map、set、multimap、multiset，基于红黑树，适合有序键值或集合操作。
• 无序关联容器：unordered_map、unordered_set、unordered_multimap、unordered_multiset，基于哈希表，适合高效查找。
• 容器适配器：stack、queue、priority_queue，提供特定操作模式（如 LIFO、FIFO、优先级）。

每个容器针对特定场景优化，底层实现结合了经典数据结构（如数组、链表、红黑树、哈希表）和高效算法。选择合适的容器能显著提升程序性能。以下逐一分析每个容器的结构、实现、使用方法及扩充知识点，并通过详细代码示例展示其功能。

---

一、vector

1. 是什么结构，底层是什么？

• 结构：动态数组，支持随机访问，元素连续存储，可动态扩展。
• 底层实现：
  • 基于连续内存块（类似 C 风格数组），通过三个指针管理：begin（起始）、end（最后一个元素的下一位置）、end_of_storage（分配内存的末尾）。
  • 扩容机制：当 size 达到 capacity 时，vector 分配一块更大的内存（通常为当前容量的 2 倍），将原有元素复制或移动到新内存，释放旧内存。扩容导致迭代器失效。
  • 内存分配：使用分配器（allocator）管理内存，默认为 std::allocator。
  • 性能特性：
    • 随机访问：O(1)，因连续存储。
    • 尾部插入/删除：O(1) 均摊，因扩容均摊成本。
    • 中间插入/删除：O(n)，需移动后续元素。
    • 扩容：O(n)，但均摊 O(1)。
• 扩充知识：
  • 迭代器失效：插入可能导致扩容，使所有迭代器、指针、引用失效；删除使后续迭代器失效。
  • 分配器：可自定义分配器，优化内存管理（如池分配）。
  • 缓存友好：连续存储对 CPU 缓存友好，适合大数据量访问。

2. 如何使用，支持哪些使用方法？

• 头文件：<vector>
• 用途：替代静态数组，适合需要动态扩展、随机访问的场景，如数据缓冲区、矩阵存储。
• 构造方式（扩充）：
  • 默认构造：vector<int> v;
  • 指定大小：vector<int> v(n);（默认值初始化）
  • 指定大小和值：vector<int> v(n, val);
  • 初始列表：vector<int> v = {1, 2, 3};
  • 范围构造：vector<int> v(other.begin(), other.end());
  • 拷贝构造：vector<int> v2(v1);
  • 移动构造：vector<int> v2(std::move(v1));
• 常用方法（扩充）：
  • 访问：
    • v[i]：下标访问，无边界检查。
    • v.at(i)：带边界检查，抛出 std::out_of_range。
    • front()/back()：访问首/尾元素。
    • data()：返回底层数组指针。
  • 添加：
    • push_back(val)：尾部添加。
    • emplace_back(args...)：尾部构造（更高效）。
    • insert(pos, val)：指定位置插入。
    • insert(pos, n, val)：插入 n 个值。
    • insert(pos, first, last)：插入范围。
  • 删除：
    • pop_back()：删除尾部。
    • erase(pos)：删除指定位置。
    • erase(first, last)：删除范围。
    • clear()：清空所有元素。
  • 大小与容量：
    • size()：元素数量。
    • capacity()：当前容量。
    • empty()：是否为空。
    • resize(n)：调整大小，填充默认值或截断。
    • resize(n, val)：调整大小，填充指定值。
    • reserve(n)：预分配容量。
    • shrink_to_fit()：释放多余容量（C++11）。
  • 迭代：
    • begin()/end()：正向迭代器。
    • rbegin()/rend()：反向迭代器。
    • cbegin()/cend()：常量迭代器（C++11）。
  • 其他：
    • swap(v2)：交换两个 vector。
    • assign(n, val)：重新赋值 n 个值。
    • assign(first, last)：重新赋值范围。

代码示例（扩充）：

#include <iostream>
#include <vector>
using namespace std;int main() {// 多种构造vector<int> v1; // 默认vector<int> v2(3, 10); // 3 个 10vector<int> v3 = {1, 2, 3}; // 初始列表vector<int> v4(v3.begin(), v3.end()); // 范围构造vector<int> v5(v3); // 拷贝构造// 添加元素v1.push_back(1); // 1v1.emplace_back(2); // 1, 2v1.insert(v1.begin(), 0); // 0, 1, 2v1.insert(v1.end(), 2, 3); // 0, 1, 2, 3, 3// 访问cout << "v1[0]: " << v1[0] << endl; // 0cout << "front: " << v1.front() << ", back: " << v1.back() << endl; // 0, 3// 遍历cout << "v1: ";for (auto it = v1.cbegin(); it != v1.cend(); ++it) {cout << *it << " "; // 0 1 2 3 3}cout << endl;// 删除v1.erase(v1.begin() + 1); // 删除 1v1.erase(v1.begin(), v1.begin() + 2); // 删除 0, 2cout << "After erase: ";for (int x : v1) {cout << x << " "; // 3 3}cout << endl;// 大小与容量v1.reserve(100); // 预分配cout << "Size: " << v1.size() << ", Capacity: " << v1.capacity() << endl;v1.shrink_to_fit(); // 释放多余容量cout << "After shrink, Capacity: " << v1.capacity() << endl;// 交换vector<int> v6 = {4, 5};v1.swap(v6);cout << "v1 after swap: ";for (int x : v1) {cout << x << " "; // 4 5}cout << endl;return 0;
}

理解与扩充：

• 性能优化：使用 reserve 预分配容量可避免频繁扩容；emplace_back 比 push_back 更高效（避免拷贝）。
• 迭代器失效：插入可能导致扩容，所有迭代器失效；删除使后续迭代器失效，需谨慎使用。
• 应用场景：vector 适合存储表格数据、缓冲区、矩阵等需要快速访问的场景，但不适合频繁中间插入/删除。
• 底层细节：扩容因子（通常 2）因实现而异，MSVC 和 GCC 可能不同；分配器可定制以优化内存分配。

---

二、list

1. 是什么结构，底层是什么？

• 结构：双向链表，元素非连续存储，支持双向遍历。
• 底层实现：
  • 基于双向链表，每个节点包含元素值、前指针、后指针。节点通过指针连接，插入/删除只需调整指针。
  • 内存管理：使用分配器动态分配节点，节点分散在内存中。
  • 性能特性：
    • 随机访问：O(n)，需遍历。
    • 插入/删除：O(1)（已知位置）。
    • 头部/尾部操作：O(1)。
  • 迭代器：双向迭代器，支持正向和反向遍历，但不支持随机访问。
• 扩充知识：
  • 节点管理：list 维护一个伪头节点（不存储数据），简化边界操作。
  • 迭代器稳定性：插入/删除不影响其他迭代器（除被删除元素），适合动态调整。
  • 内存开销：每个节点需额外存储前后指针，空间效率低于 vector。
  • 缓存不友好：非连续存储导致缓存命中率低，遍历性能较差。

2. 如何使用，支持哪些使用方法？

• 头文件：<list>
• 用途：适合频繁插入/删除的场景，如动态列表、任务队列。
• 构造方式（扩充）：
  • 默认构造：list<int> lst;
  • 指定大小：list<int> lst(n);
  • 指定大小和值：list<int> lst(n, val);
  • 初始列表：list<int> lst = {1, 2, 3};
  • 范围构造：list<int> lst(other.begin(), other.end());
  • 拷贝/移动构造：list<int> lst2(lst1);, list<int> lst2(std::move(lst1));
• 常用方法（扩充）：
  • 添加：
    • push_front(val)/push_back(val)：头部/尾部添加。
    • emplace_front(args...)/emplace_back(args...)：头部/尾部构造。
    • insert(pos, val)：指定位置插入。
    • insert(pos, n, val)：插入 n 个值。
    • insert(pos, first, last)：插入范围。
  • 删除：
    • pop_front()/pop_back()：删除头部/尾部。
    • erase(pos)：删除指定位置。
    • erase(first, last)：删除范围。
    • clear()：清空。
    • remove(val)：删除所有等于 val 的元素。
    • remove_if(pred)：删除满足谓词的元素。
  • 大小：
    • size()：元素数量（C++11 前可能 O(n)）。
    • empty()：是否为空。
  • 操作：
    • splice(pos, other)：将 other 整个链表拼接。
    • splice(pos, other, it)：拼接 other 的单个元素。
    • splice(pos, other, first, last)：拼接 other 的范围。
    • sort()：排序（默认升序）。
    • sort(comp)：自定义比较器排序。
    • merge(other)：合并有序链表。
    • unique()：删除连续重复元素。
    • reverse()：反转链表。
  • 迭代：
    • begin()/end()：双向迭代器。
    • rbegin()/rend()：反向迭代器。

代码示例（扩充）：

#include <iostream>
#include <list>
using namespace std;int main() {// 构造list<int> lst = {3, 2, 1};list<int> lst2(2, 5); // 5, 5// 添加lst.push_front(0); // 0, 3, 2, 1lst.emplace_back(4); // 0, 3, 2, 1, 4lst.insert(++lst.begin(), 10); // 0, 10, 3, 2, 1, 4// 遍历cout << "lst: ";for (auto x : lst) {cout << x << " "; // 0 10 3 2 1 4}cout << endl;// 删除lst.pop_front(); // 10, 3, 2, 1, 4lst.remove(2); // 删除所有 2cout << "After remove 2: ";for (auto x : lst) {cout << x << " "; // 10 3 1 4}cout << endl;// 排序lst.sort(); // 1, 3, 4, 10cout << "Sorted: ";for (auto x : lst) {cout << x << " "; // 1 3 4 10}cout << endl;// 拼接lst.splice(lst.begin(), lst2); // 将 lst2 拼接至 lst 开头cout << "After splice: ";for (auto x : lst) {cout << x << " "; // 5 5 1 3 4 10}cout << endl;// 去重lst.sort();lst.unique(); // 删除连续重复元素cout << "After unique: ";for (auto x : lst) {cout << x << " "; // 1 3 4 5 10}cout << endl;return 0;
}

理解与扩充：

• 性能优化：splice 和 merge 是 list 的高效操作，复杂度 O(1) 或 O(n)，适合链表合并。
• 迭代器稳定性：list 的插入/删除不影响其他迭代器，适合动态调整场景。
• 应用场景：list 适合任务队列、双端操作、频繁插入/删除的场景，但不适合需要快速索引的场景。
• 底层细节：伪头节点简化了边界处理；size() 在 C++98 中可能 O(n)，C++11 后优化为 O(1)。

---

三、stack

1. 是什么结构，底层是什么？

• 结构：栈，遵循后进先出（LIFO）原则。
• 底层实现：
  • 容器适配器，默认基于 deque，可指定 vector 或 list。
  • 适配机制：通过封装底层容器接口，仅暴露栈操作（push, pop, top）。
  • 性能特性：
    • 入栈/出栈：O(1)（依赖底层容器）。
    • 访问栈顶：O(1)。
  • 限制：无迭代器，仅栈顶可访问。
• 扩充知识：
  • 底层容器选择：
    • deque：默认，高效尾部操作，内存分块存储。
    • vector：连续存储，扩容可能影响性能。
    • list：适合动态调整，但内存开销大。
  • 内存管理：继承底层容器的分配器。
  • 线程安全：stack 本身非线程安全，需外部同步。

2. 如何使用，支持哪些使用方法？

• 头文件：<stack>
• 用途：实现栈结构，适合递归模拟、表达式求值、回溯算法。
• 构造方式（扩充）：
  • 默认构造：stack<int> s;
  • 指定容器：stack<int, vector<int>> s;
  • 拷贝构造：stack<int> s2(s1);
  • 移动构造：stack<int> s2(std::move(s1));
• 常用方法（扩充）：
  • push(val)：入栈。
  • emplace(args...)：构造入栈。
  • pop()：出栈（无返回值）。
  • top()：访问栈顶。
  • size()：元素数量。
  • empty()：是否为空。
  • swap(s2)：交换两个 stack。

代码示例（扩充）：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;int main() {// 构造stack<int> s; // 默认 dequestack<int, vector<int>> s_vec; // 使用 vector// 入栈s.push(1);s.push(2);s.emplace(3); // 构造入栈// 访问cout << "Top: " << s.top() << endl; // 3// 出栈s.pop();cout << "Top after pop: " << s.top() << endl; // 2// 大小cout << "Size: " << s.size() << endl; // 2// 交换stack<int> s2;s2.push(4);s.swap(s2);cout << "s top after swap: " << s.top() << endl; // 4cout << "s2 top: " << s2.top() << endl; // 2return 0;
}

理解与扩充：

• 性能优化：emplace 避免拷贝；选择合适的底层容器（如 vector 节省空间）。
• 应用场景：stack 适合表达式求值（如中缀转后缀）、深度优先搜索、函数调用栈模拟。
• 底层细节：stack 通过模板参数 Container 适配底层容器，接口简洁但功能有限。

---

四、queue

1. 是什么结构，底层是什么？

• 结构：队列，遵循先进先出（FIFO）原则。
• 底层实现：
  • 容器适配器，默认基于 deque，可指定 list。
  • 适配机制：封装底层容器，仅暴露队列操作（push, pop, front, back）。
  • 性能特性：
    • 入队/出队：O(1)。
    • 访问队首/队尾：O(1)。
  • 限制：无迭代器，仅队首/队尾可访问。
• 扩充知识：
  • 底层容器选择：
    • deque：高效首尾操作，分块存储。
    • list：适合动态调整，但内存开销大。
  • 内存管理：继承底层容器分配器。
  • 变种：std::deque 提供双端队列功能，queue 是其子集。

2. 如何使用，支持哪些使用方法？

• 头文件：<queue>
• 用途：实现队列，适合任务调度、广度优先搜索、缓冲区。
• 构造方式（扩充）：
  • 默认构造：queue<int> q;
  • 指定容器：queue<int, list<int>> q;
  • 拷贝/移动构造：queue<int> q2(q1);, queue<int> q2(std::move(q1));
• 常用方法（扩充）：
  • push(val)：入队。
  • emplace(args...)：构造入队。
  • pop()：出队。
  • front()：访问队首。
  • back()：访问队尾。
  • size()：元素数量。
  • empty()：是否为空。
  • swap(q2)：交换两个 queue。

代码示例（扩充）：

#include <iostream>
#include <queue>
#include <list>
using namespace std;int main() {// 构造queue<int> q; // 默认 dequequeue<int, list<int>> q_list; // 使用 list// 入队q.push(1);q.push(2);q.emplace(3);// 访问cout << "Front: " << q.front() << endl; // 1cout << "Back: " << q.back() << endl; // 3// 出队q.pop();cout << "Front after pop: " << q.front() << endl; // 2// 大小cout << "Size: " << q.size() << endl; // 2// 交换queue<int> q2;q2.push(4);q.swap(q2);cout << "q front after swap: " << q.front() << endl; // 4cout << "q2 front: " << q2.front() << endl; // 2return 0;
}

理解与扩充：

• 性能优化：emplace 避免拷贝；deque 作为默认容器平衡了性能和内存。
• 应用场景：queue 适合任务队列、消费者-生产者模型、BFS。
• 底层细节：queue 通过限制 deque 接口实现 FIFO，简洁但功能有限。

---

五、priority_queue

1. 是什么结构，底层是什么？

• 结构：优先队列，元素按优先级（默认最大值优先）出队。
• 底层实现：
  • 基于堆（默认最大堆），使用 vector 存储。
  • 堆实现：通过 std::make_heap, std::push_heap, std::pop_heap 维护堆性质。
  • 比较器：默认 std::less<T>（最大堆），可指定 std::greater<T>（最小堆）。
  • 性能特性：
    • 入队/出队：O(log n)（调整堆）。
    • 访问队首：O(1)。
  • 限制：无迭代器，仅队首可访问。
• 扩充知识：
  • 堆结构：完全二叉树，存储在 vector 中，父子节点通过索引计算（父：i/2，子：2i, 2i+1）。
  • 调整算法：插入时上滤（sift-up），删除时下滤（sift-down）。
  • 内存管理：继承 vector 的分配器。
  • 自定义比较器：可定义复杂优先级规则。

2. 如何使用，支持哪些使用方法？

• 头文件：<queue>
• 用途：实现优先级调度，适合贪心算法、Dijkstra 算法、事件调度。
• 构造方式（扩充）：
  • 默认构造（最大堆）：priority_queue<int> pq;
  • 最小堆：priority_queue<int, vector<int>, greater<int>> pq;
  • 范围构造：priority_queue<int> pq(v.begin(), v.end());
  • 自定义比较器：priority_queue<int, vector<int>, MyComp> pq;
• 常用方法（扩充）：
  • push(val)：入队。
  • emplace(args...)：构造入队。
  • pop()：出队。
  • top()：访问队首。
  • size()：元素数量。
  • empty()：是否为空。
  • swap(pq2)：交换两个 priority_queue。

代码示例（扩充）：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main() {// 最大堆priority_queue<int> pq;pq.push(3);pq.push(1);pq.emplace(4);cout << "Top: " << pq.top() << endl; // 4pq.pop();cout << "Top after pop: " << pq.top() << endl; // 3// 最小堆priority_queue<int, vector<int>, greater<int>> min_pq({3, 1, 4});cout << "Min Top: " << min_pq.top() << endl; // 1// 自定义比较器struct MyComp {bool operator()(int a, int b) { return a > b; } // 最小堆};priority_queue<int, vector<int>, MyComp> custom_pq;custom_pq.push(3);custom_pq.push(1);custom_pq.push(4);cout << "Custom Top: " << custom_pq.top() << endl; // 1return 0;
}

理解与扩充：

• 性能优化：emplace 避免拷贝；初始范围构造可减少插入次数。
• 应用场景：priority_queue 适合任务调度（高优先级先执行）、Huffman 编码、图算法。
• 底层细节：堆基于 vector 实现，调整算法确保堆性质；比较器决定优先级。

---

六、map

1. 是什么结构，底层是什么？

• 结构：有序键值对容器，键唯一，键按升序（默认）存储。
• 底层实现：
  • 基于红黑树（平衡二叉搜索树），每个节点存储键值对（pair<const Key, T>）。
  • 红黑树特性：通过颜色（红/黑）和旋转操作保持平衡，树高 O(log n)。
  • 内存管理：使用分配器管理节点，节点非连续存储。
  • 性能特性：
    • 查找、插入、删除：O(log n)。
    • 遍历：O(n)，按键升序。
  • 比较器：默认 std::less<Key>（升序），可自定义。
• 扩充知识：
  • 红黑树细节：节点包含键值对、左右子节点、父节点、颜色。插入/删除通过旋转和颜色调整保持平衡。
  • 迭代器：双向迭代器，按键序遍历，键不可修改（const Key）。
  • 内存开销：每个节点需存储指针和颜色，空间效率低于哈希表。
  • 平衡性：红黑树保证最坏情况 O(log n)，优于普通 BST。

2. 如何使用，支持哪些使用方法？

• 头文件：<map>
• 用途：存储键值对，适合字典、计数、按键排序的场景。
• 构造方式（扩充）：
  • 默认构造：map<string, int> m;
  • 初始列表：map<string, int> m = {{"a", 1}, {"b", 2}};
  • 范围构造：map<string, int> m(other.begin(), other.end());
  • 拷贝/移动构造：map<string, int> m2(m1);, map<string, int> m2(std::move(m1));
  • 自定义比较器：map<string, int, greater<string>> m;（降序）。
• 常用方法（扩充）：
  • 插入：
    • m[key] = val：插入或更新。
    • insert(pair)：插入键值对。
    • insert(pos, pair)：带提示位置插入（优化性能）。
    • insert(first, last)：插入范围。
    • emplace(args...)：构造插入。
    • insert_or_assign(key, val)（C++17）：插入或覆盖。
  • 查找：
    • find(key)：返回迭代器。
    • count(key)：返回键出现次数（0 或 1）。
    • at(key)：带边界检查访问，抛出 std::out_of_range。
    • lower_bound(key)/upper_bound(key)：查找键的范围。
  • 删除：
    • erase(key)：删除指定键。
    • erase(pos)：删除迭代器位置。
    • erase(first, last)：删除范围。
    • clear()：清空。
  • 大小：
    • size()：元素数量。
    • empty()：是否为空。
    • max_size()：最大可能元素数。
  • 其他：
    • swap(m2)：交换两个 map。
    • key_comp()/value_comp()：返回比较器。

代码示例（扩充）：

#include <iostream>
#include <map>
#include <string>
using namespace std;int main() {// 构造map<string, int> m = {{"apple", 5}, {"banana", 3}};map<string, int, greater<string>> m_desc; // 降序// 插入m["orange"] = 2;m.insert({"grape", 4});m.emplace("pear", 1);m.insert_or_assign("apple", 6); // 覆盖 apple// 遍历cout << "m: ";for (const auto& p : m) {cout << p.first << ":" << p.second << " "; // apple:6 banana:3 grape:4 orange:2 pear:1}cout << endl;// 查找auto it = m.find("banana");if (it != m.end()) {cout << "Found banana: " << it->second << endl; // 3}cout << "apple count: " << m.count("apple") << endl; // 1// 范围查找auto lb = m.lower_bound("b");auto ub = m.upper_bound("c");cout << "Keys [b, c): ";for (auto it = lb; it != ub; ++it) {cout << it->first << ":" << it->second << " "; // banana:3}cout << endl;// 删除m.erase("banana");m.erase(m.find("grape"), m.end()); // 删除 grape 及之后cout << "After erase: ";for (const auto& p : m) {cout << p.first << ":" << p.second << " "; // apple:6}cout << endl;return 0;
}

理解与扩充：

• 性能优化：使用 insert(pos, pair) 可利用红黑树局部性；emplace 避免拷贝。
• 迭代器稳定性：插入/删除不影响其他迭代器（除被删除元素）。
• 应用场景：map 适合有序字典、频率统计、按键排序的场景，如词频表、配置文件解析。
• 底层细节：红黑树的旋转操作（左旋、右旋）确保平衡；比较器可自定义（如忽略大小写）。

---

七、set

1. 是什么结构，底层是什么？

• 结构：有序集合，元素唯一，元素按升序（默认）存储。
• 底层实现：
  • 基于红黑树，每个节点存储元素值。
  • 红黑树特性：平衡树，树高 O(log n)，通过旋转和颜色调整保持平衡。
  • 性能特性：
    • 查找、插入、删除：O(log n)。
    • 遍历：O(n)，按升序。
  • 比较器：默认 std::less<T>，可自定义。
• 扩充知识：
  • 红黑树细节：节点包含值、左右子节点、父节点、颜色。平衡操作类似 map。
  • 迭代器：双向迭代器，元素不可修改（const T）。
  • 内存开销：节点存储指针和颜色，空间效率低于哈希表。
  • 平衡性：红黑树保证最坏情况 O(log n)。

2. 如何使用，支持哪些使用方法？

• 头文件：<set>
• 用途：存储唯一元素，适合去重、排序、集合操作。
• 构造方式（扩充）：
  • 默认构造：set<int> s;
  • 初始列表：set<int> s = {1, 2, 3};
  • 范围构造：set<int> s(v.begin(), v.end());
  • 自定义比较器：set<int, greater<int>> s;（降序）。
• 常用方法（扩充）：
  • 插入：
    • insert(val)：插入元素。
    • insert(pos, val)：带提示位置插入。
    • insert(first, last)：插入范围。
    • emplace(args...)：构造插入。
  • 查找：
    • find(val)：返回迭代器。
    • count(val)：返回元素出现次数（0 或 1）。
    • lower_bound(val)/upper_bound(val)：查找范围。
  • 删除：
    • erase(val)：删除指定值。
    • erase(pos)：删除迭代器位置。
    • erase(first, last)：删除范围。
  • 大小：
    • size()：元素数量。
    • empty()：是否为空。
  • 其他：
    • swap(s2)：交换两个 set。
    • key_comp()：返回比较器。

code 示例（扩充）：

#include <iostream>
#include <set>
using namespace std;int main() {// 构造set<int> s = {3, 1, 3}; // 自动去重set<int, greater<int>> s_desc; // 降序// 插入s.insert(2);s.emplace(4);cout << "s: ";for (auto x : s) {cout << x << " "; // 1 2 3 4}cout << endl;// 查找if (s.find(2) != s.end()) {cout << "Found 2" << endl;}cout << "Count of 3: " << s.count(3) << endl; // 1// 范围查找auto lb = s.lower_bound(2);auto ub = s.upper_bound(3);cout << "Elements [2, 3]: ";for (auto it = lb; it != ub; ++it) {cout << *it << " "; // 2 3}cout << endl;// 删除s.erase(1);s.erase(s.find(2), s.end()); // 删除 2 及之后cout << "After erase: ";for (auto x : s) {cout << x << " "; // 3}cout << endl;return 0;
}

理解与扩充：

• 性能优化：insert(pos, val) 利用红黑树局部性；emplace 避免拷贝。
• 应用场景：set 适合去重、排序、集合交并差操作。
• 底层细节：红黑树与 map 类似，但仅存储值；比较器可自定义排序规则。

---

八、multiset

1. 是什么结构，底层是什么？

• 结构：有序多重集合，允许重复元素，按升序（默认）存储。
• 底层实现：
  • 基于红黑树，支持重复元素，结构与 set 类似。
  • 性能特性：
    • 查找、插入、删除：O(log n)。
    • 遍历：O(n)，按升序。
  • 比较器：默认 std::less<T>。
• 扩充知识：
  • 重复处理：红黑树允许相同值的节点，维护插入顺序。
  • 迭代器：双向迭代器，元素不可修改。
  • 内存开销：与 set 相同，空间效率较低。

2. 如何使用，支持哪些使用方法？

• 头文件：<set>
• 用途：存储可重复的有序元素，适合频率统计、排序。
• 构造方式（扩充）：
  • 默认构造：multiset<int> ms;
  • 初始列表：multiset<int> ms = {1, 1, 2};
  • 范围构造：multiset<int> ms(v.begin(), v.end());
  • 自定义比较器：multiset<int, greater<int>> ms;
• 常用方法（扩充）：
  • 插入：
    • insert(val)：插入元素。
    • insert(pos, val)：带提示位置插入。
    • insert(first, last)：插入范围。
    • emplace(args...)：构造插入。
  • 查找：
    • find(val)：返回第一个匹配的迭代器。
    • count(val)：返回元素出现次数。
    • equal_range(val)：返回元素范围。
    • lower_bound(val)/upper_bound(val)：查找范围。
  • 删除：
    • erase(val)：删除所有等于 val 的元素。
    • erase(pos)：删除迭代器位置。
    • erase(first, last)：删除范围。
  • 大小：
    • size()：元素数量。
    • empty()：是否为空。

code 示例（扩充）：

#include <iostream>
#include <set>
using namespace std;int main() {// 构造multiset<int> ms = {1, 1, 2};// 插入ms.insert(2);ms.emplace(3);cout << "ms: ";for (auto x : ms) {cout << x << " "; // 1 1 2 2 3}cout << endl;// 查找cout << "Count of 1: " << ms.count(1) << endl; // 2auto range = ms.equal_range(2);cout << "Elements == 2: ";for (auto it = range.first; it != range.second; ++it) {cout << *it << " "; // 2 2}cout << endl;// 删除ms.erase(ms.find(1)); // 删除一个 1ms.erase(2); // 删除所有 2cout << "After erase: ";for (auto x : ms) {cout << x << " "; // 1 3}cout << endl;return 0;
}

理解与扩充：

• 性能优化：equal_range 高效查找重复元素；emplace 避免拷贝。
• 应用场景：multiset 适合统计元素频率、维护有序可重复集合。
• 底层细节：红黑树支持重复值，通过插入顺序区分相同元素。

---

九、multimap

1. 是什么结构，底层是什么？

• 结构：有序多重键值对容器，允许重复键，按键升序（默认）存储。
• 底层实现：
  • 基于红黑树，支持重复键，结构与 map 类似。
  • 性能特性：
    • 查找、插入、删除：O(log n)。
    • 遍历：O(n)，按键升序。
  • 比较器：默认 std::less<Key>。
• 扩充知识：
  • 重复键：红黑树允许相同键的节点，维护插入顺序。
  • 迭代器：双向迭代器，键不可修改。
  • 内存开销：与 map 相同，空间效率较低。

2. 如何使用，支持哪些使用方法？

• 头文件：<map>
• 用途：存储可重复键的键值对，适合一对多映射。
• 构造方式（扩充）：
  • 默认构造：multimap<string, int> mm;
  • 初始列表：multimap<string, int> mm = {{"a", 1}, {"a", 2}};
  • 范围构造：multimap<string, int> mm(m.begin(), m.end());
  • 自定义比较器：multimap<string, int, greater<string>> mm;
• 常用方法（扩充）：
  • 插入：
    • insert(pair)：插入键值对。
    • insert(pos, pair)：带提示位置插入。
    • insert(first, last)：插入范围。
    • emplace(args...)：构造插入。
  • 查找：
    • find(key)：返回第一个匹配的迭代器。
    • count(key)：返回键出现次数。
    • equal_range(key)：返回键的范围。
    • lower_bound(key)/upper_bound(key)：查找范围。
  • 删除：
    • erase(key)：删除所有等于 key 的键值对。
    • erase(pos)：删除迭代器位置。
    • erase(first, last)：删除范围。
  • 大小：
    • size()：元素数量。
    • empty()：是否为空。

code 示例（扩充）：

#include <iostream>
#include <map>
using namespace std;int main() {// 构造multimap<string, int> mm = {{"apple", 1}, {"apple", 2}};// 插入mm.insert({"banana", 3});mm.emplace("apple", 4);cout << "mm: ";for (const auto& p : mm) {cout << p.first << ":" << p.second << " "; // apple:1 apple:2 apple:4 banana:3}cout << endl;// 查找cout << "Count of apple: " << mm.count("apple") << endl; // 3auto range = mm.equal_range("apple");cout << "Values for apple: ";for (auto it = range.first; it != range.second; ++it) {cout << it->second << " "; // 1 2 4}cout << endl;// 删除mm.erase("apple"); // 删除所有 applecout << "After erase: ";for (const auto& p : mm) {cout << p.first << ":" << p.second << " "; // banana:3}cout << endl;return 0;
}

理解与扩充：

• 性能优化：equal_range 高效查找重复键；emplace 避免拷贝。
• 应用场景：multimap 适合一对多关系，如学生-课程映射。
• 底层细节：红黑树支持重复键，插入顺序决定相同键的遍历顺序。

---

十、unordered_set

1. 是什么结构，底层是什么？

• 结构：无序集合，元素唯一，无序存储。
• 底层实现：
  • 基于哈希表，通过哈希函数将元素映射到桶，冲突通过链表或红黑树（C++11 后）解决。
  • 哈希表特性：
    • 桶（bucket）：存储元素的数组，元素通过哈希函数分配。
    • 冲突处理：早期用链表，现代实现（如 GCC）在冲突过多时转为红黑树。
    • 负载因子（load factor）：元素数/桶数，超过阈值（默认 1.0）触发重哈希。
  • 性能特性：
    • 查找、插入、删除：平均 O(1)，最坏 O(n)（冲突严重）。
    • 遍历：O(n)。
  • 哈希函数：默认 std::hash<T>，可自定义。
• 扩充知识：
  • 重哈希：当负载因子超阈值，重新分配桶并重新映射元素，复杂度 O(n)。
  • 迭代器：前向迭代器，元素不可修改。
  • 内存开销：桶数组和冲突链表/树增加空间需求。
  • 性能依赖：哈希函数质量和负载因子影响性能。

2. 如何使用，支持哪些使用方法？

• 头文件：<unordered_set>
• 用途：存储唯一元素，适合快速查找、去重。
• 构造方式（扩充）：
  • 默认构造：unordered_set<int> us;
  • 初始列表：unordered_set<int> us = {1, 2, 3};
  • 范围构造：unordered_set<int> us(v.begin(), v.end());
  • 自定义哈希/比较器：unordered_set<string, MyHash, MyEqual> us;
• 常用方法（扩充）：
  • 插入：
    • insert(val)：插入元素。
    • insert(first, last)：插入范围。
    • emplace(args...)：构造插入。
  • 查找：
    • find(val)：返回迭代器。
    • count(val)：返回元素出现次数（0 或 1）。
  • 删除：
    • erase(val)：删除指定值。
    • erase(pos)：删除迭代器位置。
    • erase(first, last)：删除范围。
  • 大小：
    • size()：元素数量。
    • empty()：是否为空。
  • 哈希管理：
    • bucket_count()：桶数量。
    • load_factor()：当前负载因子。
    • max_load_factor(f)：设置最大负载因子。
    • rehash(n)：重新设置桶数。
    • reserve(n)：预分配空间。

code 示例（扩充）：

#include <iostream>
#include <unordered_set>
using namespace std;int main() {// 构造unordered_set<int> us = {1, 2, 3, 2};// 插入us.insert(4);us.emplace(5);cout << "us: ";for (auto x : us) {cout << x << " "; // 无序，如 1 2 3 4 5}cout << endl;// 查找if (us.find(2) != us.end()) {cout << "Found 2" << endl;}cout << "Count of 3: " << us.count(3) << endl; // 1// 删除us.erase(1);cout << "After erase: ";for (auto x : us) {cout << x << " "; // 2 3 4 5}cout << endl;// 哈希管理cout << "Bucket count: " << us.bucket_count() << endl;us.max_load_factor(0.5); // 降低负载因子us.rehash(20); // 设置桶数cout << "New bucket count: " << us.bucket_count() << endl;return 0;
}

理解与扩充：

• 性能优化：reserve 预分配桶数减少重哈希；自定义哈希函数提高分布均匀性。
• 应用场景：unordered_set 适合快速去重、成员检查，如词汇表、ID 集合。
• 底层细节：哈希表性能依赖哈希函数和冲突处理；现代实现用红黑树优化最坏情况。

---

十一、unordered_map

1. 是什么结构，底层是什么？

• 结构：无序键值对容器，键唯一，无序存储。
• 底层实现：
  • 基于哈希表，键通过哈希函数映射到桶，冲突通过链表或红黑树解决。
  • 性能特性：
    • 查找、插入、删除：平均 O(1)，最坏 O(n)。
    • 遍历：O(n)。
  • 哈希函数：默认 std::hash<Key>，可自定义。
• 扩充知识：
  • 重哈希：负载因子超阈值时重新分配桶，复杂度 O(n)。
  • 迭代器：前向迭代器，键不可修改。
  • 内存开销：桶和冲突结构增加空间需求。
  • 性能依赖：哈希函数质量关键。

2. 如何使用，支持哪些使用方法？

• 头文件：<unordered_map>
• 用途：存储键值对，适合快速查找的字典。
• 构造方式（扩充）：
  • 默认构造：unordered_map<string, int> um;
  • 初始列表：unordered_map<string, int> um = {{"a", 1}, {"b", 2}};
  • 范围构造：unordered_map<string, int> um(m.begin(), m.end());
  • 自定义哈希/比较器：unordered_map<string, int, MyHash, MyEqual> um;
• 常用方法（扩充）：
  • 插入：
    • um[key] = val：插入或更新。
    • insert(pair)：插入键值对。
    • insert(first, last)：插入范围。
    • emplace(args...)：构造插入。
    • insert_or_assign(key, val)（C++17）：插入或覆盖。
  • 查找：
    • find(key)：返回迭代器。
    • count(key)：返回键出现次数（0 或 1）。
    • at(key)：带边界检查访问。
  • 删除：
    • erase(key)：删除指定键。
    • erase(pos)：删除迭代器位置。
    • erase(first, last)：删除范围。
  • 大小：
    • size()：元素数量。
    • empty()：是否为空。
  • 哈希管理：
    • bucket_count()：桶数量。
    • load_factor()：负载因子。
    • max_load_factor(f)：设置最大负载因子。
    • rehash(n)：重新设置桶数。
    • reserve(n)：预分配空间。

code 示例（扩充）：

#include <iostream>
#include <unordered_map>
using namespace std;int main() {// 构造unordered_map<string, int> um = {{"apple", 5}, {"banana", 3}};// 插入um["orange"] = 2;um.insert({"grape", 4});um.emplace("pear", 1);um.insert_or_assign("apple", 6);// 遍历cout << "um: ";for (const auto& p : um) {cout << p.first << ":" << p.second << " "; // 无序}cout << endl;// 查找if (um.find("apple") != um.end()) {cout << "Found apple: " << um.at("apple") << endl; // 6}cout << "Count of banana: " << um.count("banana") << endl; // 1// 删除um.erase("banana");cout << "After erase: ";for (const auto& p : um) {cout << p.first << ":" << p.second << " ";}cout << endl;// 哈希管理cout << "Bucket count: " << um.bucket_count() << endl;um.reserve(100); // 预分配cout << "New bucket count: " << um.bucket_count() << endl;return 0;
}

理解与扩充：

• 性能优化：reserve 减少重哈希；emplace 避免拷贝。
• 应用场景：unordered_map 适合快速键值映射，如缓存、计数器。
• 底层细节：哈希表性能依赖哈希函数；现代实现优化冲突处理。

---

STL 容器总结与理解

STL 容器提供了多样化的数据管理工具，针对不同场景优化：

• 序列容器：
  • vector：动态数组，适合随机访问，尾部操作高效。
  • list：双向链表，适合频繁插入/删除，迭代器稳定。
• 关联容器：
  • map/set：红黑树，有序，适合排序和查找。
  • multimap/multiset：支持重复键/元素，适合多值映射。
• 无序关联容器：
  • unordered_map/unordered_set：哈希表，高效查找，适合无序场景。
• 容器适配器：
  • stack/queue：简单 LIFO/FIFO 操作，适合特定模式。
  • priority_queue：堆实现，适合优先级调度。

选择建议：

• 随机访问：vector（O(1) 访问）优于 deque（分块存储）。

• 频繁插入/删除：list（O(1) 操作，迭代器稳定）优于 vector。

• 有序键值：map（红黑树，O(log n)）优于 unordered_map（无序）。

• 高效查找：unordered_map/unordered_set（O(1) 平均）优于 map/set。

• 优先级：priority_queue（堆，O(log n) 调整）优于手动维护。

• 简单栈/队列：stack/queue 提供简洁接口，优于直接使用 vector/list。

• 内存优化：使用 reserve（vector, unordered_ 容器）或自定义分配器。

• 性能分析：根据数据量和操作频率选择容器，如小数据量可用 vector，频繁查找用 unordered_map。

• 算法结合：STL 算法（如 std::sort, std::find）与容器结合，提升效率。

• 线程安全：STL 容器非线程安全，多线程场景需加锁或使用并发容器。

---