AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2023-04-20 72
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 目录一、关联式容器二、键值对三、树形结构的关联式容器四、set的介绍及使用4.1 set的介绍 4.2 set的使用五、multiset的介绍及使用六、map的介绍和使用6.1 map的介绍6.2 map的使用 七、multimap的介绍和使用

目录

一、关联式容器

二、键值对

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

四、set的介绍及使用

4.1 set的介绍

4.2 set的使用

五、multiset的介绍及使用

六、map的介绍和使用

6.1 map的介绍

6.2 map的使用

七、multimap的介绍和使用

一、关联式容器

       前面已经接触过 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

成员类型介绍如下：

image.png

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

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

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

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

四、set的介绍及使用

4.1 set的介绍

set文档介绍：

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

image.png

翻译如下：

  1. set是按照一定次序存储元素的容器
  2. 在set中，元素的 value 也标识它(value就是key，类型为T)，并且每个value 必须是唯一的。set 中的元素不能在容器中修改(元素总是 const)，但是可以从容器中插入或删除它们
  3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序
  4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代
  1. set 在底层是用二叉搜索树(红黑树)实现的

set 的模板参数有三个：

image.png

  1. 第三个模板参数 class Alloc = allocator 是空间配置器，不用理会
  2. 第二个模板参数 class Compare = less 是仿函数，平时不用理会，使用缺省值即可，前面也介绍过了，有需要再传参，set 中元素默认按照小于来比较
  1. 第一个模板参数 class T 是 set 中存放元素的类型，实际在底层存储  的键值对

注意：

  1. 与 map/multimap 不同，map/multimap 中存储的是真正的键值对 ，set/multiset 中只放 value，但在底层实际存放的是由构成的键值对
  2. set 中插入元素时，只需要插入value 即可，不需要构造键值对
  3. 即 set/multiset 为 K模型，map/multimap 为 KV模型

使用set要包含头文件： 

#include <set>

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

4.2 set的使用

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

image.png

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

image.png

  • key_compare 是第二个模板参数（Compare），key_compare 也是第二个模板参数（Compare）
  • key_compare 和 value_compare 也是键值对，与上面类似

（1）set 的构造函数

image.png

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）赋值重载

image.png

测试代码

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

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

（4）Iterators

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

image.png

（5） Capacity

image.png

（6）Modifiers

set中的元素不允许修改

image.png

（7）find

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

image.png

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

五、multiset的介绍及使用

multiset的文档介绍：

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

image.png

翻译：

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

在内部，multis

  1. et中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序
  2. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列
  3. multiset底层结构为二叉搜索树(红黑树)

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

注意：

  1. multiset中再底层中存储的是的键值对
  2. mtltiset的插入接口中只需要插入即可
  3. 与set的区别是，multiset中的元素可以重复，set 是中value是唯一的
  4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
  5. multiset中的元素不能修改
  6. 在multiset中找某个元素，时间复杂度为O(logN)
  7. multiset的作用：可以对元素进行排序


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

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

使用 multiset 要包含头文件：

#include <set>

六、map的介绍和使用

6.1 map的介绍

map的文档介绍：

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

image.png

翻译：

  1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
  2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与 value通过成员类型 value_type 绑定在一起，为其取别名称为 pair
  3. typedef pair value_type
  4. 在内部，map中的元素总是按照键值key进行比较排序的
  5. map中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)
  1. map支持下标访问符，即在[]中放入key，就可以找到与key对应的 value
  2. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

map 的模板参数有4个

image.png

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

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

使用 map 需要包含头文件：

#include <map>

注意：map 也是去重+排序

6.2 map的使用

先介绍 map成员类型：

image.png

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

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

（1）构造函数

image.png

测试代码

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）赋值重载

image.png

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

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

（3）Iterators

image.png

支持迭代器则支持范围 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;
    }
}

运行结果

image.png

（4）Capacity

image.png

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

（5）Modifiers

image.png

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

erase接口如下

image.png

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

insert 接口如下：

image.png

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

先看 insert 接口解释：

  • 参数类型 value_type 是 pair 进行 typedef 得到的，也就是说参数是一个键值对，并使用引用传参
  • insert 第一个（框起来的）的返回类型为 pair
  • pair 第一个iteratior是迭代器，第二个是 bool，用于反映是否插入成功，成功返回true，否则返回false
  • 如果插入成功（即元素不存在进行插入），返回为 pair，迭代器返回的是新插入元素位置的迭代器（pair）
  • 如果插入失败（即元素已经存在），返回为 pair，迭代器返回的是已存在元素位置的迭代器（pair）

image.png

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

测试代码

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;
    }
}

运行结果

image.png

解释一下 make_pair

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

image.png

make_pair 定义如下:

image.png

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

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

下面解释 map的随机访问

（6）Element access

接口如下：

image.png

operator[] 接口定义如下

image.png

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

operator[] 详情如下：


翻译：

  1. 如果k（Key）与容器中元素的键匹配（即Key存在），则函数返回对其映射值的引用，即返回 Key 值的引用
  2. 如果k（Key）与容器中任何元素的键不匹配（即Key不存在），函数将插入具有该键的新元素，并返回对其映射值的引用，即返回 新插入 Key 值的引用
  3. 注意，即使没有为元素分配映射值（即不给T传值，T为空），该元素使用其默认构造函数构造，插入新元素后，这会将容器大小增加1
  4. at 成员函数功能与 [] 类似，但是在具有键的元素存在时具有相同的行为（即查找的元素 Key 是存在的时候，at 和 [] 的功能是一样的），但在不存在时抛出异常（即查找的 Key 不存在，[] 的功能是把这个 Key 直接插入map中，但是 at 是抛异常，不会进行插入）

总结：

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

[] 等价于：

image.png

(*((this->insert(make_pair(k, mapped_type()))).first)).second
  1. 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;
    }
}

运行结果

image.png

总结

  1. map中的的元素是键值对
  2. map中的key是唯一的，并且不能修改
  3. 默认按照小于的方式对key进行比较
  4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
  5. map的底层为平衡搜索树(红黑树)，查找效率logN
  1. map支持[]操作符，operator[]中实际进行插入查找

（7） find

image.png

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

七、multimap的介绍和使用

multimap文档的介绍：

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

image.png

翻译：

  1. Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对，其中多个键值对之间的key是可以重复的
  2. 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对: typedef pair value_type;
  3. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的
  4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列
  5. multimap在底层用二叉搜索树(红黑树)来实现


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

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

注意：

  1. multimap中没有重载 operator[] 操作，因为 multimap 的 Key 可能不唯一
  2. 使用时与map包含的头文件相同

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

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

文章标签：
C++
容器
自然语言处理
存储
关键词：
C++ map
C++ set
C++ set map
C++进阶
Map进阶
枫叶先生_
目录
相关文章
2的n次方_
|
15天前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet（哈希表实现，无序且元素唯一）、LinkedHashSet（保持插入顺序的HashSet）、TreeSet（红黑树实现，自动排序）。Map系列为双列集合，键值一一对应，键不可重复，值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景，并提供了面试题示例，如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
2的n次方_
23 6
【数据结构】map&set详解
刘大猫.
|
4天前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
16 5
游客j4mujezz7vm7y
|
8天前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
游客j4mujezz7vm7y
22 5
周一同学Zelina
|
7天前
|
存储 前端开发 API
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法，并探讨了它们在前端开发中的具体应用，包括如何利用这些数据结构来解决常见的编程问题。
周一同学Zelina
12 0
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
热爱技术的小郑
|
2月前
|
存储 安全 Java
java集合框架复习----（4）Map、List、set
这篇文章是Java集合框架的复习总结，重点介绍了Map集合的特点和HashMap的使用，以及Collections工具类的使用示例，同时回顾了List、Set和Map集合的概念和特点，以及Collection工具类的作用。
热爱技术的小郑
35 1
java集合框架复习----（4）Map、List、set
热爱技术的小郑
|
2月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别？
该CSDN博客文章讨论了Map和Set的区别，但提供的内容摘要并未直接解释这两种集合类型的差异。通常，Map是一种键值对集合，提供通过键快速检索值的能力，而Set是一个不允许重复元素的集合。
热爱技术的小郑
37 3
游客ot6eft3qn37ga
|
2月前
|
存储 JavaScript 前端开发
ES6新特性（四）: Set 和 Map
ES6新特性（四）: Set 和 Map
游客ot6eft3qn37ga
29 1
wljslmz
|
2月前
|
存储 Java 索引
Java 中 List、Set、Map 和 Queue 之间的区别
【8月更文挑战第22天】
wljslmz
20 0
დ旧言~
|
3月前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
დ旧言~
31 2
დ旧言~
|
3月前
|
存储 C++ 容器
【C++】map和set深度讲解（下）
【C++】map和set深度讲解（下）
დ旧言~
55 2

热门文章

最新文章

  • 1
    set DataGrid1.DataSource = rs DataGrid1为什么时空的？
  • 2
    【JAVA秒会技术之异常解决】Dmaven.multiModuleProjectDirectory system propery is not set
  • 3
    Multiple Server Query Execution报The result set could not be merged..
  • 4
    python set(集合)
  • 5
    Set Perennial reservation on RDM LUNs in a Cluster
  • 6
    特殊权限位set_uid set_gid stick_bit 软链接硬链接
  • 7
    oc-16-set,get方法
  • 8
    PHP 魔术方法__set() __get() 方法
  • 9
    主外键关联删除(on delete set null和on delete cascade)
  • 10
    Error: Failed to set Event Logging
  • 1
    JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】（二）
    43
  • 2
    JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】（一）
    30
  • 3
    vue 百度地图开发【教程】1. 绘制百度地图（不使用 vue-baidu-map，解决 BMap is undefined）
    243
  • 4
    vue-baidu-map 绘制行政区划的轮廓，添加行政区划名称（含给覆盖物添加点击事件）——vue 百度地图开发
    169
  • 5
    vue-baidu-map 报错 | map is undefined
    58
  • 6
    vue-baidu-map 报错 | BMap is undefined
    82
  • 7
    vue-baidu-map 自定义地图主题
    171
  • 8
    vue-baidu-map 百度地图检索、获取坐标
    33
  • 9
    DOM 属性列表（命名节点图 Named Node Map）
    29
  • 10
    C++一分钟之-扁平化映射与unordered_map
    50

    • 相关课程

    更多
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    无影云桌面