一、关联式容器

前面已经接触过 STL 中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身

什么是关联式容器？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高

set 和 map 便是关联式容器

二、键值对

什么是键值对？

键值对是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息

比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义

在 set 和 map 就使用了键值对，这个键值对名为 pair，他是一个 struct 定义的类模板，即可以在外部访问 pair 里面的成员变量

SGI-STL中关于键值对的定义如下：

template<classT1, classT2>structpair{
typedefT1first_type;
typedefT2second_type;
T1first;
T2second;
pair() : first(T1()), second(T2())
    {}
pair(constT1&a, constT2&b) : first(a), second(b)
    {}
};

pair文档介绍：

https://legacy.cplusplus.com/reference/utility/pair/?kw=pair

成员类型介绍如下：

如何使用 pair ，下面介绍 set 和 map 再解释

三、树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构

树型结构的关联式容器主要有四种：map、set、multimap、multiset，这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列

四、set的介绍及使用

4.1 set的介绍

set文档介绍：

https://legacy.cplusplus.com/reference/set/set/?kw=set

翻译如下：

set是按照一定次序存储元素的容器

在set中，元素的 value 也标识它(value就是key，类型为T)，并且每个value 必须是唯一的。set 中的元素不能在容器中修改(元素总是 const)，但是可以从容器中插入或删除它们

在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序

set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代

set 在底层是用二叉搜索树(红黑树)实现的

set 的模板参数有三个：

第三个模板参数 class Alloc = allocator 是空间配置器，不用理会
第二个模板参数 class Compare = less 是仿函数，平时不用理会，使用缺省值即可，前面也介绍过了，有需要再传参，set 中元素默认按照小于来比较

第一个模板参数 class T 是 set 中存放元素的类型，实际在底层存储的键值对

注意：

与 map/multimap 不同，map/multimap 中存储的是真正的键值对 ，set/multiset 中只放 value，但在底层实际存放的是由构成的键值对

set 中插入元素时，只需要插入value 即可，不需要构造键值对

即 set/multiset 为 K模型，map/multimap 为 KV模型

使用set要包含头文件：

#include <set>

注意：set中的元素不可以重复(因此可以使用set进行去重)

4.2 set的使用

先介绍一下set的前四个成员类型

key_type 是第一个模板参数，即（T），value_type 也是第一个模板参数（T）

value_type 对应键值对 pair 的第一个模板参数（T1），value_type 对应键值对 pair 的第一个模板参数（T2），即

key_compare 是第二个模板参数（Compare），key_compare 也是第二个模板参数（Compare）

key_compare 和 value_compare 也是键值对，与上面类似

（1）set 的构造函数

set 提供的构造函数有：第一个空构造和第二个迭代器区间构造，一般都使用空构造，第三个是拷贝构造函数

测试代码

voidTest_Set()
{
set<int>s1;//空构造set<int>s2(s1.begin(), s1.end());//区间构造set<int>s3(s1);//拷贝构造}

set 提供的构造函数有：第一个空构造和第二个迭代器区间构造，一般都使用空构造，第三个是拷贝构造函数

测试代码

voidTest_Set()
{
set<int>s1;//空构造set<int>s2(s1.begin(), s1.end());//区间构造set<int>s3(s1);//拷贝构造}

（2）赋值重载

测试代码

voidTest_Set()
{
set<int>s1;//空构造set<int>s2(s1);//拷贝构造set<int>s3;
s3=s1;//赋值重载}

析构函数，这个就不介绍了，程序结束自动调用

（4）Iterators

使用 set 的迭代器遍历set中的元素，可以得到有序序列

（5） Capacity

（6）Modifiers

set中的元素不允许修改

（7）find

set 中查找某个元素，时间复杂度为：logN

以上接口都与之前学的容器接口用法大致相同，就不再演示了

五、multiset的介绍及使用

multiset的文档介绍：

https://legacy.cplusplus.com/reference/set/multiset/

翻译：

multiset是按照特定顺序存储元素的容器，其中元素是可以重复的

在multiset中，元素的value也会识别它(因为multiset中本身存储的就是组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除

在内部，multis

et中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序

multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列

multiset底层结构为二叉搜索树(红黑树)

模板参数和成员类型与set一致，不解释了

注意：

multiset中再底层中存储的是的键值对

mtltiset的插入接口中只需要插入即可

与set的区别是，multiset中的元素可以重复，set 是中value是唯一的

使用迭代器对multiset中的元素进行遍历，可以得到有序的序列

multiset中的元素不能修改

在multiset中找某个元素，时间复杂度为O(logN)

multiset的作用：可以对元素进行排序

multiset 的使用与 set一致，最大区别就是：set去重+排序，multiset元素可重复+排序

注意：查找的元素是相同元素的时候，返回的是中序遇到相同的第一个元素的迭代器

使用 multiset 要包含头文件：

#include <set>

六、map的介绍和使用

6.1 map的介绍

map的文档介绍：

https://legacy.cplusplus.com/reference/map/map/?kw=map

翻译：

map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素

在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与 value通过成员类型 value_type 绑定在一起，为其取别名称为 pair

typedef pair value_type

在内部，map中的元素总是按照键值key进行比较排序的

map中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)

map支持下标访问符，即在[]中放入key，就可以找到与key对应的 value

map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

map 的模板参数有4个

第四个模板参数 class Alloc = allocator > 是空间配置器，现在不用理会
第三个模板参数 class Compare = less 是仿函数，平时不用理会，使用缺省值即可，前面也介绍过了，有需要再传参，默认按照小于来比较

第二个模板参数 class T 是键值对中 value 的类型
第二个模板参数 class Key 是键值对中 key 的类型

注意：Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

使用 map 需要包含头文件：

#include <map>

注意：map 也是去重+排序

6.2 map的使用

先介绍 map成员类型：

key_type 是第一个模板参数（Key）
mapped_type 是第二个模板参数（T）
value_type 是 pair 进行 typedef 得到的
key_compare 是第三个模板参数（Compare），比较的是 key_type（Key），缺省值为 less
value_compare是用于比较元素的嵌套函数类

map接口跟 set差不多，但是 map多了随机访问的接口，对 map很重要，下面介绍

（1）构造函数

测试代码

voidTest_Map()
{
//KV模型，通过 Key查找Value//map<Key, Value>map<int, char>m1;//空构造map<int, string>m2;//空构造map<int, char>m3(m1.begin(), m1.end());//区间构造map<int, char>m4(m1);//拷贝构造}

（2）赋值重载

voidTest_Map()
{
map<int, char>m1;//空构造map<int, char>m2(m1);//拷贝构造//赋值重载map<int, char>m3;
m3=m1;
}

析构函数自动调用，不解释

（3）Iterators

支持迭代器则支持范围 for

测试代码

voidTest_Map()
{
map<int, char>m1;//空构造//插入数据。后面解释m1.insert(make_pair(1, 'a'));
m1.insert(make_pair(2, 'b'));
m1.insert(make_pair(3, 'c'));
m1.insert(make_pair(4, 'd'));
m1.insert(make_pair(4, 'd'));//key已存在则不插入，map去重//遍历//map<int, char>::iterator it = m1.begin();autoit=m1.begin();
while (it!=m1.end())
    {
//通过Key查找Value//first是Key，second是Value，（KV模型）//键值对 pair<T1, T2> ---> pair<first, second>cout<<it->first<<"-->"<<it->second<<endl;
++it;
    }
cout<<endl;
//范围forfor (auto&e : m1)//建议加上引用，否则数据大量的时候会带来拷贝大的代价    {
cout<<e.first<<"-->"<<e.second<<endl;
    }
}

运行结果

（4）Capacity

一个判空和一个返回数据的大小，就不演示了

（5）Modifiers

swap 和 clear 不演示了，下面介绍 insert 和 erase

erase接口如下

常用就是传 Key 删除节点，不多解释

insert 接口如下：

最常用就是第一个，问题来了，pair 是什么？？

先看 insert 接口解释：

参数类型 value_type 是 pair 进行 typedef 得到的，也就是说参数是一个键值对，并使用引用传参

insert 第一个（框起来的）的返回类型为 pair

pair 第一个iteratior是迭代器，第二个是 bool，用于反映是否插入成功，成功返回true，否则返回false

如果插入成功（即元素不存在进行插入），返回为 pair，迭代器返回的是新插入元素位置的迭代器（pair）

如果插入失败（即元素已经存在），返回为 pair，迭代器返回的是已存在元素位置的迭代器（pair）

注：这个对下面理解 [] 很重要

测试代码

voidTest_Map()
{
map<int, char>m1;//空构造//插入也要指明键值对的类型 pair<T1, T2>m1.insert(pair<int, char>(1, 'a'));
m1.insert(pair<int, char>(2, 'b'));
// pair<T1, T2> 也可以写成 make_pairm1.insert(make_pair(3, 'c'));
m1.insert(make_pair(4, 'd'));
m1.insert(make_pair(4, 'd'));//key已存在则不插入，map去重for (auto&e : m1)//建议加上引用，否则数据大量的时候会带来拷贝大的代价    {
cout<<e.first<<"-->"<<e.second<<endl;
    }
}

运行结果

解释一下 make_pair

make_pair 是一个模板函数，在 pair 的文档有介绍

make_pair 定义如下:

简单来说，这个函数的功能就像是给 pair 进行 typedef 为 make_pair，直接使用即可

注：pair（x, y）是一个匿名对象

下面解释 map的随机访问

（6）Element access

接口如下：

operator[] 接口定义如下

operator[] 访问的条件是：只需传入第一个模板参数，即 Key 的值，也就是说 [] 访问是通过 Key 来进行访问的

operator[] 详情如下：

翻译：

如果k（Key）与容器中元素的键匹配（即Key存在），则函数返回对其映射值的引用，即返回 Key 值的引用

如果k（Key）与容器中任何元素的键不匹配（即Key不存在），函数将插入具有该键的新元素，并返回对其映射值的引用，即返回新插入 Key 值的引用

注意，即使没有为元素分配映射值（即不给T传值，T为空），该元素使用其默认构造函数构造，插入新元素后，这会将容器大小增加1

at 成员函数功能与 [] 类似，但是在具有键的元素存在时具有相同的行为（即查找的元素 Key 是存在的时候，at 和 [] 的功能是一样的），但在不存在时抛出异常（即查找的 Key 不存在，[] 的功能是把这个 Key 直接插入map中，但是 at 是抛异常，不会进行插入）

总结：

[] 的功能是查找+修改+插入（修改的原因是 [] 返回 mapped_type（T）值的引用）

at 的功能是查找+修改（不支持插入）

[] 等价于：

(*((this->insert(make_pair(k, mapped_type()))).first)).second

make_pair(k, mapped_type()) 第一个参数k（Key）为 pair 第一个模板参数T1

第二个参数 mapped_type() 是一个匿名对象，为 pair 第二个模板参数T2，mapped_type 是 map 第二个模板参数T，即T()

(*((this->insert( make_pair(k, mapped_type()) )).first)).second
make_pair(k, mapped_type())

make_pair 返回的类型是 pair，make_pair 返回 pair，insert 进行接收，把 pair （x, y）作为insert 的参数，即参数 const value_type& val

也就是说

(*((this->insert( make_pair(k, mapped_type()) )).first)).second

可以转换为（方便理解）：

mapped_type&operator[] (constkey_type&k)
{
return (*((this->insert( make_pair(k, mapped_type()) )).first)).second}
---T&operator[](constKey&k)
{
pair<iterator,bool>ret=insert( make_pair(k, T());
//insert 返回 pair<iterator,bool>//迭代器在pair的first的位置（即用 . 可以访问pair的成员变量 first）//迭代器内容访问方式为 ->//-> 操作符的重载前面篇章有过解释returnret.first->second;
}

假设给你一个 string，要统计水果出现的次数

stringarr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

可以使用map进行统计，代码如下：

voidTest_Map()
{
//统计水果出现的次数stringarr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int>countMap1;
for (auto&e : arr)
    {
//map<string, int>::iterator it = countMapautoit=countMap1.find(e);
if (it==countMap1.end())//没有就进行插入        {
countMap1.insert(make_pair(e, 1));
        }
else        {
it->second++;
        }
    }
for (constauto&kv : countMap1)
    {
cout<<kv.first<<":"<<kv.second<<endl;
    }
cout<<endl;
//使用 []map<string, int>countMap2;
for (auto&e : arr)
    {
//不存在则插入//[] 的功能是 查找+修改+插入//operator[]的原理是：//  用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中//  如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器//  如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器//  operator[]函数最后将insert返回值键值对中的value返回countMap2[e]++;
    }
for (constauto&kv : countMap2)
    {
cout<<kv.first<<":"<<kv.second<<endl;
    }
}

运行结果

总结

map中的的元素是键值对

map中的key是唯一的，并且不能修改

默认按照小于的方式对key进行比较

map中的元素如果用迭代器去遍历，可以得到一个有序的序列

map的底层为平衡搜索树(红黑树)，查找效率logN

map支持[]操作符，operator[]中实际进行插入查找

（7） find

直接使用，就不解释了，不懂看文档

七、multimap的介绍和使用

multimap文档的介绍：

https://legacy.cplusplus.com/reference/map/multimap/

翻译：

Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对，其中多个键值对之间的key是可以重复的

在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对: typedef pair value_type;

在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的

multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列

multimap在底层用二叉搜索树(红黑树)来实现

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的

multimap的使用和map一致，就不解释了

注意：

multimap中没有重载 operator[] 操作，因为 multimap 的 Key 可能不唯一

使用时与map包含的头文件相同

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新

【C++进阶】四、STL---set和map的介绍和使用

一、关联式容器

二、键值对

三、树形结构的关联式容器

四、set的介绍及使用

4.1 set的介绍

4.2 set的使用

五、multiset的介绍及使用

六、map的介绍和使用

6.1 map的介绍

6.2 map的使用

七、multimap的介绍和使用

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【C++进阶】四、STL---set和map的介绍和使用

一、关联式容器

二、键值对

三、树形结构的关联式容器

四、set的介绍及使用

4.1 set的介绍

4.2 set的使用

五、multiset的介绍及使用

六、map的介绍和使用

6.1 map的介绍

6.2 map的使用

七、multimap的介绍和使用

热门文章

最新文章

相关课程

相关电子书