C++STL之set与map的使用

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

本文目录

前言

关于C++的STL库相信大家已经知道是什么了也正是因为有了它才能让C++变得如此方便今天我们就来看一下STL库中map与set的使用方法。

一、关联式容器

我们之前已经接触过STL中的部分容器比如vector、list、deque等这些容器称为序列式容器因为其底层为线性的数据结构里面存储的是元素本身那么什么是关联式容器呢
关联式容器也是用来存放数据的与序列式容器不同的是里面存储的是 <key,value> 结构的键值对在数据检索是比序列式容器效率更高。

二、键值对(pair)

用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。
在这里插入图片描述

pair对象的构建
在这里插入图片描述

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

根据应用场景的不同STL总共实现了两种不同结构的关联式容器树型结构与哈希结构。树型结构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结构容器中的元素是一个有序的序列。下面我们会依次介绍每一个容器。

1.set

1.1set的介绍

  1. set是按照一定次序存储元素的容器
  2. 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。
    set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。
  3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格排序准则进行排序。
  4. set在底层是用二叉搜索树(红黑树)实现的。
    注意:
  5. 与map/multimap不同map/multimap中存储的是真正的键值对<key, value>set中只放value但在底层实际存放的是由<value, value>构成的键值对。
  6. set中插入元素时只需要插入value即可不需要构造键值对。
  7. set中的元素不可以重复(因此可以使用set进行去重)。
  8. 使用set的迭代器遍历set中的元素可以得到有序序列
  9. set中的元素默认按照小于来比较
  10. set中查找某个元素时间复杂度为 l o g 2 n log_2 n log2​n
  11. set中的元素不允许修改
  12. set中的底层使用二叉搜索树(红黑树)来实现

1.2set的使用

1.2.1set的模板参数列表

在这里插入图片描述

1.2.2set的构造

(1)构造空的set
set<int> s; //注意一定指明存储元素的类型
(2)以数组的形式构造
set<int> s = { 0,2,5,1,4,0,6 };
(3)用迭代器区间进行构造
int a[] = { 0,1,5,1,3,6,7 };
set<int> s(a, a + sizeof(a) / sizeof(int));
(4)拷贝构造
set<int> s = { 0,2,5,6,7 };
set<int> copy(s);

1.2.3set的迭代器

(1)iterator begin()

返回set中起始位置元素的迭代器

set<int> s = { 6,5,4,3,2,1 };
//插入数据后默认顺序为1 2 3 4 5 6 
set<int>::iterator it = s.begin();
cout << *it << endl;
//最后输出的结果为1
(2)iterator end()

返回set中最后一个元素的后面的迭代器

set<int> s = { 6,5,4,3,2,1 };
//插入数据后默认顺序为1 2 3 4 5 6 
set<int>::iterator it = s.end();
cout << *(it - 1) << endl;
//最后输出的结果为6

后面的迭代器的用法与前面的用法相同我们就不再举例了。

(3)const_iterator cbegin() const

返回set中起始位置元素的const迭代器

(4)const_iterator cend() const

返回set中最后一个元素后面的const迭代器

(5)reverse_iterator rbegin()

返回set第一个元素的反向迭代器即set的最后一个元素

(6)reverse_iterator rend()

返回set中最后一个元素后面的反向迭代器
注意: 这里经过特殊的处理下一个元素并不是我们所理解的第一个元素的下一个元素。
在这里插入图片描述
这样进行处理的话我们的使用迭代器遍历数据的操作就和普通迭代器一致了不同的迭代器以相同的做法达到相同的目的。后面遍历以迭代器遍历数据的时候我们还会提及。

(7)const_reverse_iterator crbegin() const

返回set第一个元素的const反向迭代器即set的最后一个元素

(8)const_reverse_iterator crend() const

返回set中最后一个元素后面的const反向迭代器

1.2.4set的输出

(1)范围for输出
set<int> s = { 1,0,9,3,2 };
for (auto e : s)
{
	cout << e << " ";
}
//输出结果:0 1 2 3 9

注意: set的输出结果是有序的这是因为它的底层结构为红黑树的原因可以自动排序自动去重所以在set中是没有重复的元素的。
set天生 去重 + 排序

set<int> s = { 1,0,1,0,9,3,2,9,3 };
for (auto e : s)
{
	cout << e << " ";
}
//最后的输出结果为: 0 1 2 3 9
(2)通过正向迭代器遍历数据
set<int> s = { 6,5,4,3,2,1 };
set<int>::iterator it = s.begin();
while (it != s.end())
{
	cout << *it << " ";
	it++;
}
//1 2 3 4 5 6
cout << endl;

相信这个对于大家来说都没有问题

(3)通过反向迭代器遍历数据
set<int> s = { 6,5,4,3,2,1 };
//1 2 3 4 5 6
set<int>::reverse_iterator it = s.rbegin();
while (it != s.rend())
{
	cout << *it << " ";
	it++;
}
//6 5 4 3 2 1
cout << endl;

但是不知道这个操作大家会怎么去理解。
错误思路
很多人会想rbegin()返回的就是最后一个元素的位置rend()返回的是第一元素前一个位置所以我要让it–来实现遍历所有元素的目的这样是不正确的并且会报出错误。
正确思路
因为我们的语法操作要实现与使用begin()end()时的一致所以在这里it也是进行++即it++我们要把整个集合反过来看即:6 5 4 3 2 1反过来后rbegin()就可以理解为begin()rend()就可以理解为end(),其他的操作与正式遍历一致这样就很好理解了it++也就不成问题。

补充知识:(4)数据的排序

这里涉及到了我们前面所学的仿函数less和greaterless是按照升序进行排序greater是按照降序进行排序
1.set默认排升序即less我们在构造set时如果没有给定仿函数就以升序的形式输出数据
2.如果想排降序的话就要在构造set对象时显示传仿函数

set<int,greater<int>> s = {0,1,2,3,4,5};

这样输出数据是就是降序

1.2.5set的容量

(1)bool empty() const

检测set是否为空空返回true否则返回false

(2)size_t size() const

返回set中有效元素的个数

1.2.6set的修改操作

(1)插入操作

insert()函数,只能用insert函数插入数据

set<int> s;
s.insert(4);
s.insert(2);
(2)删除操作
1.删除方法一:直接删除数据
int main()
{
	int a[] = { 0,1,5,1,3,6,7 };
	set<int> s(a, a + sizeof(a) / sizeof(int));
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		//*it = 10;//注意在set中无法赋值否则会破坏树
		cout << *it << " ";
		it++;
	}
	//0 1 3 5 6 7
	cout << endl;
	//删除方法1:
	s.erase(3);//可以直接删除
	for (auto e : s)
	{
		cout << e << " ";
	}
	//0 1 5 6 7
	cout << endl;

	s.erase(30);//没有该元素删除操作不会执行
	for (auto e : s)
	{
		cout << e << " ";
	}
	//0 1 5 6 7
	cout << endl;
	return 0;
}
2.通过迭代器删除数据

1.错误删除方式

int main()
{
	int a[] = { 0,1,5,1,3,6,7 };
	set<int> s(a, a + sizeof(a) / sizeof(int));
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	//0 1 3 5 6 7
	cout << endl;
	//通过迭代器删除数据
	//但是以这种方式查找没有的数据的位置时返回的是end(),后面删除就会出错。所以不能直接删除
	set<int>::iterator it1 = s.find(20);
	//不进行判断直接对找到的位置进行删除
	s.erase(it1);
	for (auto e : s)
	{
		cout << e << " ";
	}
	//0 1 3 5 6 7
	cout << endl;
	return 0;
}

在这里插入图片描述

如果不加判断条件就会报出这样的错误。
2.正确删除方式

int main()
{
	int a[] = { 0,1,5,1,3,6,7 };
	set<int> s(a, a + sizeof(a) / sizeof(int));
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	//0 1 3 5 6 7
	cout << endl;
	set<int>::iterator it1 = s.find(20);
	if (it1 != s.end())//这里要先要判断一下是否有该数据
	{
		//存在该数据就会执行删除操作
		s.erase(it1);
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	//0 1 3 5 6 7
	cout << endl;
	return 0;
}
3.迭代器删除操作与直接删除操作对比

为什么第一种直接删除操作没有要删除的元素时不报错那是因为直接删除操作就类似于我们所说的正确的迭代器删除元素的方法相当于自己加了if判断语句所以才没有报出错误。

2.multiset

既然已经有set容器了那么multset又是用来干什么的呢
multset允许键值冗余也就是里面可以存相同的数据元素。在其他的一些函数和操作方面multiset与set是一致的下面我们直接看他比较特殊的性质
直接通过代码和测试结果查看

int main()
{
	//multiset允许键值冗余
	int a[] = { 3,1,2,1,6,3,8,3,5,3 };
	multiset<int> s(a, a + sizeof(a) / sizeof(int));
	//排序但不去重
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << s.count(1) << endl;//输出2,有两个1
	auto pos = s.find(3);//如果有多个值返回中序的第一个
	while (pos != s.end())
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;
	s.erase(3);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	pos = s.find(1);//找到第一个1的位置然后将第一个1删除
	if (pos != s.end())
	{
		s.erase(pos);
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	return 0;
}

在这里插入图片描述
通过上面的代码和结果的分析我们就可以很好的了解multiset的使用了。

3.map

3.1map的介绍

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

3.2map的使用

3.2.1map的模板参数说明

在这里插入图片描述

3.2.2map的构造

构造空的map

map<string,string> dict;

3.2.3map的修改操作

(1)插入操作

pair<iterator,bool> insert(const value_type& x)
在map中插入键值对注意x是一个键值对返回值也是键值对:iterator代表插入元素的位置bool代表是否插入成功这里insert函数的设计与后面map可以使用operator[]有密切关系

map<string, string> dict;//创建一个键值对为<string,string>类型的map
//插入方式一
pair<string,string> kvl("sort","排序");//创建一个结构体隐式类型转换
dict.insert(kvl);//可以直接将kvl插入
//也可以使用下面的匿名对象将值插入dict对象中
dict.insert(pair<string, string>("test", "测试"));
//插入方式二
//如果感觉pair<string, string>太长就可以将其进行typedef但是这个其实也不方便毕竟还要typedef一下
typedef pair<string, string> DictKV;
dict.insert(DictKV("string", "字符串"));
插入方式三(平时都习惯这么定义)
dict.insert(make_pair("left", "左边"));
(2)删除操作

1.size_type erase(const key_type& x)
删除键值为x的元素

map<string, string> dict;
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
//这里插入元素以后会按照属于key的比较方式进行排序
dict.erase("left");//删除key为left的元素
dict.erase("string");//删除key为string的元素

2.void erase(iterator position)
删除position位置上的元素

map<string, string> dict;
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
map<string, string>::iterator it = dict.find("left");
dict.erase(it);//删除it位置的元素

3.void erase(iterator first,iterator last)
删除[first,last)区间中的元素

map<string, string> dict;
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
dict.erase(dict.begin(),dict.end());//直接删除全部的元素
(3)交换操作

void swap (map& x)
交换两个map中的元素

map<string, string> dict1;
dict1.insert(make_pair("left", "左边"));
dict1.insert(make_pair("right", "右边"));
map<string, string> dict2;
dict2.insert(make_pair("sort", "排序"));
dict2.insert(make_pair("string", "字符串"));
//交换两个map中的元素
dict1.swap(dict2);
(4)清空元素操作

void clear()
将map中的元素清空

(5)查找元素操作

iterator find(const key_type& x)
在map中查找key为x的元素找到返回该元素的位置的迭代器否则返回end()

(5)个数记录(不常用)

size_type count(const key_type& x) const
返回key为x的键值在map中的个数注意map中key是唯一的因此该函数的返回值要么为0要么为1因此也可以用该函数来
检测一个key是否在map中。

3.2.4map的迭代器

(1)begin()和end()

begin:首元素的位置,end:最后一个元素的下一个位置

(2)cbegin()和cend()

与begin和end意义相同但cbegin和cend所指向的元素不能修改

(3)rbegin()和rend()

反向迭代器rbegin在end位置rend在begin位置其
++和–操作与begin和end操作移动相反

(4)crbegin()和crend()

与rbegin和rend位置相同操作相同但crbegin和crend所
指向的元素不能修改

以迭代器的方式遍历map中的元素

map<string, string> dict;
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
map<string, string>::iterator it = dict.begin();
//元素访问方式一(但是一般不这样使用)
while (it != dict.end())
{
	
	cout << (*it).first << ":" << (*it).second << endl;
	//*it为结构体然后 以结构体.成员变量的形式访问
	it++;
}
cout << endl;

//元素访问方式二(一般使用方式)
it = dict.begin();
while (it != dict.end())
{
	cout << it->first << ":" << it->second << endl;
	//it->first 其实是 it->->first(it->返回的是结构体指针但是这里编译器进行了优化)
	it++;
}
cout << endl;

3.2.5map的容量

bool empty() const
检测map中的元素是否为空是返回true否则返回false
size_type size() const
返回map中有效元素的个数

3.2.6map中元素的访问

mapped_type& operator[] (const key_type& k)
返回key对应的value
map的精髓就在operator[]这里下面我们一起来看看他的功能他远远没有表面看起来这么简单。
先来看一下该函数的介绍
在这里插入图片描述
下面我们来看看插入数据时的几种情景
在这里插入图片描述
上面的这几种情景是如何产生的呢其实与该函数介绍中的最后一行有关我将他单独拿了出来
在这里插入图片描述
这里可以看到该函数与insert函数有关系我们还要再分析insert函数
在这里插入图片描述
下面我们分析整个函数流程
在这里插入图片描述
最后我们来看一下这里的[]有什么用处或者说是他的应用场景下面我会就举一个例子但是用不同的方法实现将二者对比一下
例:给一个水果的数组我们要统计该数组中各种水果出现的次数
string a[] = { “苹果”,“香蕉”, “西瓜”, “西瓜”, “苹果”, “苹果”, “苹果”, “香蕉”, “苹果” };

string a[] = { "苹果","香蕉", "西瓜", "西瓜", "苹果", "苹果", "苹果", "香蕉", "苹果" };
map<string, int> CountMap;
for (auto& str : a)
{
	map<string, int>::iterator it = CountMap.find(str);
	if (it != CountMap.end())
	{
		it->second++;
	}
	else
	{
		CountMap.insert(make_pair(str, 1));
	}
}
map<string, int>::iterator it1 = CountMap.begin();
while (it1 != CountMap.end())
{
	cout << it1->first << ":" << it1->second << endl;
	it1++;
}

最后的输出结果
在这里插入图片描述
上面的代码看上去还可以但是有了operator[]后还有更简洁的代码实现起来更加方便。

string a[] = { "苹果","香蕉", "西瓜", "西瓜", "苹果", "苹果", "苹果", "香蕉", "苹果" };
map<string, int> CountMap;
for (auto& e : a)
{
	//1.e不在CountMap中插入pair(strint()),然后对返回的次数++
	//2.str在CountMap中返回value(次数)的引用次数++
	CountMap[e]++;
}
map<string, int>::iterator it = CountMap.begin();
while (it != CountMap.end())
{
	cout << it->first << ":" << it->second << endl;
	it++;
}

最后的输出结果:
在这里插入图片描述
我们可以看到第二种代码实现起来更加方便简洁这就是operator[]的作用。
注意 在元素访问时有一个与operator[]类似的操作at()(该函数不常用)函数都是通过key找到与key对应的value然后返回其引用不同的是当key不存在时operator[]用默认value与key构造键值对然后插入返回该默认valueat()函数直接抛异常。

4.multimap

multimap与map的函数的作用都是相似的,就和multiset与set之间的关系一样map中的key是唯一的而multimap中key是可以重复的。并且在multimap中没有重载operator[]操作 因为在该容器中key的值是可以重复的这也就说明一个key值可能会对应多个value所以不会实现该函数。

总结

关于C++中的map与set我们就讲解到这里了map与set都是很重要的容器大家下来后一定要自己动手去敲一敲代码加深一下印象同时也有利于后面的使用如果文章中有错误大家可以在评论区指出我看到后一定会第一时间修改最后如果你觉得本章内容对你有用的话就给一波三连吧你们的支持就是我写博客最大的动力。

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：MD5加密

下一篇：电脑重装系统后键盘失灵解决方法步骤

“C++STL之set与map的使用” 的相关文章

C++11 std::function 基础用法1年前 (2023-02-02)
C++基于STL的演讲比赛流程管理系统1年前 (2023-02-02)
c++、php、java、python、javascript对比，同一功能用5种编程语言写一遍，谁才是最好的编程语言？_c++ java php1年前 (2023-02-02)
P1019题解 单词接龙（c++）1年前 (2023-02-02)
（黑马C++）L09 C++类型转换 异常 输入输出流1年前 (2023-02-02)
C/C++ 调用规则1年前 (2023-02-02)
106、【树与二叉树】leetcode ——501. 二叉搜索树中的众数：双指针法+哈希表法（C++版本）1年前 (2023-02-02)
C++学习笔记——类和对象1年前 (2023-02-02)
二分查找----C/C++1年前 (2023-02-02)
c++-类成员函数-常用运算-取成员函数地址-动态调用-申明1年前 (2023-02-02)

阿里云国际版