map和set的具体用法 【C++】

这篇具有很好参考价值的文章主要介绍了map和set的具体用法 【C++】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

关联式容器

关联式容器里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。比如:set、map、unordered_set、unordered_map等

注意: C++STL当中的stack、queue和priority_queue属于容器适配器,它们默认使用的基础容器分别是deque、deque和vector

键值对

键值对是用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量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)
	{
	}
};

set

1、set是按照一定次序存储元素的容器,使用set的迭代器遍历set中的元素,可以得到有序序列

2、set当中存储元素的value都是唯一的,不可以重复,因此可以使用set进行去重

3、与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放value,但在底层实际存放的是由<value, value>构成的键值对,在set容器中插入元素时,只需要插入value即可,不需要构造键值对

4、set中的元素不能被修改,set在底层是用二叉搜索树来实现的,若是对二叉搜索树当中某个结点的值进行了修改,那么这棵树将不再是二叉搜索树

5、在内部,set中的元素总是按照其内部比较对象所指示的特定严格弱排序准则进行排序。当不传入内部比较对象时,set中的元素默认按照小于来比较

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

7、set在底层是用平衡搜索树(红黑树)实现的,所以在set当中查找某个元素的时间复杂度为logN

set的定义方式

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

//拷贝构造int类型s1
set<int> s2(s1); 
string str("abcdef");

//拷贝string
set<char> s3(str.begin(), str.end()); 

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

set的使用

void Testset()
{
	 //去重
	set<int> s;
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(3);
	s.insert(2);
	s.insert(2);
	s.insert(3);
	//遍历方式一

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//删除方式一
	s.erase(3);
	//遍历方式二

	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//删除方式二, 正向迭代器遍历 
	set<int>::iterator pos = s.find(1);
	if (pos!=s.end())
	{
		s.erase(pos);
	}
	//遍历方式三
	set<int>::reverse_iterator rit = s.rbegin();
	while (rit != s.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
	//容器中值为2的个数 
	cout<<s.count(2);
	cout << s.size();
	s.clear();
	cout << s.empty();

}

void TestmultiSet()
{
	//可以重复 
	multiset<int> m;
	m.insert(3);
	m.insert(5);
	m.insert(8);
	m.insert(7);
	m.insert(7);
	m.insert(9);
	m.insert(7);
	for (auto e : m)
	{
		cout << e << "";
	}
	//find 
	//set<int> s;
	//s.insert(1);
	//s.insert(4);
	//s.insert(3);
	//s.insert(3);
	//s.insert(2);
	//s.insert(2);
	//s.insert(3);
	//if (s.find(3) != s.end())
	//{
	//	cout << "找到了" << " ";
	//}
	//else
	//{
	//	cout << "找不到" << " ";
	//}
	auto pos = m.find(7);//返回中序中第一个7
	while (pos != m.end())
	{
		cout << *pos << " ";
		pos++;
	}
	cout << endl;
	cout << m.count(7) << endl;
	auto ret = m.equal_range(17);
	auto itlow = ret.first;
	auto itup = ret.second;
	//[itlow , itup) 左闭右开 左边界是第一个7,右边界是比7大的,才能完全删除所有的7
	cout << *itlow<<endl;
	cout << *itup<<endl;
	m.erase(itlow, itup);//?
	for (auto e : m)
	{
		cout << e << " ";
	}
	cout << endl;
	
}
void Testset2()
{
	set<int> s;
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(3);
	s.insert(2);
	s.insert(2);
	s.insert(3);
	//交换两个容器的数据 
	set<int> tmp{ 11,22,33,44 };
	s.swap(tmp);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{
Testset();
TestmultiSet();
Testset2();
return 0 ;
}

multiset

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

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

int main()
{
	multiset<int> ms;
	//插入元素(允许重复)
	ms.insert(1);
	ms.insert(4);
	ms.insert(3);
	ms.insert(3);
	ms.insert(2);
	ms.insert(2);
	ms.insert(3);
	for (auto e : ms)
	{
		cout << e << " ";
	}
	cout << endl; //1 2 2 3 3 3 4
	return 0;
}

map和set的具体用法 【C++】,c++,java,开发语言

map

1、map是关联式容器,它按照特定的次序(按照key来比较)存储键值key和值value组成的元素,使用map的迭代器遍历map中的元素,可以得到有序序列。

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

3、map容器中元素的键值key不能被修改,但是元素的值value可以被修改,因为map底层的二叉搜索树是根据每个元素的键值key进行构建的,而不是值value。

4、在内部,map中的元素总是按照键值key进行比较排序的。当不传入内部比较对象时,map中元素的键值key默认按照小于来比较。

5、map容器通过键值key访问单个元素的速度通常比unordered_map容器慢,但map容器允许根据顺序对元素进行直接迭代。

6、map容器支持下标访问符,即在[]中放入key,就可以找到与key对应的value。

7、map在底层是用平衡搜索树(红黑树)实现的,所以在map当中查找某个元素的时间复杂度为logN

map的定义方式

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

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

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

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

insert

map和set的具体用法 【C++】,c++,java,开发语言

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

value_type类型的,实际上value_type就是pair类型的别名:

typedef pair<const Key, T> value_type;

插入元素时,需要用key和value构造一个pair对象,然后再将pair对象作为参数传入insert函数

方式一:匿名对象

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<int, string> m;
	//方式一:调用pair的构造函数,构造一个匿名对象插入
	m.insert(pair<int, string>(2, "two"));
	m.insert(pair<int, string>(1, "one"));
	m.insert(pair<int, string>(3, "three"));
	for (auto e : m)
	{
		cout << "<" << e.first << "," << e.second << ">" << " ";
	}
	cout << endl; //<1,one> <2,two> <3,three>
	return 0;
}

方式二:调用make_pair函数模板插入(常用)

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

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

向make_pair函数传入key和value,该函数模板会根据传入参数类型进行自动隐式推导,最终构造并返回一个对应的pair对象

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<int, string> m;
	//方式二:调用函数模板make_pair,构造对象插入
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	for (auto e : m)
	{
		cout << "<" << e.first << "," << e.second << ">" << " ";
	}
	cout << endl; //<1,one> <2,two> <3,three>
	return 0;
}

insert函数的返回值
map和set的具体用法 【C++】,c++,java,开发语言
总结文档的内容:
insert函数的返回值也是一个pair对象,该pair对象中第一个成员的类型是map的迭代器类型,第二个成员的类型的一个bool类型,具体含义如下:

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

find

map和set的具体用法 【C++】,c++,java,开发语言

iterator find (const key_type& k);

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

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	//获取key值为2的元素的迭代器
	map<int, string>::iterator pos = m.find(2);
	if (pos != m.end())
	{
		cout << pos->second << endl; //two
	}
	return 0;
}

erase

map和set的具体用法 【C++】,c++,java,开发语言
根据key值删除指定元素,也可以根据迭代器删除指定元素,若是根据key值进行删除,则返回实际删除的元素个数。

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<int, string> m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));
	for (auto kv : m)
	{
		cout << kv.first<<" " << kv.second;
	}
	cout << endl;
	//根据key值进行删除
	m.erase(3);
	for ( auto kv : m)
	{
		cout << kv.first << " " << kv.second;
	}
	//根据迭代器删除 
	map<int, string>::iterator pos = m.find(2);
	while (pos != m.end())
	{
		m.erase(pos);
	}
	for (auto kv : m)
	{
		cout << kv.first << " " << kv.second;
	}
	return 0;
}

[]运算符重载

map和set的具体用法 【C++】,c++,java,开发语言
map和set的具体用法 【C++】,c++,java,开发语言
[ ]运算符重载函数的参数就是一个key值,而这个函数的返回值如下:

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

根据上述代码可以推断出[ ],运算符重载实现的逻辑:

mapped_type& operator[] (const key_type& k)
{
	//1、调用insert函数插入键值对
	pair<iterator, bool> ret = insert( make_pair(k, mapped_type() ) );
	//2、拿出从insert函数获取到的迭代器
	iterator it = ret.first;
	//3、返回该迭代器位置元素的值value
	return it->second;
}

[]运算符的使用

int main()
{
		 map<string, string> dict;
		 dict.insert(make_pair("string", "字符串"));
		 dict.insert(make_pair("sort", "排序"));
		 dict.insert(make_pair("insert", "插入"));
	
		 cout << dict["sort"] << endl;//查找和读
		 dict["map"];//插入
		 dict["map"] = "映射,地图";//修改
		 dict["insert"] = "xxx";//修改
		 dict["set"] = "集合";//插入+修改
}

总结一下:
1、如果k不在map中,则先插入键值对<k, V()>,然后返回该键值对中V对象的引用。
2、如果k已经在map中,则返回键值为k的元素对应的V对象的引用。

map的迭代器遍历

int main()
{
	map<int, string>  m;
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(3, "three"));

	//正向迭代器 
	map<int, string>::iterator   it = m.begin();
	while (it != m.end())
	{
		//cout << (*it).first << ":"<<(*it).second<<endl;//迭代器重载operator*
		cout << it->first << ":" << it->second << endl;//迭代器重载operator->
		it++;	
	}
	cout << endl;
	//反向迭代器 
	map<int, string>::reverse_iterator rit = m.rbegin();
	while (rit != m.rend())
	{
		cout << " " << rit->first << " " << rit->second;
		rit++;
	}
	cout << endl;
	//范围for ,kv就是*it
	for (auto kv : m)
	{
		cout << kv.first <<" " << kv.second;
	}
	return 0;
}

multimap

multimap容器与map容器的底层实现一样,也都是平衡搜索树(红黑树),multimap容器和map容器的区别与multiset容器和set容器的区别一样,multimap允许键值冗余,即multimap容器当中存储的元素是可以重复的。

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	multimap<int, string> mm;
	//插入元素(允许重复)
	mm.insert(make_pair(2, "two"));
	mm.insert(make_pair(2, "double"));
	mm.insert(make_pair(1, "one"));
	mm.insert(make_pair(3, "three"));
	for (auto e : mm)
	{
		cout << "<" << e.first << "," << e.second << ">" << " ";
	}
	cout << endl; //<1,one> <2,two> <2,double> <3,three>
	return 0;
}

map和set的具体用法 【C++】,c++,java,开发语言
如果你觉得这篇文章对你有帮助,不妨动动手指给点赞收藏加转发,给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力!!
文章来源地址https://www.toymoban.com/news/detail-720770.html

到了这里,关于map和set的具体用法 【C++】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】map和set封装

    作者:დ旧言~ 座右铭:松树千年终是朽,槿花一日自为荣。 目标:手撕哈希表的闭散列和开散列 毒鸡汤:学习,学习,再学习 ! 学,然后知不足。 专栏选自:C嘎嘎进阶 望小伙伴们点赞👍收藏✨加关注哟💕💕 map和set的知识我们学习了,模拟实现我们已经实现了AVL树和红

    2024年04月24日
    浏览(25)
  • 【C++】map和set深度讲解

    作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等 座右铭:松树千年终是朽,槿花一日自为荣。 目标:熟练掌握map和set容器。 毒鸡汤:得知坦然,失之淡然,争之必然,顺其自然。 望小伙伴们点赞👍收藏✨加关注哟💕💕  早期我们学习了顺序容器(vector,li

    2024年04月14日
    浏览(24)
  • 【C++】map & set 底层刨析

    在 C++ STL 库中,map 与 set 的底层为红黑树,那么在不写冗余代码的情况下使用红黑树同时实现 map 与 set 便是本文的重点。 迭代器的好处是可以方便遍历,是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器,需要考虑以下问题: begin() 与 end() STL 明确规定,be

    2024年04月12日
    浏览(36)
  • 【C++】set 类 和 map 类

    关联式容器 也是用来存储数据的,与序列式容器不同的是,其 里面存储的是 key, value 结构的 键值对,在数据检索时比序列式容器效率更高 用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量 key 和 value , key 代 表键值,value表示与key对应的信息 代码

    2024年04月17日
    浏览(23)
  • 【C++】map和set的封装

    在STL中,map和set都是使用的红黑树 map与set在STL中实现是一样的 对于value_type,map的第二个模板参数是pair,而set的第二个模板参数是key 这样写是为了map和set使用同一颗红黑树去复用map和set set K - rb_treeK,K mapK,V - rb_treeK,pairconst K,V 第一个模板参数拿到单独K的类型,使用Find erase接

    2024年02月05日
    浏览(40)
  • 【C++】红黑树 --- map/set 底层

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是 Red 或 Black . 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的;如下图: 每个结点不是红色就是黑色;

    2024年02月04日
    浏览(35)
  • C++:set和map的使用

    序列式容器:比如我们之前讲的vector、string、list等均为序列式容器,特点是 按元素顺序来保存和访问 。 关联式容器:比如本次讲的map和set,和序列式容器不同,其 依靠键值来保存和访问 ,数据检索效率闭序列式容器高。 PS:本文只讲使用,set和map底层是一颗 平衡二叉搜索

    2024年02月05日
    浏览(50)
  • 【C++】set和map的使用

    对于STL容器来说,有很多相似的功能,所以这里主要将与之前不同的功能说清楚 vector/list/deque 作为序列式容器(类似于线性表的存储方式) map与set作为关联式容器,里面存储的是key,value结构的键值对(数据之间有非常强的关联关系) 键值对:用来表示一 一对应的关系,key代表键

    2024年02月04日
    浏览(35)
  • 【C++】模拟实现map和set

    关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是结构的 键值对,在数据检索时比序列式容器效率更高。 用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代 表键值,value表示与key对应的信息。比如:现在要建立

    2024年02月01日
    浏览(38)
  • C++【红黑树封装map&&set】

    我们在开始之前,首先要明白一点,前面我们实现模拟实现红黑树以及现在的封装map和set,我们的目的主要学习它库中的框架及模板设计和复用,不是要原模原样的去实现。 先看库中的代码,取了核心代码。我们可以看到kv搞出来value_type,就是相关pair,pair里面的key是const,

    2024年02月07日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包