C++ 进阶篇 STL map 和 set
一、关联式容器与键值对
1.1、关联式容器
C++初阶的时候，我们已经接触了 STL 中的部分容器并进行了模拟实现，比如 vector、list、stack、queue 等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身；
同样，关联式容器也是用来存储数据的，但与序列式容器不同的是，关联式容器里面存储的是 <key, value> 结构的键值对，因此在数据检索时比序列式容器效率更高。
1.2、键值对 pair
键值对是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 – key 和 value；其中 key 代表键值，value 代表与 key 对应的信息。
我们在上一节学习二叉搜索树的时候提到的 KV 模型 (key-value 模型) 中的 KV 其实就是键值对；我们可以用上一节中提到的英汉互译的例子来理解 key-value 键值对 – 现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。
STL 中键值对的定义如下：(SGI 版本)
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first; //key
T2 second; //value
pair() : first(T1()), second(T2()) //默认构造
{}
pair(const T1& a, const T2& b) : first(a), second(b)
{}
};
可以看到，C++ 中的键值对是通过 pair 类来表示的，pair 类中的 first 就是键值 key，second 就是 key 对应的信息 value；那么以后我们在设计 KV 模型的容器时只需要在容器/容器的每一个节点中定义一个 pair 对象即可；
这里有的同学可能会有疑问，为什么不直接在容器中定义 key 和 value 变量，而是将 key、value 合并到 pair 中整体作为一个类型来使用呢？这是因为 C++ 一次只能返回一个值，如果我们将 key 和 value 单独定义在容器中，那么我们就无法同时返回 key 和 value；而如果我们将 key、value 定义到另一个类中，那我们就可以直接返回 pair，然后再到 pair 中分别去取 first 和 second 即可。
make_pair 函数
由于 pair 是类模板，所以我们通常是以 显式实例化 + 匿名对象 的方式来进行使用，但是由于显式实例化比较麻烦，所以 C++ 还提供了 make_pair 函数，其定义如下：
template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
return (pair<T1, T2>(x, y));
}
如上，make_pair 返回的是一个 pair 的匿名对象，匿名对象会自动调用 pair 的默认构造完成初始化；但由于 make_pair 是一个函数模板，所以模板参数的类型可以根据实参来自动推导完成隐式实例化，这样我们就不用每次都显式指明参数类型了。
注：由于 make_pair 使用起来比 pair 方便很多，所以我们一般都是直接使用 make_pair，而不使用 pair。
1.3、树形结构的关联式容器
根据应用场景的不同，STL 总共实现了两种不同结构的关联式容器 – 树型结构与哈希结构；树型结构的关联式容器主要有四种 – map、set、multimap、multiset，这四种容器的共同点是使用平衡二叉搜索树作为其底层结构，容器中的元素是一个有序的序列；本文将介绍这四个容器的使用。
二、set
2.1、set 的介绍
set 是按照一定次序存储元素的容器，其底层是一棵平衡二叉搜索树 (红黑树)，由于二叉搜索树的每个节点的值满足左孩子 < 根 < 右孩子，并且二叉搜索树中没有重复的 节点，所以 set 可以用来排序、去重和查找，同时由于这是一棵平衡树，所以 set 查找的时间复杂度为 O(logN)，效率非常高；
同时，set 是一种 K模型 的容器，也就是说，set 中只有键值 key，而没有对应的 value，并且每个 key 都是唯一的 ；set 中的元素也不允许修改，因为这可能会破坏搜索树的结构，但是 set 允许插入和删除。
- set 是K模型的容器，所以 set 中插入元素时，只需要插入 key 即可，不需要构造键值对；
- set中的元素不可以重复，因此可以使用set进行去重；
- 由于 set 底层是搜索树，所以使用 set 的迭代器遍历 set 中的元素，可以得到有序序列，即 set 可以用来排序；
- set 默认使用的仿函数为 less，所以 set 中的元素默认按照小于来比较；
- 由于 set 底层是平衡树搜索树，所以 set 中查找某个元素，时间复杂度为 O(logN)；
- set 中的元素不允许修改，因为这可能破坏搜索树的结构；
- set 中的底层使用平衡二叉搜索树 (红黑树) 来实现。
注：可能有的同学对 O(logN) 的时间复杂度没有什么具体的概念，那么我们可以列举一组数据大家就很清楚了：set 从1000个数据找查找某个数据最多找10次，从100万个数据中找某一个数据最多找20次，从10亿个数据中找某一个数据最多找30次；换一种说法，如果以身份证号作为 key 值存入 set 中 (假设内存足够)，那么我们从地球所有人类中查找某一个身份证号对应的人时最多只用找 31 次；相信现在大家对 O(logN) 是什么量级的存在已经有了很清楚的认识了。
2.2、set 的使用
- 构造
和传统容器一样，set 也支持单个元素构造、迭代器区间构造以及拷贝构造：
-
迭代器
set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。
-
修改
set 有如下修改操作
其中 swap 就是交换两棵树的根，clear 就是释放树中的所有节点，emplace 和 emplace_hint 我们放在 C++11 章节中学习，大家现在不用管它；最重要的修改操作是 insert 和 erase（会失效）；
insert 支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间，我们学会第一个即可，插入的过程就是二叉搜索树的插入过程；需要注意的是 insert 的返回值是 pair 类型，pair 中第一个元素代表插入的迭代器位置，第二个元素代表是否插入成功 (插入重复节点会返回 false)：
erase 也有三种，常用的是第一种和第二种，删除指定键值的数据和删除指定迭代器位置的数据：
- 操作
set 还有一些其他操作相关的函数：
其中比较重要的只有 find，由于 set 中不允许出现相同的 key，因此在 set 中 count 函数的返回值只有1/0，可以说没有什么价值，set 中定义 count 主要是因为 count 在set中用于查找一个元素在不在，在multiset中用于查找一个元素出现的次数。在 multiset 中有作用，这里是为了保持一致；lower_bound 和 upper_bound 是得到一个左闭右开的迭代器区间，然后我们可以对这段区间进行某些操作，但实际中其实没什么人用；
find 的作用是在搜索树中查找 key 对应的节点，然后返回节点位置的迭代器，如果找不到，find 会返回 end()：
2.3、set 使用范例
void set_test1()
{
//无参构造
set<int> s1;
//插入数据（重复数据忽略）
s1.insert(1);
s1.insert(6);
s1.insert(5);
s1.insert(9);
s1.insert(4);
s1.insert(8);
s1.insert(8);
s1.insert(6);
s1.insert(2);
//拷贝构造
set<int> s2(s1);
//迭代器遍历
set<int>::iterator it1 = s1.begin();
while (it1 != s1.end())
{
cout << *(it1) << " ";
it1++;
}
cout << endl;
//增强for
for (auto k : s2)
{
cout << k << " ";
}
cout << endl;
//找到8的迭代器
set<int>::iterator it2=s1.find(8);
//输出迭代器的值
cout << *it2<<endl;
//删除迭代器8
s1.erase(it2);
//增强for
for (auto k : s1)
{
cout << k << " ";
}
cout << endl;
//迭代器失效
for (auto k : s2)
{
//找到8的迭代器
//没找到会返回end()
set<int>::iterator it3 = s2.find(8);
////删除迭代器8
//if (it3 != s2.end())
//{
// s2.erase(it3);
// *it3;
//}
//删除迭代器8删除后会返回下一个迭代器的值
if (it3 != s2.end())
{
it3 = s2.erase(it3);
*it3;
}
cout << k << " ";
}
}
三、multiset
3.1、multiset 的介绍
multiset 也是 K模型 的容器，它和 set 唯一的区别在于 multiset 中允许存在重复的 key 值节点，所以 multiset 可以用来排序和查找，但是不能用来去重。
3.2、multiset 的使用
multiset 的使用其实和 set 也几乎一样，唯一需要注意的是 find 和 count 函数 – 由于 multiset 中允许存在重复 key 值的节点，所以 multiset 中 count 函数就有作用了，我们可以通过 count 函数来统计同一 key 中在 multiset 中的数量：
multiset 中 find 函数的使用也和 set 有所区别 – 由于 set 中没有重复的节点，所以 find 时要么返回该节点位置的迭代器，要么返回 end()；而 multiset 中可能有重复的节点，所以 find 时返回的是同一 key 值中的哪一个节点呢？实际上 find 返回的是中序遍历过程中第一个匹配的节点位置的迭代器：
3.3、multiset 使用范例
void multiset_test1()
{
// 相比set不同的是，multiset是排序，但是不去重
multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };//列表初始化
auto it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 相比set不同的是，x可能会存在多个，find查找中序的第一个
int x;
cin >> x;
auto pos = s.find(x);
// 相比set不同的是，count会返回x的实际个数
cout << s.count(x) << endl;
// 相比set不同的是，erase给值时会删除所有的x
s.erase(x);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
四、map
4.1、map 的介绍
- Key就是map底层关键字的类型，T是map底层value的类型。
- map默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，
- map底层存储数据的内存是从空间配置器申请的。
- 一般情况下，我们都不需要传后两个模版参数。
特别注意：map 允许修改节点中 key 对应的 value 的值，但是不允许修改 key，因为这样可能会破坏搜索树的结构。
map底层是用红黑树实现，增删查改效率是 O(logN)，迭代器遍历是走的中序，所以是按key有序顺序遍历的。
4.2、map 的使用
- 构造
其中列表构造需要给一个例子给大家：
map<string, string> dict = { {"left", "左边"},
{"right", "右边"},
{"insert", "插入"}};
- 迭代器
map支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
- 修改
修改中的重点的仍然是 insert 和 erase，swap 为交换两棵树的根，clear 为释放树中的每一个节点；
erase 一样也有三种，常用的是第一种和第二种，删除指定键值的数据和删除指定迭代器位置的数据：
// 删除一个迭代器位置的值
iterator erase (const_iterator position);
// 删除k，k存在返回0，存在返回1
size_type erase (const key_type& k);
// 删除一段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);
4.3、 插入pair的方法
和 set 一样，map 的 insert 也支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间，我们还是学会第一个即可，插入的过程就是二叉搜索树的插入过程；需要注意的是 insert 的返回值是 pair 类型，pair 中第一个元素代表插入的迭代器位置，第二个元素代表是否插入成功 (插入重复节点会返回 false)
方法一：直接新建插入pair
map<string, string> dict;
pair<string, string> kv1("first", "第一个");
dict.insert(kv1);
方法二：匿名对象插入
dict.insert(pair<string, string>("second", "第二个"));
方法三：make_pair
dict.insert(make_pair("sort", "排序"));
方法四：C++11后可以直接插入：（基于 C++11 的列表初始化）
dict.insert({"sort", "排序"});
如下：makepair的底层实现大概是这样的，传递两个值给他，他会帮你变成pair键值对。
- insert插入一个pair<key, T>对象
- 如果key已经在map中，插入失败，则返回一个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false.
- 如果key不在map中，插入成功，则返回一个pair<iterator,bool>对象，返回pair对象first是新插入key所在结点的迭代器，second是true
- 也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器
- 那么也就意味着insert插入失败时充当了查找的功能，正是因为这一点，insert可以用来实现operator[]
- 需要注意的是这里有两个pair，不要混淆了，一个是map底层红黑树节点中存的pair<key, T>，另一个是insert返回值pair<iterator,bool>
- 操作
和 set 一样，map 中有 count 函数是因为 multimap 需要count 函数，count依旧可以拿来当查找接口用，这里是为了保持一致性：
// 查找k，返回k所在的迭代器，没有找到返回end()
iterator find (const key_type& k);
// 查找k，返回k的个数
size_type count (const key_type& k) const;
4.4、operator[]数据修改
operator[]增查改三位一体，那么operator[]的底层是什么？C++官方网站中是这么说的，这说明operator[]的底层是一个insert。
(*((this)->insert(make_pair(k, mapped_type())).first)).second
((this)->insert(make_pair(k, mapped_type())).first)
我们前面说了insert可以查找一样的会返回迭代器位置这里就是找到了一样的迭代器位置
如果key已经在map中，插入失败，则返回一个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false.
(*((this)->insert(make_pair(k, mapped_type())).first)).second
对迭代器解引用取出pair在取出val
如果k不在map中，insert会插入k和mapped_type默认值，同时[]返回结点中存储mapped_type值的引用，那么我们可以通过引用修改该映射值。所以[]具备了插入+修改功能。
如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引用，所以[]具备了查找+修改的功能。
总结
插入成功: pair<新插入值所在迭代器, true>
插入失败: pair<已经存在的跟key相等值迭代器, false>
4.5、map 使用范例
4.5.1统计水果出现的次数 find和iterator
void map_test2()
{
vector<string> v = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> m1;
for (string str : v)
{
//在map里面找水果
map<string,int>::iterator ret = m1.find(str);
//不在
if (ret == m1.end())
{
m1.insert({ str, 1 });
}
//在就加加
else
{
ret->second++;
}
}
// 遍历输出
//必须带const。k不能改
for (pair<const string, int>& k : m1)
{
cout << k.first << "->" << k.second << " ";
}
}
4.5.2统计水果出现的次数 []
void map_test1()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> m1;
for (string& str : arr)
{
m1[str]++; // 有就计数+1，没有就插入默认0再+1
}
// 遍历输出
//必须带const。k不能改
for (pair<const string,int>& k : m1)
{
cout << k.first << "->" << k.second << " ";
}
}
4.5.3字典
void map_test3()
{
map<string, string> dict;
//向map中插入元素的方式：用pair直接来构造键值对
pair<string, string> p1("banan", "香蕉");
dict.insert(p1);
//匿名构造
dict.insert(pair<string, string>("peach", "桃子"));
//为了方便，我们建议直接用make_pair函数来构造键值对
dict.insert(make_pair("apple", "苹果"));
// 将<"orange", "">插入map中，插入成功，返回value的引用，将“橘子”赋值给该引用结果，
dict["orange"] = "橘子";
// 遍历输出
//必须带const。k不能改
for (pair<const string, string>& k : dict)
{
cout << k.first << "->" << k.second << " ";
}
cout << endl;
auto ret = dict.insert(make_pair("peach", "桃"));
//布尔值
if (ret.second)
cout << "<peach, 桃>不在map中, 已经插入" << endl;
else
cout << "键值为 peach 的元素已经存在：" << ret.first->first << "--->" << ret.first->second << " 插入失败" << endl;
dict.erase("apple");
if (1 == dict.count("apple"))
cout << "apple还在" << endl;
else
cout << "apple被吃了" << endl;
}
五、multimap
5.1、multimap介绍与使用
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。(人话就是：用operator[]找一个key，但是这里面有很多个key，不知道返回哪个key指向的value)
count 返回和 key 值相等的节点的个数：
5.2、multimap使用范例
void multimap_test1()
{
// 相比set不同的是，multiset是排序，但是不去重
multimap<string, int> m = {{"语文", 70},{"数学", 80},{"语文", 60},{"物理", 70},};//列表初始化
auto it = m.begin();
// 遍历输出
//必须带const。k不能改
for (pair<const string, int>& k : m)
{
cout << k.first << "->" << k.second << " ";
}
cout << endl;
// 相比set不同的是，k可能会存在多个，find查找中序的第一个
auto pos = m.find("语文");
if (pos != m.end())
{
cout << "find 找到的第一个语文：" << pos->first << "->" << pos->second << endl;
}
// 相比set不同的是，count会返回x的实际个数
cout << m.count("语文") << endl;
// 相比set不同的是，erase给值时会删除所有的x
m.erase("语文");
for (pair<const string, int>& k : m)
{
cout << k.first << "->" << k.second << " ";
}
cout << endl;
}
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
9
0- 0
已为社区贡献3条内容
所有评论(0)