【数据结构手册008】STL容器完全参考指南

【数据结构手册008】STL容器完全参考指南

0 容器概览：统一接口，各异特性

C++ STL容器虽然功能各异，但遵循统一的设计哲学。理解这种"家族相似性"能让我们更快掌握新容器。

// 所有容器的共同基础template<typenameT>classContainerConcept{public:// 类型定义usingvalue_type=T;usingsize_type=size_t;usingiterator=...;usingconst_iterator=...;// 基础操作boolempty()const;size_typesize()const;voidclear();// 迭代器iteratorbegin();iteratorend();const_iteratorcbegin()const;const_iteratorcend()const;};

1 序列容器：线性存储

std::vector - 动态数组

本质：连续内存的动态数组

#include<vector>std::vector<int>vec={1,2,3};// === 核心操作 ===vec.push_back(4);// 尾部添加: {1,2,3,4}vec.pop_back();// 尾部删除: {1,2,3}vec.insert(vec.begin()+1,9);// 指定位置插入: {1,9,2,3}vec.erase(vec.begin()+1);// 指定位置删除: {1,2,3}// === 元素访问 ===inta=vec[1];// 无边界检查: 2intb=vec.at(1);// 有边界检查: 2intc=vec.front();// 首元素: 1intd=vec.back();// 末元素: 3int*data=vec.data();// 原始指针// === 容量管理 ===vec.reserve(100);// 预分配容量vec.shrink_to_fit();// 释放多余容量size_t cap=vec.capacity();// 当前容量size_t sz=vec.size();// 当前大小// === 现代C++ ===vec.emplace_back(5);// 原地构造，避免拷贝

std::deque - 双端队列

本质：分段连续数组

#include<deque>std::deque<int>dq={2,3,4};// === 双端操作 ===dq.push_front(1);// 头部添加: {1,2,3,4}dq.push_back(5);// 尾部添加: {1,2,3,4,5}dq.pop_front();// 头部删除: {2,3,4,5}dq.pop_back();// 尾部删除: {2,3,4}// === 元素访问 ===inta=dq[1];// 随机访问: 3intb=dq.at(1);// 安全访问: 3intc=dq.front();// 头部: 2intd=dq.back();// 尾部: 4// === 修改操作 ===dq.insert(dq.begin()+1,9);// 中间插入: {2,9,3,4}dq.erase(dq.begin()+2);// 中间删除: {2,9,4}

std::list - 双向链表

本质：双向链表

#include<list>std::list<int>lst={1,3,4};// === 双端操作 ===lst.push_front(0);// 头部添加: {0,1,3,4}lst.push_back(5);// 尾部添加: {0,1,3,4,5}lst.pop_front();// 头部删除: {1,3,4,5}lst.pop_back();// 尾部删除: {1,3,4}// === 高效插入删除 ===autoit=lst.begin();++it;// 指向1lst.insert(it,2);// {1,2,3,4} - O(1)it=lst.begin();++++it;// 指向3lst.erase(it);// {1,2,4} - O(1)// === 特殊操作 ===lst.sort();// 排序: {1,2,4}lst.unique();// 去重lst.reverse();// 反转: {4,2,1}// === 链表拼接 ===std::list<int>other={5,6};lst.splice(lst.end(),other);// {4,2,1,5,6}

std::forward_list - 单向链表

本质：单向链表（更省内存）

#include<forward_list>std::forward_list<int>flst={2,3,4};// === 单端操作 ===flst.push_front(1);// 头部添加: {1,2,3,4}flst.pop_front();// 头部删除: {2,3,4}// === 特殊插入 ===autoit=flst.begin();++it;// 指向3flst.insert_after(it,9);// {2,3,9,4} - 在指定位置后插入// === 特殊删除 ===it=flst.begin();flst.erase_after(it);// {2,9,4} - 删除指定位置后的元素// 注意：没有size()、push_back()、pop_back()！

std::array - 固定大小数组

本质：编译期固定大小的数组

#include<array>std::array<int,5>arr={1,2,3,4,5};// === 元素访问 ===inta=arr[1];// 2intb=arr.at(1);// 2intc=arr.front();// 1intd=arr.back();// 5// === 容量信息 ===boolempty=arr.empty();// falsesize_t size=arr.size();// 5size_t max_size=arr.max_size();// 5// === 填充操作 ===arr.fill(0);// {0,0,0,0,0}// 注意：大小在编译期确定，无法改变！

2 容器适配器

std::stack - 后进先出

本质：LIFO栈

#include<stack>std::stack<int>stk;// === 栈操作 ===stk.push(1);// 压栈: [1]stk.push(2);// [1,2]stk.push(3);// [1,2,3]inttop=stk.top();// 查看栈顶: 3stk.pop();// 出栈: [1,2]boolempty=stk.empty();// falsesize_t size=stk.size();// 2// === 底层容器 ===std::stack<int,std::vector<int>>stk_vec;// 使用vectorstd::stack<int,std::list<int>>stk_list;// 使用list

std::queue - 先进先出

本质：FIFO队列

#include<queue>std::queue<int>q;// === 队列操作 ===q.push(1);// 入队: [1]q.push(2);// [1,2]q.push(3);// [1,2,3]intfront=q.front();// 队首: 1intback=q.back();// 队尾: 3q.pop();// 出队: [2,3]boolempty=q.empty();// falsesize_t size=q.size();// 2

std::priority_queue - 优先队列

本质：堆实现的优先级队列

#include<queue>// 默认大顶堆std::priority_queue<int>pq;// === 优先队列操作 ===pq.push(3);// 添加: [3]pq.push(1);// [3,1]pq.push(4);// [4,3,1]pq.push(2);// [4,3,2,1]inttop=pq.top();// 最大元素: 4pq.pop();// 删除最大: [3,2,1]boolempty=pq.empty();// falsesize_t size=pq.size();// 3// === 小顶堆 ===std::priority_queue<int,std::vector<int>,std::greater<int>>min_pq;min_pq.push(3);// [3]min_pq.push(1);// [1,3]min_pq.push(4);// [1,3,4]intmin_top=min_pq.top();// 最小元素: 1

3 关联容器

std::set - 唯一键有序集合

本质：红黑树实现的有序集合

#include<set>std::set<int>s={3,1,4,1,5};// {1,3,4,5}// === 插入操作 ===auto[it1,success1]=s.insert(2);// {1,2,3,4,5}, success1=trueauto[it2,success2]=s.insert(3);// 不变, success2=false// === 查找操作 ===autoit=s.find(3);// 返回迭代器if(it!=s.end()){intvalue=*it;// 3}boolexists=s.contains(4);// C++20: trueintcount=s.count(1);// 1 (存在)// === 范围操作 ===autolower=s.lower_bound(2);// 第一个>=2的元素autoupper=s.upper_bound(4);// 第一个>4的元素// === 删除操作 ===s.erase(3);// 删除3: {1,2,4,5}s.erase(it);// 通过迭代器删除

std::multiset - 可重复键有序集合

本质：允许重复的有序集合

#include<set>std::multiset<int>ms={1,3,3,4};// === 重复插入 ===ms.insert(3);// {1,3,3,3,4}// === 计数操作 ===intcount=ms.count(3);// 3// === 范围查找 ===autorange=ms.equal_range(3);for(autoit=range.first;it!=range.second;++it){std::cout<<*it<<" ";// 3 3 3}

std::unordered_set - 唯一键无序集合

本质：哈希表实现的无序集合

#include<unordered_set>std::unordered_set<int>us={3,1,4,1,5};// {1,3,4,5} 顺序不定// === 基本操作 ===us.insert(2);// 插入2us.erase(3);// 删除3boolfound=us.contains(4);// 检查存在// === 哈希表管理 ===us.reserve(100);// 预分配桶floatload_factor=us.load_factor();// 当前负载因子size_t bucket_count=us.bucket_count();// 桶数量// === 桶迭代 ===for(size_t i=0;i<us.bucket_count();++i){size_t bucket_size=us.bucket_size(i);}

std::unordered_multiset - 可重复键无序集合

本质：允许重复的无序集合

#include<unordered_set>std::unordered_multiset<int>ums={1,3,3,4};// === 重复操作 ===ums.insert(3);// 再添加一个3intcount=ums.count(3);// 3autorange=ums.equal_range(3);// 所有等于3的元素

4 关联数组

std::map - 唯一键有序映射

本质：红黑树实现的有序键值对

#include<map>std::map<std::string,int>scores={{"Alice",95},{"Bob",87}};// === 插入操作 ===scores["Charlie"]=92;// 插入或更新auto[it,success]=scores.insert({"David",78});// === 访问操作 ===intalice_score=scores["Alice"];// 95intbob_score=scores.at("Bob");// 87// === 查找操作 ===autofind_it=scores.find("Alice");if(find_it!=scores.end()){auto&[key,value]=*find_it;// 结构化绑定}boolhas_eve=scores.contains("Eve");// false// === 范围操作 ===autolower=scores.lower_bound("B");// 第一个键>=Bautoupper=scores.upper_bound("C");// 第一个键>C// === 现代插入 ===scores.emplace("Eve",88);// 原地构造scores.try_emplace("Frank",91);// 键不存在时插入scores.insert_or_assign("Alice",96);// 插入或更新

std::multimap - 可重复键有序映射

本质：允许重复键的有序映射

#include<map>std::multimap<std::string,int>mmap={{"Alice",95},{"Alice",88},{"Bob",87}};// === 重复插入 ===mmap.insert({"Alice",92});// 允许重复键// === 范围查找 ===autorange=mmap.equal_range("Alice");for(autoit=range.first;it!=range.second;++it){std::cout<<it->second<<" ";// 95 88 92}

std::unordered_map - 唯一键无序映射

本质：哈希表实现的无序键值对

#include<unordered_map>std::unordered_map<std::string,int>word_count;// === 基本操作 ===word_count["hello"]=3;// 插入或更新word_count["world"]++;// 更新word_count.erase("hello");// 删除// === 安全访问 ===if(word_count.find("test")!=word_count.end()){intcount=word_count["test"];// 安全访问}// === 哈希表管理 ===word_count.reserve(1000);// 预分配word_count.rehash(500);// 重新哈希// === 现代操作 ===word_count.emplace("new",1);// 原地构造word_count.try_emplace("key",42);// 安全插入

std::unordered_multimap - 可重复键无序映射

本质：允许重复键的无序映射

#include<unordered_map>std::unordered_multimap<std::string,int>ummap;// === 重复插入 ===ummap.insert({"key",1});ummap.insert({"key",2});// 允许重复// === 范围操作 ===autorange=ummap.equal_range("key");for(autoit=range.first;it!=range.second;++it){std::cout<<it->second<<" ";// 1 2}

5 字符串

std::string - 字符序列

本质：动态字符数组

#include<string>std::string str="Hello";// === 修改操作 ===str+=" World";// 拼接: "Hello World"str.append("!");// 追加: "Hello World!"str.insert(5,",");// 插入: "Hello, World!"str.erase(5,1);// 删除: "Hello World!"// === 查找操作 ===size_t pos=str.find("World");// 6size_t rpos=str.rfind("l");// 9 (最后一个l)// === 子串操作 ===std::string sub=str.substr(6,5);// "World"str.replace(6,5,"C++");// "Hello C++!"// === 数值转换 ===std::string num_str=std::to_string(42);// "42"intnum=std::stoi("123");// 123// === C字符串交互 ===constchar*cstr=str.c_str();// C风格字符串size_t len=str.length();// 字符串长度

位集合：紧凑的布尔数组

std::bitset - 固定大小位集合

本质：编译期固定大小的位数组

#include<bitset>std::bitset<8>bs(0b10101010);// 170// === 位操作 ===bs.set(0);// 设置第0位: 0b10101011bs.reset(1);// 清除第1位: 0b10101001bs.flip(2);// 翻转第2位: 0b10101101// === 访问操作 ===boolbit0=bs[0];// 访问第0位boolbit1=bs.test(1);// 安全访问第1位// === 统计操作 ===size_t count=bs.count();// 设置位数量: 5boolany=bs.any();// 是否有设置位: trueboolall=bs.all();// 是否所有位都设置: falseboolnone=bs.none();// 是否没有设置位: false// === 转换操作 ===std::string str=bs.to_string();// "10101101"unsignedlongnum=bs.to_ulong();// 173

性能特征快速参考

时间复杂度对比表

迭代器失效规则

选择决策树

基础选择流程

需要键值对？ ├─ 是 → 需要有序？ │ ├─ 是 → 键是否唯一？ │ │ ├─ 是 → std::map │ │ └─ 否 → std::multimap │ └─ 否 → 键是否唯一？ │ ├─ 是 → std::unordered_map │ └─ 否 → std::unordered_multimap │ └─ 否 → 需要唯一元素？ ├─ 是 → 需要有序？ │ ├─ 是 → std::set │ └─ 否 → std::unordered_set │ └─ 否 → 主要操作在首尾？ ├─ 是 → std::deque ├─ 否 → 需要随机访问？ │ ├─ 是 → std::vector │ └─ 否 → std::list │ └─ 特定访问模式？ ├─ LIFO → std::stack ├─ FIFO → std::queue └─ 优先级 → std::priority_queue

性能优化指南

// 1. 预分配空间std::vector<int>vec;vec.reserve(1000);// 避免重复分配std::unordered_map<int,int>umap;umap.reserve(1000);// 避免重新哈希// 2. 使用emplace避免拷贝std::vector<std::string>vec;vec.emplace_back("hello");// 原地构造std::map<int,std::string>map;map.emplace(1,"world");// 避免临时对象// 3. 利用移动语义std::vector<std::string>getData(){std::vector<std::string>data;// ... 填充数据returndata;// 移动而非拷贝}// 4. 选择合适的算法std::vector<int>data={5,3,1,4,2};std::sort(data.begin(),data.end());// 快速排序std::stable_sort(data.begin(),data.end());// 稳定排序// 5. 利用视图避免拷贝 (C++20)#if__has_include(<ranges>)#include<ranges>std::vector<int>numbers={1,2,3,4,5};autoeven_numbers=numbers|std::views::filter([](intn){returnn%2==0;});// 不拷贝数据#endif

现代C++最佳实践

1. 结构化绑定 (C++17)

std::map<std::string,int>scores={{"Alice",95},{"Bob",87}};// 传统方式for(constauto&pair:scores){std::cout<<pair.first<<": "<<pair.second<<std::endl;}// 现代方式for(constauto&[name,score]:scores){std::cout<<name<<": "<<score<<std::endl;}

2. 透明比较器 (C++14)

std::set<std::string,std::less<>>transparent_set;transparent_set.insert("hello");boolfound=transparent_set.contains("hello");// 不需要构造std::string

3. 安全访问模式

std::optional<int>safeGet(conststd::map<std::string,int>&map,conststd::string&key){autoit=map.find(key);if(it!=map.end()){returnit->second;}returnstd::nullopt;}// 使用if(autovalue=safeGet(scores,"Alice")){std::cout<<"Score: "<<*value<<std::endl;}

总结：STL容器的设计哲学

1. RAII原则：自动管理资源生命周期
2. 泛型编程：模板实现类型无关算法
3. 迭代器抽象：统一访问接口
4. 算法与容器分离：通过迭代器连接
5. 异常安全：提供基本异常安全保证

掌握这些容器不仅意味着知道它们的API，更重要的是理解它们的设计思想和适用场景。在实际开发中，正确的容器选择往往比算法优化带来更大的性能提升。