STL容器分类总结

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

	1序列容器:vector、deque、list、forward_list、array、string
	2关联容器：set、multisat、map、multimap
	3无序关联容器：unordered_set、unordered_multiset、unordered_map、unordered_multimap
	4容器适配器：stack、queue、priority_queue

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

一、序列容器（Sequence Containers）

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

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

***序列容器选择指南

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（返回队列中元素的数量）。此外，可以通过指定比较函数来改变元素的优先级顺序。

适用场景：需要优先级队列的场景，如任务优先级调度。

五、如何选择容器？

六、示例代码

#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; // 输出：20
 
    queue<int> q;
    q.push(100);
    q.push(200);
    cout << "Queue front: " << q.front() << endl; // 输出：100
 
    priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(20);
    cout << "Priority queue top: " << pq.top() << endl; // 输出：30
 
    return 0;
}

七、总结

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

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

。