C++笔记---set和map

1. 序列式容器与关联式容器

前面我们已经接触过STL中的部分容器如:string、vector、list、deque、array、forward_list等,这些容器统称为序列式容器,因为逻辑结构为线性序列的数据结构,两个位置存储的值之间一般没有紧密的关联关系,比如交换⼀下,他依旧是序列式容器。

顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是用来存储数据的,与序列式容器不同的是,关联式容器逻辑结构通常是非线性结构,两个位置有紧密的关联关系,交换一下,他的存储结构就被破坏了。

顺序容器中的元素是按关键字来保存和访问的。

关联式容器有map/set系列和unordered_map/unordered_set系列。

本章节讲解的map和set底层是红黑树,红黑树是一颗平衡二叉搜索树。

set/multiset是key搜索场景的结构, map/multimap是key/value搜索场景的结构。

set/map不支持相同的值插入,multiset/multimap支持相同的值插入。

2. pair类 

在正式介绍set和map之前,我们需要先了解一下pair类。

这个类也是一个类模板,顾名思义,它的作用就是存储两个数据,也即将两个数据绑定到一起。

在需要返回两个数据的场景下,我们就可以将两个数据存到pair中进行返回。

pair的原型如下:

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

// C++11之间常用的构造pair的函数
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}

3. set的介绍

参考文档:set - C++ Reference,关于set的使用,将其当作key搜索场景的红黑树来使用即可。

set的原型:

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

类型参数分别为:key的类型,比较器(通过仿函数实现,默认为小于比较,中序遍历得到升序序列),内存池。

一般来说,后两个参数有缺省值,的使用频率较低,我们在日常使用的过程中只需要传入第一个参数即可。

3.1 常用接口

STL的容器都是大同小异,这里只列出需要注意的。

3.1.1 构造函数
set();默认构造
template <class InputIterator>
set(InputIterator first, InputIterator last);
迭代器区间构造
set(const set& x);拷贝构造

在C++11之后还支持用列表构造:

// initializer list (5) initializer 列表构造
set (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());


eg:
set<int> mySet1({1, 2, 3, 4});
set<int> mySet2 = {1, 2, 3, 4};

在原文档中,前两个构造函数的参数列表还包括比较器和内存池:

但是经过我自己的测试发现,如果在定义set的时候传入比较器或内存池,这个定义语句会被编译器识别成函数的声明:

也就是说,比较器和内存池依然只能在类型参数列表中传入。

 3.1.2 迭代器

这里就不列表了,set的迭代器是双向迭代器,函数还是那几个函数。

正向迭代器的是按照key值从小到大进行遍历。

除此之外,在set中无论是iterator还是const_iterator都不支持通过解引用修改set中的数据,因为这样会破坏红黑树的底层结构。

3.1.3 增删
(1)pair<iterator, bool> insert(const value_type& val);
(2)iterator insert(iterator position, const value_type& val);
(3)template <class InputIterator>
   void insert(InputIterator first, InputIterator last);

(1)按值插入

(2)指定位置插入

(3)将容器的迭代器区间内的值插入

(1)void erase(iterator position);
(2)size_type erase(const value_type& val);
(3)void erase(iterator first, iterator last);

(1)删除指定位置的值

(2)删除指定的值

(3)删除一个迭代器区间

insert函数(1)的返回值是一个pair:

插入成功时:iterator为新插入数据的迭代器,bool为true

插入失败时:iterator为已有的相同值的迭代器,bool为false

 insert函数(2)的第一个参数实质上只是一个插入建议,由于set的特殊的红黑树的底层结构,该插入建议可能不会被采纳。

 3.1.4 查找
iterator find (const value_type& val) const;查找某个值
size_type count (const value_type& val) const;查找某个值在set中有几个

set不支持相同的值进行插入,所以count的结果不是1就是0。

这样看来count似乎有点鸡肋,或者说与名称不符,但set中的count实际上是为了与multiset统一而存在的。

但count也并非一无是处,如果只想确定某个值存不存在的话,count就稍微比find方便一点:

if(mySet.find(24) != mySet.end())
{
    // ......
}

if(mySet.count(24))
{
    // ......
}

3.2 multiset

基本与set相同,但是支持插入相同的数据,由此而引发的变化还有:

1. insert一定成功,插入函数(1)的返回值不再是pair而只有iterator。

2. count返回数据在set中的个数。

3. 如果有多个相同的值,无论是删除还是查找,都是对中序遍历的第一个进行操作。

 4. map的介绍

参考文档:map - C++ Reference,关于map的使用,将其当作key/value搜索场景的红黑树来使用即可。

map的原型:

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

类型参数分别为:key的类型,value的类型,比较器(通过仿函数实现,默认为小于比较,中序遍历得到升序序列),内存池。

除此之外,pair在map中起到了将key和value绑定到一起的作用,所以在map的结点中存的数据实际上是pair,而没有单独存储key和value。

typedef pair<const Key, T> value_type;

同样,大多数情况下只需要传入前两个参数即可。

4.1 常用接口

同样,此处只列出较为重要或与其他容器有所不同的。

4.1.1 构造函数
map();默认构造
template <class InputIterator>
map (InputIterator first, InputIterator last);
迭代器区间构造
map (const map& x);拷贝构造

在C++11之后支持列表构造:

// initializer list (5) initializer 列表构造
map (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());

eg:
map<string, int> myMap1({{"张三", 18}, {"李四", 21}, {"王五", 35}});
map<string, int> myMap2 = {{"张三", 18}, {"李四", 21}, {"王五", 35}};

内层大括号会通过pair的列表构造隐式类型转换为pair<string, int>类型。 

关于参考文档中给出的函数原型,依然存在着和set相同的问题。

 4.1.2 迭代器

函数还是那些函数,迭代器还是双向迭代器。

但与set不同的是,map的迭代器支持对value进行修改,而依然不支持对key进行修改。

由于map结点中存的是pair<key, value>,所以按照逻辑来说,map的迭代器解引用得到的就是pair<key, value>。

在pair中,key对应的是first,value对应的是second:

map<string, int> myMap(...);
map<string, int>::iterator it = myMap.begin();
while(it != myMap.end())
{
    cout << "key:" << (*it).first << " value:" << *(it).second << endl;
    cout << "key:" << it->first << " value:" << it->second << endl;
}
4.1.3 增删
(1)pair<iterator, bool> insert(const value_type& val);
(2)iterator insert(iterator position, const value_type& val);
(3)template <class InputIterator>
   void insert(InputIterator first, InputIterator last);

(1)按值插入

(2)指定位置插入

(3)将容器的迭代器区间内的值插入

(1)void erase(iterator position);
(2)size_type erase(const key_type& k);
(3)void erase(iterator first, iterator last);

(1)删除指定位置的值

(2)删除指定的值

(3)删除一个迭代器区间

函数原型与set完全一样,除了erase函数(2),只需要key即可找到对应的数据进行删除。

但是要切记,这里的value_type是pair。

insert函数(1)的返回值逻辑也与set相同,但是只要key相同就不支持继续插入了。

4.1.4 查找
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;
按键值key查找
size_type count (const key_type& k) const;查找某个键值key在set中有几个

 同样这里的count函数的返回值也只能是1或0。

4.1.5 operator[]

没错,map重载了"[]"。

但是,按理来说,只有支持随机迭代器的容器才可以重载"[]",而map不是双向迭代器吗?

看了函数原型你就明白了:

mapped_type& operator[] (const key_type& k);

所以,这个"[]"的功能是根据key来返回value的引用,而与迭代器没有关系。

但这个函数并不简单:

当key存在时,返回其对应的value的引用。

当key不存在时,在map中插入key,并给value默认值,然后返回value的引用。

所以map中的"[]"可以说是"查找,修改,插入"三位一体。

这是由于operator[]的内部实现是基于insert函数完成的:

// operator[]的内部实现
mapped_type& operator[] (const key_type& k)
{
    // 1、如果k不在map中,insert会插⼊k和mapped_type默认值,同时[]返回结点中存储
    //mapped_type值的引⽤,那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能

    // 2、如果k在map中,insert会插⼊失败,但是insert返回pair对象的first是指向key结点的
    //迭代器,返回值同时[]返回结点中存储mapped_type值的引⽤,所以[]具备了查找+修改的功能

    pair<iterator, bool> ret = insert({ k, mapped_type() });
    iterator it = ret.first;
    return it->second;
}

 4.2 multimap

基本与map相同,但是支持插入相同的数据,由此而引发的变化还有:

1. insert一定成功,插入函数(1)的返回值不再是pair而只有iterator。

2. count返回数据在map中的个数。

3. 如果有多个相同的值,无论是删除还是查找,都是对中序遍历的第一个进行操作。

4. 不再支持operator[],因为同一个key存在多组值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/882302.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

U盘格式化了怎么办?这4个工具能帮你恢复数据。

如果你思维U盘被格式化了&#xff0c;也不用太过担心&#xff0c;其实里面的数据并没有被删除&#xff0c;只是被标记为了可覆盖的状态。只要我们及时采取正确的数据恢复措施&#xff0c;就有很大的机会可以将数据找回。比如使用专业得的数据恢复软件&#xff0c;我也可以跟大家…

缓存的思考与总结

缓存的思考与总结 什么是缓存缓存命中率数据一致性旁路模式 Cache aside双写模式直写模式 write through异步写 Write Behind 旁路和双写 案例 新技术或中间的引入&#xff0c;一定是解决了亟待解决的问题或是显著提升了系统性能&#xff0c;并且这种改变所带来的增幅&#xff…

python新手的五个练习题

代码 # 1. 定义一个变量my_Number,将其设置为你的学号&#xff0c;然后输出到终端。 my_Number "20240001" # 假设你的学号是20240001 print("学号:", my_Number) # 2. 计算并输出到终端:两个数(例如3和5)的和、差、乘积和商。 num1 3 num2 5 print(&…

nodejs基于vue电子产品商城销售网站的设计与实现 _bugfu

目录 技术栈具体实现截图系统设计思路技术可行性nodejs类核心代码部分展示可行性论证研究方法解决的思路Express框架介绍源码获取/联系我 技术栈 该系统将采用B/S结构模式&#xff0c;开发软件有很多种可以用&#xff0c;本次开发用到的软件是vscode&#xff0c;用到的数据库是…

论文集搜索网站-dblp 详细使用方法

分享在dblp论文集中的两种论文搜索方式&#xff1a;关键字搜索&#xff0c;指定会议/期刊搜索。 关键字搜索 进入dblp官方网址dblp: computer science bibliography&#xff0c;直接在上方搜索栏&#xff0c;搜索关键字&#xff0c;底下会列出相关论文。 指定会议/期刊搜索 …

三菱FX5U PLC故障处理(各种出错的内容、原因及处理方法进行说明。)

对使用系统时发生的各种出错的内容、原因及处理方法进行说明。 故障排除的步骤 发生故障时&#xff0c;按以下顺序实施故障排除。 1.确认各模块是否正确安装或正确配线。 2、确认CPU模块的LED。 3.确认各智能功能模块的LED。(各模块的用户手册) 4、连接工程工具&#xff0c;启…

从数据仓库到数据中台再到数据飞轮:我了解的数据技术进化史

这里写目录标题 前言数据仓库&#xff1a;数据整合的起点数据中台&#xff1a;数据共享的桥梁数据飞轮&#xff1a;业务与数据的双向驱动结语 前言 在当今这个数据驱动的时代&#xff0c;企业发展离不开对数据的深度挖掘和高效利用。从最初的数据仓库&#xff0c;到后来的数据…

828华为云征文|华为Flexus云服务器搭建Cloudreve私人网盘

一、华为云 Flexus X 实例&#xff1a;开启高效云服务新篇&#x1f31f; 在云计算的广阔领域中&#xff0c;资源的灵活配置与卓越性能犹如璀璨星辰般闪耀。华为云 Flexus X 实例恰似一颗最为耀眼的新星&#xff0c;将云服务器技术推向了崭新的高度。 华为云 Flexus X 实例基于…

使用SpringCloud构建可伸缩的微服务架构

Spring Cloud是一个用于构建分布式系统的开源框架。它基于Spring Boot构建&#xff0c;并提供了一系列的工具和组件&#xff0c;用于简化开发分布式系统的难度。Spring Cloud可以帮助开发人员快速构建可伸缩的微服务架构。 要使用Spring Cloud构建可伸缩的微服务架构&#xff0…

对接阿里asr和Azure asr

1&#xff1a;对接阿里asr 1.1&#xff1a;pom <dependency><groupId>com.alibaba.nls</groupId><artifactId>nls-sdk-recognizer</artifactId><version>2.2.1</version> </dependency>1.2&#xff1a;生成token package c…

C++之STL—vector容器基础篇

头文件 #include <vector> //vector容器 #include <algorithm> //算法 基本用法&&概念 vector<int> v; v.push_back(10); vector<int >::iterator v.begin(); v.end(); 三种遍历方式 #include <vector> #include <algorithm>…

基于区块链的相亲交易系统源码解析

随着区块链技术的成熟与发展&#xff0c;其去中心化、不可篡改的特性逐渐被应用于各行各业。特别是在婚恋市场中&#xff0c;区块链技术的应用为相亲平台带来了新的可能性 。本文将探讨如何利用区块链技术构建一个透明、高效的相亲交易系统&#xff0c;并提供部分源码示例。 区…

大模型的实践应用30-大模型训练和推理中分布式核心技术的应用

大家好,我是微学AI,今天给大家介绍一下大模型的实践应用30-大模型训练和推理中分布式核心技术的应用。本文深入探讨了大模型训练和推理中分布式核心技术的应用。首先介绍了项目背景,阐述了大模型发展对高效技术的需求。接着详细讲解了分布式技术的原理,包括数据并行、模型并…

数据转换器——佛朗哥Chater2

【注:本文基于《数据转换器》一书进行学习、总结编撰,适合新手小白进行学习】 目录 2.1 数据转换器类别 2.2 工作条件 2.3 转换器性能参数 2.3.1 基本特性参数 2.4 静态性能参数 2.5 动态性能参数 2.6 数字和开关性能参数 2.1 数据转换器类别 转换器类型可以被分为两…

英飞凌TC3xx -- Bootstrap Loader分析

目录 1.Bootstrap Loaders作用 2.CAN BSL详解 2.1 CAN BSL的时钟系统 2.2 CAN BSL流程 3.小结 英飞凌TC3xx的Platform Firmware章节里&#xff0c;提供了多种启动模式&#xff1a; Internal start from Flash&#xff1a;b111Alternate Boot Mode&#xff1a;b110Generic …

杀软对抗 ---> Perfect Syscall??

好久没更了&#xff0c;今天想起来更新了&#x1f60b;&#x1f60b;&#x1f60b;&#x1f60b; 目录 1.AV && EDR 2.Perfect Syscall&#xff1f;&#xff1f; 3.Truly Perfect ??? 在开始之前先来展示一下这次的免杀效果 1.AV && EDR 360 天擎EDR …

[c++进阶(九)] STL之deque深度剖析

1.前言 本章重点 本章将会着重的介绍deque底层到底是如何实现它能够双向进出的&#xff0c;并且双向进出的消耗率还特别低&#xff0c;并且讲解deque的优缺点。 2.deque的使用 如果没有看我前面两篇文章的&#xff0c;请先看前面两篇文章再来看这篇文章&#xff0c;可以有助于…

手写Spring第三篇,原来Spring容器是使用反射来初始化对象的

上次是不是你小子和大家说你拿来做登记的样品被我收了&#xff0c;然后取豆子的时候就是这个样品的&#xff1f; 今天我来辟一下谣&#xff0c;真的是这样的。这小子的样品确实被我收了&#xff0c;不过这小子没给真东西给我&#xff0c;只给了一个指针&#xff0c;害我宝贝得存…

Git rebase 的使用(结合图与案例)

目录 Git rebase 的使用Git rebase 概念Git rebase 原理rebase和merge的选择 Git rebase 的使用 在 Git 中整合来自不同分支的修改主要有两种方法&#xff1a;merge 以及 rebase Git rebase 概念 **rebase概念&#xff1a;**用来重新应用提交&#xff08;commits&#xff09…

Llama 3.1 技术研究报告-1

llama3模型 现代⼈⼯智能&#xff08;AI&#xff09;系统由基础模型驱动。本⽂介绍了⼀组新的基础模型&#xff0c;称为Llama 3。它是⼀个语⾔模型群&#xff0c;原⽣⽀持多语⾔性、编码、推理和⼯具使⽤。我们最⼤的模型是⼀个密集变换器&#xff0c;有 405B个参数&#xff0…