C++之map，set，multimap，multiset的使用

map，set，multimap，multiset的使用

  • 关联式容器
  • 键值对
  • 树形结构的关联式容器
  • set
    • set介绍
    • set的使用
      • set定义方式
      • set各种操作函数
    • multiset
  • map
    • map的介绍
    • map的使用
      • insert函数
      • find函数
      • erase函数
      • [ ]运算符重载
      • map的迭代器遍历
    • multimap

关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

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

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该英文单词，在词典中就可以找到与其对应的中文含义。

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

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

树形结构的关联式容器

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

set

set介绍

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

注意：

  • 与map/multimap不同，map/multimap中存储的是真正的键值对<key,
  • value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对；
  • set中插入元素时，只需要插入value即可，不需要构造键值对；
  • set中的元素不可以重复(因此可以使用set进行去重)；
  • 使用set的迭代器遍历set中的元素，可以得到有序序列；
  • set中的元素默认按照小于来比较；
  • set中查找某个元素，时间复杂度为：logN；
  • set中的元素不允许修改；
  • set中的底层使用二叉搜索树(红黑树)来实现；

set的使用

set定义方式

方式1：构造某一类型空容器

set<int> s1; //构造int类型的空容器

方式2：拷贝构造某一set类型的容器

set<int> s2(s1); //拷贝构造int类型s1容器的复制品

方式3： 使用迭代器拷贝构造某一段内容。

string str("abcdef");
set<char> s3(str.begin(), str.end()); //构造string对象某段区间的复制品

方式4： 构造一个某类型的空容器，比较方式指定为大于。

set < int, greater<int>> s4; //构造int类型的空容器，比较方式指定为大于

set各种操作函数

普通成员函数：

成员函数指定功能
insert插入指定元素
erase删除指定元素
find查找指定元素
size获取容器中元素的个数
empty判断容器是否为空
clear清空容器
swap交换两个容器中的数据
count获取容器中指定元素值的元素个数

迭代器成员函数：

成员函数指定功能
begin获取容器中第一个元素的正向迭代器
end获取容器中最后一个元素下一个位置的正向迭代器
rbegin获取容器中最后一个元素的反向迭代器
rend获取容器中第一个元素前一个位置的反向迭代器

使用示例：

#include<iostream>
#include<set>
using namespace std;

void Test_set1()
{
	int a[] = { 1, 2, 1, 6, 3, 8, 5 };
	//顺序+去重
	set<int> s1(a, a + sizeof(a) / sizeof(a[0]));//1,2,3,5,6,8
	//逆序+去重
	set<int, greater<int>> s2(a, a + sizeof(a) / sizeof(a[0]));//8,6,5,3,2,1

	set<int>::iterator it = s1.begin();
	//迭代器遍历
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//范围for
	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl;
	//反向迭代器遍历
	set<int>::reverse_iterator rit = s1.rbegin();
	while (rit != s1.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
	//删除
	//1.直接删除
	s1.erase(3);
	//2.使用find查找删除
	set<int>::iterator pos = s1.find(1);
	if (pos != s1.end())
	{
		s1.erase(1);
	}
	//元素1的个数
	cout << s1.count(2) << endl;//1
	//计算有效元素个数
	cout << s2.size() << endl;//4
	//交换两个set容器
	set<int> s3{ 1,2,3,4,5 };
	s1.swap(s3);
}
int main()
{
	Test_set1();
	return 0;
}

multiset

multiset容器与set容器的底层实现一样，都是平衡搜索树（红黑树），其次，multiset容器和set容器所提供的成员函数的接口都是基本一致的，multiset容器和set容器的唯一区别就是，multiset允许键值冗余，即multiset容器当中存储的元素是可以重复的。

void Test_set2()
{
	int a[] = { 2,2,1,1,1,4,4,5,3,6,6 };
	multiset<int> s(a, a + sizeof(a) / sizeof(a[0]));

	for (auto e : s)
	{
		cout << e << " ";//1 1 1 2 2 3 4 4 5 6 6
	}
	cout << endl;
	//1的数量
	cout << s.count(1) << endl;//3
	//删除所有1
	s.erase(1);//2 2 3 4 4 5 6 6

	//查找的是中序遍历的第一个1
	auto pos = s.find(2);
	if (pos != s.end())
	{
		s.erase(pos);
	}
}
int main()
{
	Test_set2();
	return 0;
}

我们要注意的是multiset中find函数查找的是中序遍历的第一个元素，erase函数是将要删除的元素全部删除，count函数是记录此元素的个数。

map

map的介绍

  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通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

方式1： 指定key和value的类型构造一个空容器。

map<int, double> m1; //构造一个key为int类型，value为double类型的空容器

方式2： 拷贝构造某同类型容器的复制品。

map<int, double> m2(m1); //拷贝构造key为int类型，value为double类型的m1容器的复制品

方式3： 使用迭代器拷贝构造某一段内容。

map<int, double> m3(m2.begin(), m2.end()); //使用迭代器拷贝构造m2容器某段区间的复制品

方式4： 指定key和value的类型构造一个空容器，key比较方式指定为大于。

map<int, double, greater<int>> m4; //构造一个key为int类型，value为double类型的空容器，key比较方式指定为大于

map的使用

insert函数

map的插入函数的函数原型如下：

pair<iterator,bool> insert (const value_type& val);

insert函数的参数显示是value_type类型的，实际上value_type就是pair类型的别名：

typedef pair<const Key, T> value_type;
  1. 构建匿名对象进行插入
map<string, string> dict;

dict.insert(pair<string, string>("left", "左边"));
dict.insert(pair<string, string>("right", "右边"));
dict.insert(pair<string, string>("mid", "中间"));
//范围for遍历
for (const auto& e : dict)
{
	cout << e.first << ":" << e.second << endl;
}
cout << endl;
//迭代器遍历
auto it = dict.begin();
while (it != dict.end())
{
	cout << it->first << ":" << it->second << endl;
	it++;
}
  1. 使用nake_pair模板函数进行插入：

在库当中提供以下make_pair函数模板：

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}

map<string, string> dict;

dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("mid", "中间"));
//范围for遍历
for (const auto& e : dict)
{
	cout << e.first << ":" << e.second << endl;
}
cout << endl;
//迭代器遍历
auto it = dict.begin();
while (it != dict.end())
{
	cout << it->first << ":" << it->second << endl;
	it++;
}

insert函数的返回值

insert函数的返回值也是一个pair对象，该pair对象中第一个成员的类型是map的迭代器类型，第二个成员的类型的一个bool类型，具体含义如下：

  • 若待插入元素的键值key在map当中不存在，则insert函数插入成功，并返回插入后元素的迭代器和true。
  • 若待插入元素的键值key在map当中已经存在，则insert函数插入失败，并返回map当中键值为key的元素的迭代器和false。

find函数

map的查找函数的函数原型如下：

iterator find (const key_type& k);

map的查找函数是根据所给key值在map当中进行查找，若找到了，则返回对应元素的迭代器，若未找到，则返回容器中最后一个元素下一个位置的正向迭代器。

map<string, string> dict;

dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("mid", "中间"));

map<string, string>::iterator pos = dict.find("left");
if(pos != dict.end())
{
	cout << pos->second << endl;//左边
}

erase函数

map的删除函数的函数原型如下：

//删除函数1
size_type erase (const key_type& k);
//删除函数2
void erase(iterator position);

我们既可以根据key值删除指定元素，也可以根据迭代器删除指定元素，若是根据key值进行删除，则返回实际删除的元素个数。

map<string, string> dict;

dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("mid", "中间"));

dict.erase("left");

map<string, string>::iterator pos = dict.find("right");
if (pos != dict.end())
{
	dict.erase("right");
}

[ ]运算符重载

[ ]运算符重载函数原型如下：

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

[ ]运算符重载函数的参数就是一个key值，而这个函数的返回值如下：

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

实际上[ ]运算符重载实现的逻辑实际上就是以下三个步骤：

  1. 调用insert函数进行键值对插入；
  2. 拿出insert函数获取到的迭代器；
  3. 返回该迭代器位置的元素值value。
V& operator[](const K& key)
{
	//调用insert函数进行键值对插入
	pair<iterator, bool> ret = insert(make_pair(key, V());
	//拿出insert函数获取到的迭代器并返回该迭代器位置的元素值value
	return ret.first->second;
}
  • map中没有这个key，返回value的引用；（查找+修改）
  • map中有这个key，会插入一个pair(key, V()），返回value的引用；（插入+修改）
map<string, string> dict;

dict["left"];
dict["left"] = "左边";
dict["right"] = "右边";
dict["mid"] = "中间";

for (auto& e : dict)
{
	cout << e.first << ":" << e.second << endl;
}

在这里插入图片描述

map的迭代器遍历

map当中迭代器相关函数如下：

成员函数功能
begin获取容器中第一个元素的正向迭代器
end获取容器中最后一个元素下一个位置的正向迭代器
rbegin获取容器中最后一个元素的反向迭代器
rend获取容器中第一个元素前一个位置的反向迭代器
map<string, string> dict;

dict.insert(pair<string, string>("left", "左边"));
dict.insert(pair<string, string>("right", "右边"));
dict.insert(pair<string, string>("mid", "中间"));
//范围for遍历
for (const auto& e : dict)
{
	cout << e.first << ":" << e.second << endl;//left:左边  mid:中间  right:右边
}
cout << endl;
//迭代器遍历
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
	cout << it->first << ":" << it->second << endl;//left:左边  mid:中间  right:右边
	it++;
}
cout << endl; 
//反向迭代器遍历
map<string, string>::reverse_iterator rit = dict.rbegin();
while (rit != dict.rend())
{
	cout << rit->first << ":" << rit->second << endl;//right:右边  mid:中间  left:左边
	rit++;
}

map的其他成员函数
除了上述成员函数外，set当中还有如下几个常用的成员函数：

成员函数功能
size获取容器中元素的个数
empty判断容器是否为空
clear清空容器
swap交换两个容器中的数据
count获取容器中指定key值的元素个数

multimap

multimap容器与map容器的底层实现一样，也都是平衡搜索树（红黑树），其次，multimap容器和map容器所提供的成员函数的接口都是基本一致的，multimap容器和map容器的区别与multiset容器和set容器的区别一样，multimap允许键值冗余，即multimap容器当中存储的元素是可以重复的。

multimap<string, string> dict;

dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("mid", "中间"));

for (auto& e : dict)
{
	cout << e.first << ":" << e.second << endl;
	//left:左边  left:左边  mid:中间  right:右边
}
cout << endl;

//left出现次数
cout << dict.count("left") << endl;//2

//删除全部left
dict.erase("left");
for (auto& e : dict)
{
	cout << e.first << ":" << e.second << endl;//mid:中间  right:右边
}

由于multimap容器允许键值冗余，因此两个容器中成员函数find和count的意义也有所不同：

成员函数find功能
map对象返回值为键值为key的元素的迭代器
multimap对象返回底层搜索树中序的第一个键值为key的元素的迭代器
成员函数count功能
map对象键值为key的元素存在则返回1，不存在则返回0（find成员函数可代替）
multimap对象返回键值为key的元素个数（find成员函数不可代替）

我们还需要注意的是在multimap中是没有[]运算符重载的，因为multimap允许键值冗余，使用[]就会引发歧义。

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

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

相关文章

VC++使用Microsoft Speech SDK进行文字TTS朗读

VC++使用Microsoft Speech SDK进行文字TTS朗读

Microsoft Speech SDK下载地址 https://www.microsoft.com/en-us/download/details.aspx?id10121 需要msttss22L.exe、SpeechSDK51.exe、SpeechSDK51LangPack.exe三个&#xff0c;下载后全部安装 使用VS2005建立一个win32控制台项目 朗读"hello word"、中文“你好”…
阅读更多...
弯道超车必做好题集锦三（C语言编程题）

弯道超车必做好题集锦三（C语言编程题）

目录 前言&#xff1a; 1.单词倒排 方法1&#xff1a;scanf匹配特定字符法 方法2&#xff1a; 双指针法 2.统计每个月兔子的总数 方法1&#xff1a;斐波那契数列 方法2&#xff1a;斐波那契的递归 3.珠玑妙算 方法&#xff1a;遍历 4.寻找奇数&#xff08;单身狗&#…
阅读更多...
Linux - Docker 安装使用 常用命令 教程

Linux - Docker 安装使用 常用命令 教程

Docker 官方文档地址: Get Started | Docker 中文参考手册: https://docker_practice.gitee.io/zh-cn/ 1.什么是 Docker 1.1 官方定义 最新官网首页 # 1.官方介绍 - We have a complete container solution for you - no matter who you are and where you are on your contain…
阅读更多...
VMware 安装 Centos7 超详细过程

VMware 安装 Centos7 超详细过程

CentOS系统&#xff0c;安装教程可参考以下&#xff1a; 哪些模型需要在Linux下运行&#xff0c;需提前预装Linux系统呢&#xff0c;评论区讨论吧 比如Noah-MP 5.0模型 1.软硬件准备 软件&#xff1a;推荐使用 VMware&#xff0c;我用的是 VMware 12 镜像&#xff1a;CentO…
阅读更多...
15. 查看开源项目

15. 查看开源项目

15.1 parser.add_argument ① 像运行Tensorboar一样&#xff0c;在Terminal终端&#xff0c;可以命令运行.py文件。 ② 如下图所示&#xff0c;Terminal终端运行.py文件时&#xff0c;--变量 后面的值是给变量进行赋值&#xff0c;赋值后再在.py文件中运行。例如 ./datasets/…
阅读更多...
【炼气境】HashMap原理以及如何使用

【炼气境】HashMap原理以及如何使用

系列文章目录 文章目录 系列文章目录前言1、数据结构2、工作原理3、当两个对象的 hashCode 相同会发生什么&#xff1f;4、你知道 hash 的实现吗&#xff1f;为什么要这样实现&#xff1f;5、为什么要用异或运算符&#xff1f;6、HashMap 的 table 的容量如何确定&#xff1f;l…
阅读更多...
WPF实战项目十三（API篇）：备忘录功能api接口、优化待办事项api接口

WPF实战项目十三（API篇）：备忘录功能api接口、优化待办事项api接口

1、新建MenoDto.cs /// <summary>/// 备忘录传输实体/// </summary>public class MemoDto : BaseDto{private string title;/// <summary>/// 标题/// </summary>public string Title{get { return title; }set { title value; OnPropertyChanged();…
阅读更多...
3.（Python数模）整数规划问题

3.（Python数模）整数规划问题

Python解决整数规划问题 在实际生活中&#xff0c;线性规划中的变量不可能都是连续的值&#xff0c;比如不可能计算出0.5个人&#xff0c;0.5只牛羊&#xff0c;往往需要根据题目需要或者实际问题来调整决策变量的变量类型 Continuous’ 表示连续变量&#xff08;默认值&…
阅读更多...
Java的23种设计模式

Java的23种设计模式

Java的23种设计模式 一、创建型设计模式1.单例模式 singleton1.1.静态属性单例模式1.2 静态属性变种1.3 基础的懒汉模式1.4 线程安全的懒加载单例1.5 线程安全的懒加载 单例-改进1.6 双重检查锁1.7 静态内部类1.8 枚举单例1.9 注册表单例 2.工厂方法模式 factory3.抽象工厂模式…
阅读更多...
工具分享 | PDF文档解析工具PyMuPDF

工具分享 | PDF文档解析工具PyMuPDF

1 需求描述 最近工作需要从PDF文档中按照章节解析出对应的文本和图片(后续可能还会有表格)&#xff0c;经过调研&#xff0c;找到了一个功能强大的解析工具MuPDF&#xff0c;对应的Python包是PyMuPDF。本篇博客记录使用它来实现具体功能。 官方文档&#xff1a;https://pymupd…
阅读更多...
Git企业开发控制理论和实操-从入门到深入（四）｜Git的远程操作｜Gitee

Git企业开发控制理论和实操-从入门到深入（四）｜Git的远程操作｜Gitee

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…
阅读更多...
ubuntu入门01——windows上直接部署linux(WSL)

ubuntu入门01——windows上直接部署linux(WSL)

win10安装参考如下教程&#xff1a; 旧版 WSL 的手动安装步骤 | Microsoft Learn 说明&#xff1a;该文档是我按如上教程安装使用Ubuntu写的回顾&#xff0c;家人们参考官方教程更妙。 1.启用适用于Linux的wundows子系统 2.启用虚拟机功能 dism.exe /online /enable-feat…
阅读更多...
开源电子合同签署平台小程序源码 在线签署电子合同小程序源码 合同在线签署源码

开源电子合同签署平台小程序源码 在线签署电子合同小程序源码 合同在线签署源码

聚合市场上各类电子合同解决方案商&#xff0c;你无需一个一个的对接电子合同厂商&#xff0c;费时&#xff0c;费力&#xff0c;因为这个工作我们已经做了适配&#xff0c;你只需要一个接口就能使用我们的所有服务商&#xff0c;同时你还可以享受我们的接口渠道价格。 Mini-C…
阅读更多...
LeetCode 23 合并 K 个升序链表

LeetCode 23 合并 K 个升序链表

LeetCode 23 合并 K 个升序链表 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;https://leetcode.cn/problems/merge-k-sorted-lists/description/ 博主Github&#xff1a;https://github.com/GDUT-Rp/LeetCode 题目&#xff1a; 给你一个链表数组…
阅读更多...
A 股个股资金流 API 数据接口

A 股个股资金流 API 数据接口

A 股个股资金流 API 数据接口 全量股票资金流数据&#xff0c;全量A股数据&#xff0c;最长30日历史数据 1. 产品功能 支持所有A股资金流数据查询&#xff1b;每日定时更新数据&#xff1b;支持多达 30 日历史数据查询&#xff1b;超高的查询效率&#xff0c;数据秒级返回&am…
阅读更多...
【LeetCode75】第四十一题 二叉搜索树中的搜索

【LeetCode75】第四十一题 二叉搜索树中的搜索

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一个搜索二叉树&#xff0c;让我们找出节点值等于目标的节点并返回出去。 首先我们可以直接遍历整棵二叉树&#xff0c;找到值…
阅读更多...
基于大语言模型知识问答应用落地实践 – 知识库构建（下）

基于大语言模型知识问答应用落地实践 – 知识库构建（下）

上篇介绍了构建知识库的大体流程和一些优化经验细节&#xff0c;但并没有结合一个具体的场景给出更细节的实战经验以及相关的一些 benchmark 等&#xff0c;所以本文将会切入到一个具体场景进行讨论。 目标场景&#xff1a;对于 PubMed 医疗学术数据中的 1w 篇文章进行知识库构…
阅读更多...
PO设计模式是selenium自动化测试中最佳的设计模式之一

PO设计模式是selenium自动化测试中最佳的设计模式之一

Page Object Model&#xff1a;PO设计模式是selenium自动化测试中最佳的设计模式之一&#xff0c;主要体现在对界面交互细节的封装&#xff0c;也就是在实际测试中只关注业务流程就OK了传统的设计中&#xff0c;在新增测试用例之后&#xff0c;代码会有以下几个问题&#xff1a…
阅读更多...
python爬虫实战(5)--获取小破站热榜

python爬虫实战(5)--获取小破站热榜

1. 分析地址 打开小破站热榜首页&#xff0c;查看响应找到如下接口地址 2. 编码 定义请求头 拿到标头 复制粘贴&#xff0c;处理成json 处理请求头代码如下: def format_headers_to_json():f open("data.txt", "r", encoding"utf-8") # 读…
阅读更多...
Qt无边框青绿色主题

Qt无边框青绿色主题

收费产品&#xff0c;学生党、闹眼子党勿扰 收费金额&#xff1a;500元 1 概述 最近因项目需要&#xff0c;写了一个炫酷的青绿色、无边框界面&#xff0c;和3DSMax的界面有点类似。 2 截图 首先看看3DSMax的界面 不知道大家看出来没&#xff0c;这个ui其实很简单&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023