C++ 标准库容器详解：特性、用法与场景选型

容器是 C++ 标准库（STL）的核心组件，用于存储和管理数据。不同容器因底层实现不同，在性能、功能和适用场景上差异显著。本文系统梳理vector、list、set、map等常用容器，从核心特性、API 用法到场景选型进行全方位解析，帮助开发者精准选择合适的容器。

一、容器分类与核心差异概览

C++ 容器按功能可分为序列式容器（侧重元素顺序）和关联式容器（侧重元素查找），核心差异如下表：

二、序列式容器详解

1. vector：动态数组（最常用序列容器）

核心特性

• 底层实现：基于动态数组，内存连续（同数组），但支持自动扩容。
• 关键优势：
  • 支持随机访问（通过[]或at()），时间复杂度 O (1)；
  • 尾部插入 / 删除（push_back/pop_back）效率极高，O (1)；
  • 内存局部性好，缓存命中率高（因内存连续）。
• 局限性：
  • 中间 / 头部插入 / 删除需移动大量元素，O (n)；
  • 扩容时可能触发内存重分配（通常扩容为原容量 2 倍），导致性能波动。

常用 API 与示例

#include <vector>
#include <iostream>
using namespace std;int main() {// 1. 初始化（三种常用方式）vector<int> vec1; // 空容器vector<int> vec2(5, 10); // 5个元素，均为10vector<int> vec3 = {1, 2, 3, 4, 5}; // 初始化列表// 2. 插入元素vec1.push_back(6); // 尾部插入（O(1)）vec1.insert(vec1.begin() + 1, 8); // 在索引1处插入（O(n)，需移动元素）// 3. 访问元素（两种方式）cout << vec3[2] << endl; // 下标访问（无越界检查，快）cout << vec3.at(3) << endl; // at()访问（有越界检查，安全）cout << "首元素：" << vec3.front() << "，尾元素：" << vec3.back() << endl;// 4. 遍历（迭代器/范围for）for (auto it = vec3.begin(); it != vec3.end(); ++it) {cout << *it << " ";}// 范围for更简洁（C++11+）for (int num : vec3) { cout << num << " "; }// 5. 修改与删除vec3[0] = 100; // 直接修改vec1.pop_back(); // 删除尾部元素（O(1)）vec3.erase(vec3.begin() + 2); // 删除索引2处元素（O(n)）// 6. 容量管理（关键！）cout << "当前大小：" << vec2.size() // 元素个数<< "，容量：" << vec2.capacity() << endl; // 已分配内存可容纳的元素数vec2.reserve(10); // 预分配容量（避免频繁扩容）vec2.resize(3); // 调整大小（多余元素被截断，新增元素为默认值）vec1.clear(); // 清空元素（size=0，但capacity不变）return 0;
}

典型场景

• 需频繁随机访问元素（如存储数组、矩阵、日志数据）；
• 元素主要在尾部增删（如批量数据收集、缓冲区）；
• 需与 C 语言数组兼容（因内存连续，可通过data()获取原始指针）。

2. list：双向链表（高效增删的序列容器）

核心特性

• 底层实现：双向链表，每个节点包含数据域和前后指针，内存不连续。
• 关键优势：
  • 任意位置（已知迭代器）插入 / 删除效率极高，O (1)（无需移动元素，仅修改指针）；
  • 无扩容开销（节点动态分配），内存使用更灵活。
• 局限性：
  • 不支持随机访问（访问第 n 个元素需从头遍历），时间复杂度 O (n)；
  • 内存开销大（每个节点额外存储两个指针）；
  • 缓存命中率低（内存不连续）。

常用 API 与示例

#include <list>
#include <iostream>int main() {// 1. 初始化list<int> list1;list<int> list2(4, 20); // 4个元素，均为20list<int> list3 = {10, 20, 30, 40};// 2. 插入元素（头部/尾部/中间）list1.push_back(5); // 尾部插入（O(1)）list1.push_front(3); // 头部插入（O(1)）auto it = list3.begin(); ++it; // 指向第二个元素（20）list3.insert(it, 25); // 在20和30之间插入25（O(1)，已知位置）// 3. 访问元素（仅支持首尾直接访问）cout << "首元素：" << list3.front() << "，尾元素：" << list3.back() << endl;// 访问中间元素需遍历it = list3.begin();advance(it, 2); // 移动迭代器到第3个元素（25）cout << "第3个元素：" << *it << endl;// 4. 遍历（仅迭代器/范围for）for (int num : list3) { cout << num << " "; }// 5. 特殊操作（链表特有）list3.reverse(); // 反转链表（O(n)，仅修改指针）list3.sort(); // 排序（O(n log n)，链表自带排序，无需转换为vector）// 6. 删除元素list1.pop_back(); // 尾部删除（O(1)）list3.pop_front(); // 头部删除（O(1)）it = list3.begin(); ++it;list3.erase(it); // 删除指定位置元素（O(1)，已知位置）return 0;
}

典型场景

• 频繁在中间位置增删元素（如实现链表、队列、栈的变种）；
• 数据量不确定，且需避免扩容开销（如实时数据采集，元素动态增减）；
• 需要高效拆分 / 合并链表（splice()方法，O (1) 实现链表拼接）。

三、关联式容器详解

1. set与unordered_set：集合（元素去重与查找）

核心特性对比

常用 API 与示例（以set为例）

#include <set>
#include <iostream>
#include <functional> // 用于自定义排序
using namespace std;
int main() {// 1. 初始化（默认升序）set<int> set1;// 自定义排序（降序）set<int,greater<int>> set2;// 2. 插入元素（自动去重）set1.insert(3);set1.insert(1);set1.insert(2);set1.insert(2); // 重复元素，插入无效set2.insert({5, 3, 7}); // 初始化列表插入// 3. 查找元素（核心操作）auto it1 = set1.find(2); // 查找值为2的元素if (it1 != set1.end()) {cout << "找到元素：" << *it1 << endl;}// 判断元素是否存在（count()返回0或1）if (set1.count(3)) { cout << "元素3存在" << endl; }// 4. 遍历（有序性体现）cout << "set1（升序）：";for (int num : set1) { cout << num << " "; } // 输出：1 2 3cout << "\nset2（降序）：";for (int num : set2) { cout << num << " "; } // 输出：7 5 3// 5. 删除元素set1.erase(1); // 按值删除（O(log n)）set2.erase(set2.begin()); // 按迭代器删除（O(1)）return 0;
}

典型场景

• set：需去重且保持有序（如排行榜、区间统计，支持lower_bound/upper_bound范围查询）；
• unordered_set：仅需去重，追求极致查找效率（如缓存校验、数据去重验证）。

2. map与unordered_map：键值对（关联查询）

核心特性对比

常用 API 与示例（以unordered_map为例）

cpp

运行

#include <unordered_map>
#include <iostream>int main() {// 1. 初始化（键为int，值为string）unordered_map<int, string> umap;// 2. 插入键值对（三种方式）umap.insert({1, "one"}); // 插入pair（重复key无效）umap[2] = "two"; // []运算符（重复key会覆盖）umap.emplace(3, "three"); // 直接构造（效率更高）// 3. 访问value（两种方式）cout << umap[2] <<endl; // []访问（无key则插入默认值）try {cout << umap.at(3) << endl; // at()访问（无key抛异常，更安全）} catch (const out_of_range& e) {cout << "key不存在" << endl;}// 4. 查找key（核心操作）auto it = umap.find(1); // 查找key=1if (it != umap.end()) {cout << "key：" << it->first << "，value：" << it->second << endl;}// 5. 遍历for (const auto& pair : umap) {cout << pair.first << " → " << pair.second << " ";}// 6. 删除元素umap.erase(2); // 按key删除it = umap.find(3);if (it != umap.end()) {umap.erase(it); // 按迭代器删除}return 0;
}

典型场景

• map：需按 key 排序的键值对（如按 ID 排序的用户信息、区间查询配置）；
• unordered_map：高频键值查询（如数据库索引、缓存映射，优先考虑查找速度）。

四、容器选型决策指南

选择容器时需结合操作类型（增删查为主？随机访问？）、数据特性（是否有序？是否重复？）和性能需求（时间 / 内存优先），决策流程如下：

1. 是否需要键值对关联？

   • 是 → 选map（有序）或unordered_map（无序）；
   • 否 → 进入下一步。

2. 是否需要去重？

   • 是 → 选set（有序）或unordered_set（无序）；
   • 否 → 进入下一步（序列容器）。

3. 序列容器核心需求？

   • 频繁随机访问 → vector；
   • 频繁中间增删 → list；
   • 头尾增删频繁且需随机访问 → deque（双端队列，未详细展开）。

五、容器算法

C++ 标准库的 <algorithm> 头文件提供了大量实用算法，涵盖排序、查找、修改、数值计算等场景。以下是常用算法的分类总结及例程：

5.1 排序与顺序相关算法

1. sort - 快速排序（不稳定）

对范围元素排序，平均复杂度 O (n log n)

#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> v = {3, 1, 4, 1, 5};std::sort(v.begin(), v.end()); // 升序// 输出：1 1 3 4 5// 自定义降序std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });// 输出：5 4 3 1 1return 0;
}

2. stable_sort - 稳定排序

保持相等元素的原始相对顺序

std::vector<std::pair<int, int>> v = {{2,1}, {1,2}, {2,3}};
std::stable_sort(v.begin(), v.end()); 
// 结果：{1,2}, {2,1}, {2,3}（两个2的相对顺序不变）

3. partial_sort - 部分排序

只保证前 k 个元素有序（最小的 k 个）

std::vector<int> v = {5, 3, 1, 4, 2};
std::partial_sort(v.begin(), v.begin()+3, v.end());
// 结果：1 2 3 5 4（前3个为最小且有序）

4. nth_element - 定位第 n 大元素

使第 n 个元素处于排序后的正确位置

std::vector<int> v = {5, 3, 1, 4, 2};
std::nth_element(v.begin(), v.begin()+2, v.end());
// 结果：2 1 3 5 4（3是第3小元素，左侧≤3，右侧≥3）

5.2  查找算法

1. find - 查找元素

返回首个匹配元素的迭代器

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = std::find(v.begin(), v.end(), 3);
if (it != v.end()) {std::cout << "找到元素：" << *it; // 输出：3
}

2. find_if - 条件查找

通过谓词查找元素

// 查找第一个偶数
auto it = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

3. binary_search - 二分查找

在已排序范围中查找（返回 bool）

std::vector<int> v = {1, 3, 5, 7};
bool exists = std::binary_search(v.begin(), v.end(), 5); // true

4. lower_bound / upper_bound

• lower_bound：返回首个 ≥ 目标值的迭代器
• upper_bound：返回首个 > 目标值的迭代器

std::vector<int> v = {1, 3, 3, 5};
auto lb = std::lower_bound(v.begin(), v.end(), 3); // 指向第一个3
auto ub = std::upper_bound(v.begin(), v.end(), 3); // 指向5
int count = ub - lb; // 3的个数：2

5.3 容器修改算法

1. copy - 复制元素

std::vector<int> src = {1, 2, 3};
std::vector<int> dest(3);
std::copy(src.begin(), src.end(), dest.begin()); // dest = {1,2,3}

2. swap - 交换元素

int a = 1, b = 2;
std::swap(a, b); // a=2, b=1std::vector<int> v1 = {1,2}, v2 = {3,4};
std::swap(v1, v2); // 交换整个容器

3. reverse - 反转范围

std::vector<int> v = {1, 2, 3};
std::reverse(v.begin(), v.end()); // {3,2,1}

4. remove - 移除元素（逻辑删除）

std::vector<int> v = {1, 2, 3, 2, 4};
// 逻辑删除所有2（返回新结尾迭代器）
auto last = std::remove(v.begin(), v.end(), 2);
v.erase(last, v.end()); // 物理删除，结果：{1,3,4}

5. unique - 移除连续重复元素

std::vector<int> v = {1, 2, 2, 3, 3, 3};
std::sort(v.begin(), v.end()); // 先排序
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end()); // 结果：{1,2,3}

5.4 数值与集合算法

1. accumulate - 累加（需 <numeric> 头文件）

#include <numeric>
std::vector<int> v = {1, 2, 3, 4};
int sum = std::accumulate(v.begin(), v.end(), 0); // 0+1+2+3+4=10// 计算乘积
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());

2. count / count_if - 计数

std::vector<int> v = {1, 2, 2, 3};
int cnt = std::count(v.begin(), v.end(), 2); // 2的个数：2// 计数偶数
int even_cnt = std::count_if(v.begin(), v.end(), [](int x) { return x%2==0; });

3. min_element / max_element - 查找最值

std::vector<int> v = {3, 1, 4};
auto min_it = std::min_element(v.begin(), v.end()); // 指向1
auto max_it = std::max_element(v.begin(), v.end()); // 指向4

4. set_intersection - 求交集（需已排序）

std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> res;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(res));
// res = {3,4}

5.5  编程练习

#include <algorithm>
#include <vector>
#include <iostream>
#include <numeric>  // 用于accumulateusing namespace std;int main() {// 一、排序与顺序相关算法{// 1. sort - 快速排序（不稳定）vector<int> v1 = {3, 1, 4, 1, 5};sort(v1.begin(), v1.end());  // 升序cout << "sort升序: ";for (int num : v1) cout << num << " ";  // 1 1 3 4 5cout << endl;// 自定义降序sort(v1.begin(), v1.end(), [](int a, int b) { return a > b; });cout << "sort降序: ";for (int num : v1) cout << num << " ";  // 5 4 3 1 1cout << endl;// 2. stable_sort - 稳定排序（保留相等元素相对顺序）vector<pair<int, int>> v2 = {{2,1}, {1,2}, {2,3}};stable_sort(v2.begin(), v2.end());cout << "stable_sort结果: ";for (auto p : v2) cout << "{" << p.first << "," << p.second << "} ";  // {1,2} {2,1} {2,3}cout << endl;// 3. partial_sort - 部分排序（前k个元素有序）vector<int> v3 = {5, 3, 1, 4, 2};partial_sort(v3.begin(), v3.begin()+3, v3.end());cout << "partial_sort前3个: ";for (int num : v3) cout << num << " ";  // 1 2 3 5 4cout << endl;// 4. nth_element - 定位第n个元素vector<int> v4 = {5, 3, 1, 4, 2};nth_element(v4.begin(), v4.begin()+2, v4.end());  // 第3小元素cout << "nth_element结果: ";for (int num : v4) cout << num << " ";  // 2 1 3 5 4（3在正确位置）cout << endl;}// 二、查找算法{vector<int> v = {1, 2, 3, 4, 5};// 1. find - 查找元素auto it1 = find(v.begin(), v.end(), 3);if (it1 != v.end()) cout << "find找到: " << *it1 << endl;  // 3// 2. find_if - 条件查找auto it2 = find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });if (it2 != v.end()) cout << "find_if找到首个偶数: " << *it2 << endl;  // 2// 3. binary_search - 二分查找（需已排序）bool exists = binary_search(v.begin(), v.end(), 5);cout << "binary_search查找5: " << (exists ? "存在" : "不存在") << endl;  // 存在// 4. lower_bound/upper_boundvector<int> v_sorted = {1, 3, 3, 5};auto lb = lower_bound(v_sorted.begin(), v_sorted.end(), 3);  // 首个>=3auto ub = upper_bound(v_sorted.begin(), v_sorted.end(), 3);  // 首个>3cout << "3的个数: " << (ub - lb) << endl;  // 2}// 三、容器修改算法{// 1. copy - 复制元素vector<int> src = {1, 2, 3};vector<int> dest(3);copy(src.begin(), src.end(), dest.begin());cout << "copy结果: ";for (int num : dest) cout << num << " ";  // 1 2 3cout << endl;// 2. swap - 交换int a = 1, b = 2;swap(a, b);cout << "swap后: a=" << a << ", b=" << b << endl;  // a=2, b=1// 3. reverse - 反转vector<int> v_rev = {1, 2, 3};reverse(v_rev.begin(), v_rev.end());cout << "reverse结果: ";for (int num : v_rev) cout << num << " ";  // 3 2 1cout << endl;// 4. remove - 移除元素（需配合erase）vector<int> v_rem = {1, 2, 3, 2, 4};auto last = remove(v_rem.begin(), v_rem.end(), 2);  // 逻辑删除v_rem.erase(last, v_rem.end());  // 物理删除cout << "remove后: ";for (int num : v_rem) cout << num << " ";  // 1 3 4cout << endl;// 5. unique - 去重（需先排序）vector<int> v_uni = {1, 2, 2, 3, 3, 3};sort(v_uni.begin(), v_uni.end());auto last_uni = unique(v_uni.begin(), v_uni.end());v_uni.erase(last_uni, v_uni.end());cout << "unique后: ";for (int num : v_uni) cout << num << " ";  // 1 2 3cout << endl;}// 四、数值与集合算法{vector<int> v = {1, 2, 3, 4};// 1. accumulate - 累加/累乘int sum = accumulate(v.begin(), v.end(), 0);  // 初始值0cout << "累加和: " << sum << endl;  // 10int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());cout << "累乘积: " << product << endl;  // 24// 2. count/count_if - 计数vector<int> v_cnt = {1, 2, 2, 3};int cnt = count(v_cnt.begin(), v_cnt.end(), 2);cout << "数字2的个数: " << cnt << endl;  // 2int even_cnt = count_if(v_cnt.begin(), v_cnt.end(), [](int x) { return x%2 == 0; });cout << "偶数个数: " << even_cnt << endl;  // 2// 3. min_element/max_element - 最值vector<int> v_minmax = {3, 1, 4};auto min_it = min_element(v_minmax.begin(), v_minmax.end());auto max_it = max_element(v_minmax.begin(), v_minmax.end());cout << "最小值: " << *min_it << ", 最大值: " << *max_it << endl;  // 1,4// 4. set_intersection - 交集（需已排序）vector<int> a = {1, 2, 3, 4};vector<int> b = {3, 4, 5, 6};vector<int> res;set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res));cout << "交集: ";for (int num : res) cout << num << " ";  // 3 4cout << endl;}return 0;
}

六 、算法使用要点

1. 算法通常接受迭代器范围 [first, last)（左闭右开）
2. 排序相关算法要求容器支持随机访问迭代器（如 vector、array）
3. 二分查找类算法要求范围已排序
4. 自定义谓词需满足 "严格弱序" 规则，避免逻辑错误

这些算法大幅简化了常见操作，合理使用可提高代码效率和可读性。

总结

C++ 容器的设计各有侧重：vector以连续内存和随机访问为核心，list以高效增删为优势，set/map提供有序性和稳定查找，unordered_*系列则追求极致查询效率。理解底层实现是掌握容器的关键 —— 红黑树带来有序性和稳定性能，哈希表带来平均 O (1) 的效率，动态数组平衡了访问与增删成本。实际开发中，需根据具体场景的操作频率和性能需求，选择最适合的容器，才能写出高效、易维护的代码。