跳到主要内容C++ set、map 及 unordered_set、unordered_map 使用详解 | 极客日志C++算法
C++ set、map 及 unordered_set、unordered_map 使用详解
系统讲解 C++ STL 中的关联式容器。涵盖 set、map 及其无序版本 unordered_set、unordered_map。对比了基于红黑树的有序容器与基于哈希表的无序容器在底层实现、迭代器特性、性能效率（O(logN) vs O(1)）及 Key 要求上的差异。详细介绍了各类容器的构造、增删查改操作及 multiset/multimap 的冗余支持特性，帮助开发者根据场景选择合适的容器结构。
协议工匠2 浏览 一、序列式容器和关联式容器
• STL 中的部分容器如：string、vector、list、deque、array、forward_list 等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，它依旧是序列式容器，容器中的元素是按它们在容器中的存储位置来顺序保存和访问的。
• 关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，其内部元素通过关键字（key）按特定规则（如比较或哈希）相互关联，形成结构化的映射或集合。顺序容器（即序列式容器）中的元素是按存储位置来保存和访问的，而关联式容器中的元素是按关键字来保存和访问的。关联式容器有 set/map 系列和 unordered_set/unordered_map 系列。
• 本章节讲解的 map/set 系列底层是红黑树，unordered_set/unordered_map 系列底层是哈希表，红黑树是一棵平衡二叉搜索树。set/unordered_set 是 key 搜索场景的结构，map/unordered_map 是 key/value 搜索场景的结构。
二、set 系列的使用
1、set 类的介绍
• set 的声明如下，T 就是 set 底层关键字的类型。
• set 默认要求 T 支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模板参数。
• set 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
• set 底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是走的搜索树的中序遍历，所以是有序的。
template<class T,class Compare = less<T>,class Alloc = allocator<T>>
class set;
2、set 的构造和迭代器
• set 支持正向和反向迭代器遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围 for，set 的迭代器都不支持修改数据，因为会破坏底层搜索树
set<int> s = { 1,2,3,4,5 };
set<int> s1;
set<int> s2(s.begin(), s.end());
set<int> s3(s);
set<int> s4{6,7,8,9,10};
iterator begin();
iterator end();
reverse_iterator rbegin();
reverse_iterator rend();
3、set 的增删查
pair<iterator,bool> insert(const value_type& val);
void insert (initializer_list<value_type> il);
template<class InputIterator>
void insert (InputIterator first,InputIterator last);
iterator erase(const_iterator position);
size_type erase(const value_type& val);
iterator erase(const_iterator first,const_iterator last);
iterator find(const value_type& val);
size_type count(const value_type& val) const;
iterator lower_bound(const value_type& val) const;
iterator upper_bound(const value_type& val) const;
4、insert 和迭代器遍历使用样例
#include<iostream>
#include<set>
using namespace std;
int main() {
set<int> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(5);
set<int>::iterator it = s.begin();
while (it != s.end()) {
cout << *it << ' ';
++it;
}
cout << endl;
for (auto& T : s) {
cout << T << ' ';
}
cout << endl;
return 0;
}
5、multiset 和 set 的差异
• multiset 和 set 的使用基本完全类似，主要区别点在于 multiset 支持值冗余，那么 insert/find/erase 都围绕着支持值冗余有所差异。
• multiset 插入值不会去掉重复的值，里面可能会有多个相同值，find 查找的是中序的第一个，erase 会删除指定的所有相同值。
template<class T,class Compare = less<T>,class Alloc = allocator<T>>
class multiset;
三、map 系列的使用
1、map 类的介绍
• map 的声明如下，Key 就是 map 底层关键字的类型，T 是 map 底层 value 的类型，map 默认要求 Key 支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模板参数，map 底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模板参数。map 底层是用红黑树实现的，增删查改效率是 O(logN),迭代器遍历走的中序，所以是按 Key 有序顺序遍历的。
template < class Key,class T,class Compare=less<Key>,class Alloc=allocator<pair<const Key,T> > >
class map;
2、pair 类型介绍
• map 底层的红黑树节点中的数据，使用 pair<Key,T> 存储键值对数据。
typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2()) {}
pair(const T1& a, const T2& b): first(a), second(b) {}
template<class U, class V>
pair (const pair<U,V>& pr): first(pr.first), second(pr.second) {}
};
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y) {
return ( pair<T1,T2>(x,y) );
}
3、map 的构造和迭代器
• map 支持正向和反向迭代器遍历，遍历默认按 Key 的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围 for，map 支持修改 value 数据，不支持修改 Key 数据，修改关键字数据，破坏了底层搜索树的结构。
map<int,string> m={{1,"apple"},{2,"banana"},{3,"orange"},{4,"mango"}};
map<int,string> m1;
map<int,string> m2(m.begin(),m.end());
map<int,string> m3(m);
map<int,string> m4{{1,"apple"},{7,"banana"},{5,"orange"},{9,"mango"}};
iterator begin();
iterator end();
reverse_iterator rbegin();
reverse_iterator rend();
4、map 的增删查
• map 增接口，插入的 pair 键值对数据，跟 set 有所不同，但是查和删的接口只用关键字 key 跟 set 是完全类似的，不过 find 返回 iterator，不仅仅可以确定 key 在不在，还找到 key 映射的 value，同时通过迭代器还可以修改 value。
pair<iterator,bool> insert (const value_type& val);
void insert (initializer_list<value_type> il);
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
iterator erase (const_iterator position);
size_type erase (const key_type& k);
iterator erase (const_iterator first, const_iterator last);
iterator find (const key_type& k);
size_type count (const key_type& k) const;
iterator lower_bound (const key_type& k);
const_iterator lower_bound (const key_type& k) const;
5、map 的数据修改
• map 第一个支持修改的方式是通过迭代器，迭代器遍历时或者 find 返回 key 所在的 iterator 修改，map 还有一个非常重要的修改接口 operator[]，但是 operator[] 不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口。
• 有一个术语上的细节需要注意：我们通常说的'值'指的是 mapped_type，也就是模板的第二个参数 T，比如 map<int, string> 中的 string。但 STL 内部把整个键值对（pair<const Key, T>）的类型称为 value_type，因为这是红黑树节点实际存储的完整单元。简单来说，你通过 map[key] 访问到的是 mapped_type，也就是你想要的'值'；而当你遍历 map 时，每个元素是 value_type，即包含键和值的整个键值对。这种术语差异源于底层实现需要存储完整的键值对，但对外提供便捷的键值访问接口。
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
map<int, string> m{ {1,"apple"} };
auto it = m.begin();
cout << it->first << endl;
cout << it->second << endl;
cout << "************" << endl;
it->second = "banana";
cout << it->first << endl;
cout << it->second << endl;
cout << "************" << endl;
m[1]="apple";
cout << m[1] << endl;
return 0;
}
6.multimap 和 map 的差异
• multimap 和 map 的使用基本完全类似，主要区别点在于 multimap 支持关键值 Key 冗余，那么 insert/find/erase 都围绕着支持关键值 Key 冗余有所差异，就像 set 与 multiset 一样。其次就是 multimap 不支持 []，因为支持 Key 冗余，[] 就只能支持插入了，不能支持修改。
四、unordered_set 和 unordered_map 系列的使用
1、unordered_set 和 unordered_multiset 参考文档
2、unordered_set 类的介绍
• unordered_set 的声明如下，Key 就是 unordered_set 底层关键字的类型。
• unordered_set 默认要求 Key 支持转换为整形，如果不支持或者想按自己的需求走可以自行实现支持将 Key 转成整形的仿函数传给第二个模板参数。
• unordered_set 默认哟啊求 Key 支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将 Key 比较相等的仿函数传给第三个模板参数。
• unordered_set 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数。
• unordered_set 底层是用哈希桶实现，增删查平均效率是 O(1)，迭代器遍历不再有序，为了跟 set 区分，所以取名 unordered_set。
• unordered_set 和 set 的功能高度相似，只是底层结构不同，有一些性能和使用的差异，这里我们只讲他们的差异部分。
template < class Key,class Hash = hash<Key>, class Pred = equal_to<Key>,class Alloc = allocator<Key> >
class unordered_set;
3、unordered_set 和 set 的使用差异
• unordered_set 和 set 的增删查使用方法一模一样。
• unordered_set 和 set 的第一个差异是对 Key 的要求不同，set 要求 Key 支持小于比较，而 unordered_set 要求 Key 支持转成整形且支持等于比较，要理解 unordered_set 的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
• unordered_set 和 set 的第二个差异是迭代器的差异，set 的 iterator 是双向迭代器，unordered_set 是单向迭代器，其次 set 底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以 set 迭代器遍历是有序 + 去重。而 unordered_set 底层是哈希表，迭代器遍历是无序 + 去重。
• unordered_set 和 set 的第三个差异是性能的差异，整体而言大多数场景下，unordered_set 的增删查改更快一些，因为红黑树增删查改效率是 O(logN)，而哈希表增删查平均效率是 O(1)。
4、unordered_map 和 map 的使用差异
• unordered_map 和 map 的增删查改使用方法一模一样。
• unordered_map 和 map 的第一个差异是对 Key 的要求不同，map 要求 Key 支持小于比较，而 unordered_map 要求 Key 支持转成整形且支持等于比较，要理解 unordered_map 的这两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表地要求。
• unordered_map 和 map 的第二个差异是迭代器的差异，map 的 iterator 是双向迭代器，unordered_map 是单向迭代器，其次 map 底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以 map 迭代器遍历是 Key 有序 + 去重。而 unordered_map 底层是哈希表，迭代器遍历是 Key 无序 + 去重。
• unordered_map 和 map 的第三个差异是性能的差异，整体而言大多数场景下，unordered_map 的增删查改更快一些，因为红黑树增删查改效率是 O(logN)，而哈希表增删查平均效率是 O(1)。
5、unordered_multimap/unordered_multiset
• unordered_multimap/unordered_multiset 跟 multimap/multiset 功能完全类似，支持 Key 冗余。
• unordered_multimap/unordered_multiset 跟 multimap/multiset 的差异也是三个方面的差异，Key 的要求的差异，iterator 及遍历顺序的差异，性能的差异。
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
- HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
