C++ map 与 set：关联式容器的去重、排序与键值统计
大家好，STL 前面接触过 string、vector、list、deque 这些序列式容器，这篇转到关联式容器里最常用的两个：set 和 map。它们底层都是红黑树，天生带"去重 + 有序"，再加上 map 的键值对，能省掉不少手写排序去重和查找的代码。下面把常用接口和典型用法过一遍，示例均可直接编译。
目录
- 一、序列式容器与关联式容器
- 二、set：key 模型，去重加排序
- 三、set 的构造与迭代器
- 四、set 常用接口：insert、find、erase
- 五、multiset：允许冗余的 set
- 六、map：key/value 键值对
- 七、map 的插入与查找
- 八、operator[]：插入、查找、修改三合一
- 九、和 unordered 系列的区别
- 十、总结
一、序列式容器与关联式容器
STL 容器大体分两类：
- 序列式容器：string、vector、list、deque、array、forward_list 等，逻辑结构是线性序列，元素按在容器中的存储位置顺序保存和访问。两个位置存的值之间没有强约束，交换一下它还是序列式容器。
- 关联式容器：map/set 系列、unordered_map/unordered_set 系列，逻辑结构通常是非线性的，元素按关键字保存和访问，两个位置之间有紧密关系。底层是搜索树或哈希表，插入时就要放对位置，不能随意交换。
注意区分：按关键字保存访问的是关联式容器，序列式容器是按存储位置访问的，这一点不要记反。
map 和 set 这一系列底层是红黑树——一棵平衡二叉搜索树。所以：
- set 对应纯 key的搜索场景，只判断某个 key 在不在；
- map 对应key/value的搜索场景，存键值对，查 key 拿 value。
二、set：key 模型，去重加排序
set 里每个元素就是一个 key，底层红黑树自动保证两件事：
- 去重：不支持重复值，相同 key 再插也只保留一份；
- 有序：遍历走的是红黑树中序，默认按
less<T>升序排列。
#include<iostream>#include<set>#include<vector>usingnamespacestd;intmain(){// 列表构造：自动去重、自动升序set<int>s4{9,2,6,2,1};for(autoe:s4)cout<<e<<" ";// 1 2 6 9cout<<endl;// 区间构造：可以拿 vector 的迭代器来初始化vector<int>vec{4,2,7,1};set<int>s(vec.begin(),vec.end());for(autoe:s)cout<<e<<" ";// 1 2 4 7cout<<endl;// 降序：第二个模板参数传 greater<int>set<int,greater<int>>ds{5,2,7,3};for(autoe:ds)cout<<e<<" ";// 7 5 3 2cout<<endl;return0;}set 的模板签名长这样，一般只用第一个参数：
template<classT,classCompare=less<T>,classAlloc=allocator<T>>classset;- 第二个参数 Compare 决定比较方式，默认
less<T>升序；想降序传greater<int>，自定义类型也可以自己写仿函数； - 第三个参数是空间配置器，日常不用管。
三、set 的构造与迭代器
常见构造方式：无参默认构造、拷贝构造、迭代器区间构造、初始化列表构造。支持正向和反向双向迭代器，也就支持范围 for。
一个容易想不通的点：线性结构里迭代器就是指针，++走到下一个位置就行；set 是树形结构，在节点分叉时怎么保证按顺序走？
答案在中序遍历：set 的迭代器内部记住了下一个该访问哪个节点，operator++沿着中序关系走，所以遍历出来天然有序。begin()指向最小值，end()是最右节点之后的哨兵位置，它的前一个迭代器就是最大值。
另外，set 的迭代器是不能修改 key的——*it = 1会编译报错，因为改了关键码就破坏了底层搜索树结构。
四、set 常用接口：insert、find、erase
#include<iostream>#include<set>#include<algorithm>usingnamespacestd;intmain(){set<int>s={1,2,3,4,2,7,6,5,8};for(autoe:s)cout<<e<<" ";// 1 2 3 4 5 6 7 8cout<<endl;// 1. 直接按值删除：不存在返回 0，存在删除并返回 1if(s.erase(2)==0)cout<<"2 不存在"<<endl;elsecout<<"删除 2 成功"<<endl;// 2. 先 find 再按迭代器删除autopos=s.find(5);if(pos==s.end())cout<<"5 不存在"<<endl;else{cout<<"5 存在，准备删除"<<endl;s.erase(pos);}for(autoe:s)cout<<e<<" ";cout<<endl;// 3. 两个 find 的区别intx=6;// 算法库的 find：从头遍历，O(N)autoit1=find(s.begin(),s.end(),x);// set 自己的 find：沿红黑树比较路径查找，O(logN)autoit2=s.find(x);cout<<(it1!=s.end()?"算法find找到":"算法find没找到")<<endl;cout<<(it2!=s.end()?"set.find找到":"set.find没找到")<<endl;return0;}几个要点：
insert(val)返回pair<iterator, bool>：插入成功 bool 为 true，key 已存在则 bool 为 false，但 first 都会指向这个 key 所在节点；find(val)沿比较路径找，O(logN)，找不到返回end()；erase(val)返回删除个数（set 里是 0 或 1），erase(pos)删迭代器位置；- 算法库的
find(begin, end, x)对 set 是线性遍历 O(N)，能用成员find就用成员的。
相关接口还有lower_bound(k)返回第一个大于等于k 的位置、upper_bound(k)返回第一个大于k 的位置，常用来截取一个有序区间。
五、multiset：允许冗余的 set
multiset 和 set 用法几乎一样，区别只有一个：允许 key 重复，它仍然排序，但不去重。因此 insert、find、count、erase 都围绕"允许冗余"有差异。
#include<iostream>#include<set>usingnamespacestd;intmain(){// 排序，但不去重multiset<int>s={4,2,7,2,4,8,4,5,4,9};for(autoe:s)cout<<e<<" ";cout<<endl;// 2 2 4 4 4 4 5 7 8 9// find 返回中序里第一个等于 x 的节点；// 从它开始连续往后，就能遍历所有等于 x 的元素intx=4;autopos=s.find(x);while(pos!=s.end()&&*pos==x){cout<<*pos<<" ";++pos;}cout<<endl;// 4 4 4 4// 按值 erase 会删除所有等于 x 的元素（set 里只删 0 或 1 个）s.erase(4);for(autoe:s)cout<<e<<" ";cout<<endl;// 2 2 5 7 8 9return0;}注意：multiset 里erase(x)一次删掉全部 x；如果只想删其中一个，要拿到它的迭代器再erase(pos)。删除涉及节点改动，遍历时不要一边删一边用旧迭代器，否则会迭代器失效。
六、map：key/value 键值对
map 每个节点存的是一对数据，底层红黑树节点里用pair<const Key, T>存键值对。pair 是 STL 里用来捆绑两个不同类型值的结构体，定义大致如下：
template<classT1,classT2>structpair{typedefT1 first_type;// 第一个值的类型typedefT2 second_type;// 第二个值的类型T1 first;// 第一个成员：map 里就是 keyT2 second;// 第二个成员：map 里就是 value// 默认构造：两个成员都调默认构造pair():first(T1()),second(T2()){}// 用两个给定值构造pair(constT1&a,constT2&b):first(a),second(b){}// 模板拷贝构造：允许从 pair<U,V> 转换过来（U/V 可隐式转换为 T1/T2）template<classU,classV>pair(constpair<U,V>&pr):first(pr.first),second(pr.second){}};日常不用手动new pair，更多是用make_pair函数模板简便地构造一对值：
template<classT1,classT2>inlinepair<T1,T2>make_pair(T1 x,T2 y){returnpair<T1,T2>(x,y);}它的好处是自动推导类型，写make_pair("sort", "排序")就不用再手写pair<string,string>。
对应到 map 的模板：
template<classKey,classT,classCompare=less<Key>,classAlloc=allocator<pair<constKey,T>>>classmap;几个类型别名要分清：
key_type是 Key，mapped_type是 T（日常习惯叫 value）；value_type是pair<const Key, mapped_type>——注意 pair 里 key 前面带const。
正因为节点存的是pair<const Key, T>，key 是 const 成员，所以key 不能改、value 可以改：你可以it->second = "新值"，但不能it->first = "新key"，改了 key 就破坏了红黑树的有序结构。
map 同样是红黑树，增删查 O(logN)，迭代器走中序，按 key 升序遍历。
七、map 的插入与查找
#include<iostream>#include<map>#include<string>usingnamespacestd;intmain(){map<string,string>dict={{"left","左边"},{"right","右边"},{"insert","插入"},{"string","字符串"}};// 遍历：it->first 取 key，it->second 取 valuefor(constauto&e:dict)cout<<e.first<<":"<<e.second<<endl;// insert 的四种写法pair<string,string>kv1("first","第一个");dict.insert(kv1);dict.insert(pair<string,string>("second","第二个"));dict.insert(make_pair("sort","排序"));dict.insert({"auto","自动的"});// key 已存在，插入失败，value 不会被覆盖dict.insert({"left","左边，剩余"});// find 不仅判断 key 在不在，还能拿到对应的 valuestring word="sort";autoret=dict.find(word);if(ret!=dict.end())cout<<word<<" -> "<<ret->second<<endl;elsecout<<word<<" 不在字典中"<<endl;return0;}两个细节：
- 迭代器输出写成
it->first：第一个->是迭代器重载，返回指向 pair 的指针；第二个->才是取 pair 的成员，连着写省略了中间一步； insert返回的pair<iterator, bool>和底层节点存的pair<key, value>是两个不同的 pair，不要混：前者 first 是迭代器、second 是是否插入成功；后者 first 是 key、second 是 value。
八、operator[]：插入、查找、修改三合一
map 最常用的operator[]不只是"取值"，它一个接口干三件事：key 不存在就插入并给 mapped_type 默认值，key 存在就返回 value 的引用。
它的内部实现大致就是借助 insert：
mapped_type&operator[](constkey_type&k){// insert 不存在的 k 时会插入 {k, mapped_type()}；// 已存在则插入失败，但 first 仍指向该节点pair<iterator,bool>ret=insert({k,mapped_type()});// ret.first是iterator，迭代器封装的是Node*节点指针，而节点的关节存值Key和Value又是piar的形式iterator it=ret.first;returnit->second;// it现在是pair类型，first是key，second是value，返回 value 的引用，可读可写}典型应用是统计次数。先看用 find + insert 的写法：
#include<iostream>#include<map>#include<string>usingnamespacestd;intmain(){string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"};map<string,int>countMap;for(constauto&str:arr){autoret=countMap.find(str);if(ret==countMap.end())countMap.insert({str,1});// 第一次出现elseret->second++;// 已存在，次数加一}for(constauto&e:countMap)cout<<e.first<<":"<<e.second<<endl;return0;}同样的逻辑用[]一行就够：
for(constauto&str:arr){// 不存在：插入 {str, 0}，返回 0 的引用，++ 变 1// 已存在：返回次数的引用，++ 加一countMap[str]++;}[]的另外几种用法：
#include<iostream>#include<map>#include<string>usingnamespacestd;intmain(){map<string,string>dict;dict.insert(make_pair("sort","排序"));dict["insert"];// key 不存在：插入 {"insert", ""}dict["left"]="左边";// 插入 + 赋值dict["left"]="左边、剩余";// key 已存在：修改 valuecout<<dict["left"]<<endl;// key 存在：查找取值return0;}注意：用
[]时如果 key 不存在，它会顺手把 key 插进去。所以只有在确定要"找不到就新建"时才用它；单纯判断 key 在不在，更适合用find或count，避免误插入空节点。
九、和 unordered 系列的区别
关联式容器还有另一组：unordered_map、unordered_set。区别在底层：
- map/set：红黑树，key 有序，增删查 O(logN)；
- unordered_map/unordered_set：哈希表，key 无序，平均 O(1)。
需要按 key 有序遍历、取范围时用 map/set；只关心快速查找、不需要顺序时，unordered 系列更快。
十、总结
- 两类容器：序列式按存储位置访问，关联式按关键字访问；map/set 底层是红黑树。
- set：纯 key、自动去重升序；迭代器走中序所以有序，不能通过迭代器改 key。
- 常用接口：
insert返回pair<iterator,bool>，find是 O(logN)，erase支持按值或按迭代器；算法库find对 set 是 O(N)。 - multiset：允许 key 冗余、仍排序；
erase(x)一次删掉全部 x。 - map：节点存
pair<const Key,T>，key 不能改、value 可以改；find能直接拿到 value。 - operator[]：插入、查找、修改三合一，典型用法是
map[key]++计数；但会顺手插入不存在的 key。 - 有序用 map/set（红黑树 O(logN)），无序快速查找用 unordered 系列（哈希 O(1)）。
