STL容器分类总结

在C++的STL（标准模板库）中，容器是用于存储和管理数据的核心组件。STL提供了多种容器，根据其底层实现和特性，可以分为四大类。

	1序列容器:vector、deque、list、forward_list、array、string2关联容器：set、multisat、map、multimap3无序关联容器：unordered_set、unordered_multiset、unordered_map、unordered_multimap4容器适配器：stack、queue、priority_queue

以下是STL容器的详细分类和介绍：

一、序列容器（Sequence Containers）

序列容器是C++标准模板库(STL)中用于存储线性数据集合的容器类型，它们按照严格的线性顺序组织元素，支持通过位置（索引或迭代器）访问元素。以下是C++中主要的序列容器及其核心特性：
序列容器按元素插入的顺序存储数据，支持随机访问或顺序访问。

***序列容器核心操作对比

操作	vector	deque	list	forward_list	array
随机访问	O(1)	O(1)	不支持O(n)	不支持	O(1)
尾部插入/删除	O(1)	O(1)	O(1)	不支持	不支持
头部插入/删除	O(n)	O(1)	O(1)	O(1)	不支持
中间插入/删除	O(n)	O(n)	O(1)	O(n)	不支持
内存连续性	是	部分	否	否	是
大小动态性	是	是	是	是	否

---

***序列容器选择指南

1需要随机访问：

• 优先选择vector（除非需要频繁头部操作）
• 如果需要频繁头部操作，选择deque

2需要频繁中间插入/删除：

• 选择list或forward_list（根据是否需要反向遍历）

3需要固定大小数组：

• 选择array（比内置数组更安全）

4内存敏感场景：

• 考虑forward_list（比list更节省内存）
• 或预先分配足够空间的vector（避免多次扩容）

5需要迭代器稳定性：

• list和forward_list的迭代器在插入/删除时不会失效（除非指向被删除的元素）
• 其他容器的迭代器在插入/删除时可能失效

---

*性能优化建议

1vector预分配：

std::vector<int> v;
v.reserve(1000); // 预先分配空间，避免多次扩容

2使用emplace代替push：

std::vector<std::pair<int, std::string>> v;
v.emplace_back(1, "hello"); // 原地构造，避免临时对象

3避免不必要的拷贝：

	使用引用或移动语义传递容器

4考虑迭代器稳定性需求：

	如果需要频繁插入/删除且要保持迭代器有效，选择链表类容器

---

1. std::vector（动态数组）

底层实现：连续内存，动态扩容（通常翻倍）。
特点：1动态增长的连续内存数组2支持快速随机访问（O(1)）3尾部插入/删除高效（平均O(1)）4中间插入/删除低效（O(n)）适用场景：1需要频繁随机访问2尾部操作多于中间操作3大小动态变化但不需要频繁中间插入

#include <vector>
std::vector<int> v = {1, 2, 3}; // 初始化
v.push_back(4);                 // 尾部插入
int x = v[1];                   // 随机访问

2. std::deque（双端队列）

底层实现：分段连续内存，类似多个vector的组合。
特点：1分段连续内存结构2支持头尾高效插入/删除（O(1)）-----3支持随机访问（O(1)）4中间操作效率低于vector-----
适用场景：需要频繁在头部和尾部操作需要随机访问但中间操作较少

#include <deque>
std::deque<int> d = {1, 2, 3};
d.push_front(0);  // 头部插入
d.push_back(4);   // 尾部插入

3. std::list（双向链表）

底层实现：双向链表，节点分散在内存中。
特点：1双向链表，节点分散在内存中。2支持高效的插入/删除操作（O(1)），但需要遍历到指定位置（O(n)）。3不支持随机访问。4内存不连续，适合频繁插入/删除的场景。5额外内存开销（每个节点存储前后指针）适用场景：需要频繁插入/删除不关心随机访问的场景，如链表操作。

#include <list>
std::list<int> l = {1, 2, 3};
auto it = l.begin();
++it; // 移动到第二个元素
l.insert(it, 10); // 在第二个位置插入

4. std::forward_list（单向链表，C++11）

底层实现：单向链表，节点分散在内存中。
特点：1仅支持单向遍历，比list更节省内存。2插入/删除操作高效（O(1)），但需要遍历到指定位置（O(n)）。3不支持随机访问。4没有size()成员函数（需要遍历计算）---适用场景：1需要单向链表特性2内存敏感且不需要反向遍历

#include <forward_list>
std::forward_list<int> fl = {1, 2, 3};
fl.push_front(0); // 只能在头部插入

5. std::array（固定大小数组，C++11）

底层实现：连续内存，大小在编译时确定。
特点：1固定大小的连续内存数组2编译时确定大小3支持随机访问（O(1)）4不支持动态增长适用场景：1需要固定大小数组2需要STL容器的接口和安全性如替代普通数组。

#include <array>
std::array<int, 3> arr = {1, 2, 3};
int x = arr[1]; // 随机访问

6. string（字符串容器）

底层实现：本质上是字符的vector，支持动态扩容。
特点：1支持丰富的字符串操作函数（如拼接、查找、替换等）。2动态扩容，适合需要频繁修改字符串的场景。适用场景：字符串处理，如文本操作。

二、关联容器（Associative Containers）

关联容器通过键（key）存储和检索元素，元素默认按升序排列。
在C++中，关联容器是一种用于存储和管理键值对（或仅键）数据的容器，其主要特点是能够通过键快速查找值。关联容器与序列容器不同，它们不保证元素的存储顺序（有序关联容器除外），而是根据键的排序方式或哈希值来组织数据。以下是C++中关联容器的核心概念和类型

*关联容器的主要类型

1有序关联容器：

std::map：存储唯一的键值对，按键自动排序。
std::multimap：存储键值对，允许键重复，按键自动排序。
std::set：存储唯一的键（无值），按键自动排序。
std::multiset：存储键，允许键重复，按键自动排序。

这些容器通常基于平衡二叉搜索树（如红黑树）实现，查找、插入和删除操作的时间复杂度为O(log n)。

2无序关联容器（C++11引入）：

std::unordered_map：存储唯一的键值对，不保证顺序，使用哈希表实现。
std::unordered_multimap：存储键值对，允许键重复，不保证顺序，使用哈希表实现。
std::unordered_set：存储唯一的键，不保证顺序，使用哈希表实现。
std::unordered_multiset：存储键，允许键重复，不保证顺序，使用哈希表实现。

无序关联容器的查找、插入和删除操作的平均时间复杂度为O(1)，但在最坏情况下可能退化为O(n)。

**关联容器的核心特性

1键值对存储：

	map和multimap存储键值对，通过键访问值。set和multiset仅存储键，键本身即标识元素。

2自动排序（有序关联容器）：

	元素按键的顺序自动排序，默认使用<运算符进行比较。可自定义比较函数或函数对象来改变排序规则。

3高效查找：

	通过键快速查找元素，时间复杂度通常为O(log n)（有序）或O(1)（无序）。

4不允许键重复（除multimap和multiset外）：

	插入重复键时，map和set会忽略新元素，而multimap和multiset会保留所有重复键。

1. set（唯一键集合）

底层实现：红黑树（平衡二叉搜索树）。
特点：1键唯一，元素有序。2插入、删除、查找的时间复杂度为O(log n)。适用场景：需要唯一键且有序的场景，如去重和排序。---

2. multiset（可重复键集合）

底层实现：红黑树。
特点：1键可重复，元素有序。2插入、删除、查找的时间复杂度为O(log n)。适用场景：需要可重复键且有序的场景，如统计词频。---

3. map（唯一键值对映射）

底层实现：红黑树。
特点：1键唯一，键值对有序。2插入、删除、查找的时间复杂度为O(log n)。适用场景：需要唯一键且有序的键值对场景，如字典。----

4. multimap（可重复键值对映射）

底层实现：红黑树。
特点：1键可重复，键值对有序。2插入、删除、查找的时间复杂度为O(log n)。适用场景：需要可重复键且有序的键值对场景，如多值映射。-----

关联容器的操作示例

#include <iostream>
#include <map>
#include <set>
#include <unordered_map>int main() {// 有序关联容器示例std::map<std::string, int> ages;ages["Alice"] = 30;ages["Bob"] = 25;for (const auto& entry : ages) {std::cout << entry.first << ": " << entry.second << std::endl;}std::set<int> numbers = {3, 1, 4, 1, 5};for (int num : numbers) {std::cout << num << " "; // 输出: 1 3 4 5（自动去重并排序）}// 无序关联容器示例std::unordered_map<std::string, int> scores;scores["Alice"] = 90;scores["Bob"] = 85;for (const auto& entry : scores) {std::cout << entry.first << ": " << entry.second << std::endl;}return 0;
}

三、无序关联容器（Unordered Associative Containers）

无序关联容器通过哈希表实现，元素无序，但插入、删除和查找的平均时间复杂度为O(1)。

1. unordered_set（唯一键集合）

底层实现：哈希表。
特点：1键唯一，元素无序。2插入、删除、查找的平均时间复杂度为O(1)，最坏为O(n)。适用场景：需要快速查找且不关心顺序的场景，如哈希集合

2. unordered_multiset（可重复键集合）

底层实现：哈希表。
特点：1键可重复，元素无序。2插入、删除、查找的平均时间复杂度为O(1)，最坏为O(n)。适用场景：需要快速查找且键可重复的场景，如哈希多值集合。

3. unordered_map（唯一键值对映射）

底层实现：哈希表。
特点：1键唯一，键值对无序。2插入、删除、查找的平均时间复杂度为O(1)，最坏为O(n)。适用场景：需要快速查找且不关心键顺序的键值对场景，如哈希字典。

4. unordered_multimap（可重复键值对映射）

底层实现：哈希表。
特点：1键可重复，键值对无序。2插入、删除、查找的平均时间复杂度为O(1)，最坏为O(n)。适用场景：需要快速查找且键可重复的键值对场景，如哈希多值映射。

无序关联容器的操作示例

#include <iostream>
#include <unordered_map>
#include <unordered_set>int main() {// unordered_map示例std::unordered_map<std::string, int> ages;ages["Alice"] = 30;ages["Bob"] = 25;ages["Charlie"] = 35;for (const auto& entry : ages) {std::cout << entry.first << ": " << entry.second << std::endl;}// unordered_set示例std::unordered_set<int> numbers = {3, 1, 4, 1, 5};for (int num : numbers) {std::cout << num << " "; // 输出可能是: 3 1 4 5（顺序不确定）}// unordered_multimap示例std::unordered_multimap<std::string, int> scores;scores.insert({"Alice", 90});scores.insert({"Bob", 85});scores.insert({"Alice", 95}); // 允许重复键auto range = scores.equal_range("Alice");for (auto it = range.first; it != range.second; ++it) {std::cout << it->first << ": " << it->second << std::endl;}return 0;
}

四、容器适配器（Container Adapters）

容器适配器是基于其他容器实现的，提供了特定的接口和行为。
在C++中，容器适配器（Container Adapter）是一种特殊的容器类型，它通过封装现有的容器并限制其接口，提供特定数据结构的特性（如栈、队列、优先队列等）。以下是容器适配器的核心概念：

1、基本特性

封装与限制：容器适配器不是独立的容器，而是基于其他容器（如deque、vector、list）实现的。它们通过封装这些基础容器，并仅暴露符合目标数据结构特性的操作，从而限制用户只能按特定方式操作数据。

特定数据结构行为：容器适配器提供了栈、队列、优先队列等经典数据结构的操作接口，使得用户可以直接使用这些数据结构，而无需手动实现。

*应用场景：

栈：适用于需要后进先出操作的场景，如函数调用栈、括号匹配、表达式求值（逆波兰式）等。
队列：适用于需要先进先出操作的场景，如任务调度、BFS广度优先搜索、缓冲池等。
优先队列：适用于需要按优先级处理元素的场景，如任务优先级调度、Dijkstra最短路径算法、Top K问题等。

1. stack（栈）

底层实现：默认基于deque，也可基于vector或list。
特点：1后进先出（LIFO）结构。2支持操作：push（插入元素到栈顶）、pop（删除栈顶元素）、top（返回栈顶元素）、empty（检查栈是否为空）、size（返回栈中元素的数量）。适用场景：需要栈行为的场景，如函数调用栈。

2. queue（队列）

底层实现：默认基于deque，也可基于list。注意，vector不能作为queue的底层容器，因为它不支持在头部进行高效的插入和删除操作。
特点：1先进先出（FIFO）结构。2支持操作：push（插入元素到队尾）、pop（删除队头元素）、front（返回队头元素）、back（返回队尾元素）、empty（检查队列是否为空）、size（返回队列中元素的数量）。适用场景：需要队列行为的场景，如任务调度。

3. priority_queue（优先级队列）

底层实现：vector，并使用make_heap、push_heap和pop_heap来维护堆结构。
特点：1元素按优先级排序，默认最大值优先。2支持操作：push（插入元素并维护优先级顺序）、pop（删除优先级最高的元素）、top（返回优先级最高的元素）、empty（检查队列是否为空）、size（返回队列中元素的数量）。此外，可以通过指定比较函数来改变元素的优先级顺序。适用场景：需要优先级队列的场景，如任务优先级调度。

五、如何选择容器？

场景需求	推荐容器	说明
需要随机访问	vector、deque、array	vector适合频繁访问，deque适合头部/尾部操作，array适合固定大小。
需要频繁插入/删除	list、forward_list	list适合双向操作，forward_list适合单向操作。
需要唯一键且有序	set、map	键唯一且有序，适合字典或集合操作。
需要可重复键且有序	multiset、multimap	键可重复且有序，适合多值映射。
需要快速查找且不关心顺序	unordered_set、unordered_map	平均O(1)时间复杂度，适合哈希操作。
需要栈行为	stack	基于其他容器实现，默认deque。
需要队列行为	queue	基于其他容器实现，默认deque。
需要优先级队列	priority_queue	基于堆实现，默认最大值优先。

六、示例代码

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
using namespace std;int main() {// 序列容器示例vector<int> vec = {1, 2, 3};list<string> lst = {"a", "b", "c"};// 关联容器示例map<string, int> m = {{"apple", 10}, {"banana", 20}};m["orange"] = 30;// 无序关联容器示例unordered_map<int, string> um = {{1, "one"}, {2, "two"}};// 容器适配器示例stack<int> stk;stk.push(10);stk.push(20);cout << "Stack top: " << stk.top() << endl; // 输出：20queue<int> q;q.push(100);q.push(200);cout << "Queue front: " << q.front() << endl; // 输出：100priority_queue<int> pq;pq.push(30);pq.push(10);pq.push(20);cout << "Priority queue top: " << pq.top() << endl; // 输出：30return 0;
}

七、总结

序列容器：适合需要按顺序存储和访问数据的场景。
关联容器：适合需要通过键快速查找数据的场景，且键有序。
无序关联容器：适合需要通过键快速查找数据的场景，但不关心顺序。
容器适配器：适合需要特定行为（如栈、队列、优先级队列）的场景。

通过合理选择容器，可以显著提高代码的效率和可读性。根据具体需求（如是否需要随机访问、是否需要有序、是否需要快速查找等）选择合适的容器是关键

。