C++中容器的概念

顺序容器

顺序容器通过元素的‌插入顺序‌维护数据，不自动按值排序，具体包括：

• ‌array‌：固定大小的数组，支持快速随机访问，内存连续‌45 ‌vector‌：动态数组，支持尾部高效插入/删除，内存连续‌

• ‌deque‌：双端队列，支持头尾高效插入/删除，内存分段连续‌24 ‌list‌：双向链表，支持任意位置高效插入/删除，内存非连续‌

• forward_list‌：单向链表，内存占用更小，但仅支持单向遍历‌

• string‌：专用于字符串的动态数组，与vector类似但提供字符串操作接口‌

关联式容器容器

• ‌set‌：唯一键集合，元素即键，不可重复‌
• multiset‌：允许重复键的集合‌
• map‌：键值对映射，键唯一，每个键对应一个值‌
• ‌multimap‌：允许重复键的映射‌

一、有序关联容器

基于红黑树实现，元素按‌键值自动排序‌（默认升序），支持高效的范围查询和有序遍历‌12。
‌包含容器：‌

• ‌set‌：唯一键集合，键不可重复‌ ‌
• map‌：键值对映射，键唯一，支持键到值的映射‌ ‌
• multiset‌：允许重复键的集合‌
• multimap‌：允许重复键的键值对映射‌

‌特性：‌

‌键值要求‌：键类型需支持比较运算（如 < 运算符）‌。
‌查找复杂度‌：基于红黑树的平衡性，查找/插入/删除操作的时间复杂度为 ‌O(log n)‌‌。
‌适用场景‌：需按键有序遍历或范围查询（如区间检索）‌。

二、无序关联容器

基于哈希表实现，元素‌无固定顺序‌，依赖哈希函数确定存储位置，提供平均 O(1) 复杂度的查找效率‌。
‌包含容器：‌

• ‌unordered_set‌：唯一键哈希集合‌ ‌
• unordered_map‌：键值对哈希映射，键唯一‌
• unordered_multiset‌：允许重复键的哈希集合‌ ‌
• unordered_multimap‌：允许重复键的哈希映射‌

容器操作方法

一、顺序容器（如 vector、list、deque 等）

顺序容器通过插入顺序维护元素，常用操作函数如下：

‌插入操作‌
push_back(val)：在尾部插入元素（适用 vector、deque、list）‌24
emplace_back(args…)：尾部构造元素（避免复制，效率更高）‌24
insert(iter, val)：在迭代器位置插入元素（适用所有顺序容器）‌26
‌删除操作‌
pop_back()：删除尾部元素‌24
erase(iter)：删除迭代器指向的元素‌26
‌访问操作‌
operator[] 或 at(n)：随机访问第 n 个元素（适用 vector、deque）‌24
‌容量管理‌
resize(n)：调整容器大小‌26
reserve(n)：预分配内存（适用 vector）‌46

二、有序关联容器（如 set、map、multiset、multimap）

基于红黑树实现，支持按键排序，常用函数如下：

‌插入操作‌
insert(val)：插入元素（返回插入状态的 pair<iter, bool>）
emplace(args…)：直接构造元素‌
‌删除操作‌
erase(key)：删除所有匹配键的元素，返回删除数量‌
erase(iter)：删除迭代器指向的元素‌
‌查找操作‌
find(key)：返回指向首个匹配键的迭代器（未找到则返回 end()）
count(key)：统计匹配键的元素数量‌
lower_bound(key) 和 upper_bound(key)：返回有序范围边界的迭代器‌
‌访问操作‌
operator[]（仅 map）：通过键访问值（若键不存在则插入默认值）
at(key)（仅 map）：通过键访问值（键不存在时抛出异常）‌

三、无序关联容器（如 unordered_set、unordered_map 等）

基于哈希表实现，元素无固定顺序，常用函数如下：

‌插入与删除‌
insert(val) 或 emplace(args…)：插入元素‌
erase(key)：删除所有匹配键的元素‌
‌查找操作‌
find(key)：返回指向首个匹配键的迭代器‌
count(key)：统计匹配键的元素数量‌
‌哈希桶管理‌
bucket_count()：返回哈希桶数量‌
bucket(key)：返回键对应的哈希桶索引‌
load_factor()：返回当前负载因子（每个桶的平均元素数）
rehash(n)：重新调整哈希桶数量以优化性能‌