首页 > 其他分享 >STL之set和map使用介绍（六千字长文详解）

STL之set和map使用介绍（六千字长文详解）

时间：2023-10-25 11:01:02浏览次数：43  
标签：map set cout insert STL dict pair

set和map介绍

基础概念

关联式容器

像是vector，list，deque，forward_list这些都是属于==序列式容器==！因为其底层为线性序列的数据结构，里面存储的是元素本身。

而map和set是属于==关联式容器==！

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

==关联式容器的数据与数据之间是紧密关联的！==像是list，vector这样的序列式容器，数据之间的关联很小！如果要插入一个数据实际上插入那个位置是无所谓的！

==但是关联式容器不一样！关联式容器的每一个数据都是有固定的位置的！数据与数据之间有强烈的关联关系！我们正是通过数据之间的关系，才能做到高效率的搜索==

键对值

用来表示==具有一一对应关系==的一种结构，==该结构中一般只包含两个成员变量key和value，key代 表键值，value表示与key对应的信息。==

比如：现在要建立一个英汉互译的字典，那该字典中必然 有英文单词与其对应的中文含义，==而且英文单词与其中文含义是一一对应的关系==，即通过该应该单词，在词典中就可以找到与其对应的中文含义

其定义为

template<class K,class V>
struct pair
{
	K first;
	V second;
	pair()
		:first(K()),
		second(V())
	{}
	pair(const K& key,const V& value)
		:first(key).
		second(value)
	{}
};

在底层中image-20230410212341029

树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：==树型结构与哈希结构==。==树型结构的关联式容器主要有四种：map、set、multimap、multiset==。

这四种容器的共同点是：使用==平衡搜索树(即红黑树)作为其底层结果==，容器中的元素是一个有序的序列。

set

set的底层是一个==平衡二叉搜索树==！平衡二叉搜索树比起二叉搜索树解决了二叉搜索树的可能出现的退化成单链的问题！让整个二叉搜索树的可以一直保持接近完全二叉树的状态！让搜索效率一直维持在O(logN)——理论上10亿个数据也只要搜索30次左右！如果是14亿个也只要多搜索一次！

==set是一个k模型！==

image-20230410095657746

set有三个模板参数，一个是关于数据类型的T，一个是仿函数的——如果我们想要自己决定树中key的比较的规则，那么我们就可以自己写一个仿函数传进去！最后一个是空间配置器，这个我们暂且不讲

修改接口

insert：向树里面进行插入

image-20230410115208276

==insert是支持在某个迭代器位置插入一个值的！==

==但是要慎用！因为可能会破坏树的结构！==

image-20230410115716234

void test_insert()
{
	set<int> s;
	s.insert(100);
	s.insert(17);
	s.insert(19);
	s.insert(89);
	s.insert(99);
	s.insert(99);
	//排序+去重
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	//底层就是一个中序遍历！
}
int main()
{
	test_insert();
	return 0;
}

==set的插入就是一个排序+去重的过程！==

image-20230410171911988

erase：从树里面删除一个节点！

image-20230410115805483

erase可以删除某个迭代器的位置！

或者删除某个值！（就是find+删除）

image-20230410121314164

==如果是调用第二个接口，那么会返回删除的元素个数！有就是1，没有就是0==

void test_erase()
{
	set<int> s;
	s.insert(100);
	s.insert(17);
	s.insert(19);
	s.insert(89);
	s.insert(99);

	cout << s.erase(100) << endl;//删除100 此时返回删除的个数1
	cout << s.erase(100) << endl;//这个数 返回0
    //erase删除一个不存在的数是不会报错的！

	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
}
int main()
{
	test_erase();
	return 0;
}

image-20230410172229833

clear：清除容器
#include <iostream>
#include <set>
int main ()
{
  std::set<int> myset;

  myset.insert (100);
  myset.insert (200);
  myset.insert (300);

  std::cout << "myset contains:";
  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  myset.clear();
  myset.insert (1101);
  myset.insert (2202);

  std::cout << "myset contains:";
  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

image-20230410203906273

emplace

也是插入！但是和右值引用有关！这里就不详细的介绍了！

int main ()
{
	set<int> s;
	s.emplace(100);
	s.emplace(7);
	s.emplace(89);
	s.emplace(88);
	s.emplace(78);
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
  return 0;
}

image-20230410203647211

swap：交换两个set容器的根节点
// swap sets
#include <iostream>
#include <set>

main ()
{
  int myints[]={12,75,10,32,20,25};
  std::set<int> first (myints,myints+3);     // 10,12,75
  std::set<int> second (myints+3,myints+6);  // 20,25,32

  first.swap(second);

  std::cout << "first contains:";
  for (std::set<int>::iterator it=first.begin(); it!=first.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  std::cout << "second contains:";
  for (std::set<int>::iterator it=second.begin(); it!=second.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

image-20230410203417114

操作接口

image-20230410113154104

find——查找一个元素，并返回迭代器

image-20230410120324132

image-20230410120308235

如果找不到这个元素就返回set::end()

void test_find()
{
	set<int> s;
	s.insert(100);
	s.insert(17);
	s.insert(19);
	s.insert(89);
	s.insert(99);
	s.insert(99);
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	auto pos = s.find(100);
	if (pos != s.end())
		cout << *pos << endl;
	s.erase(pos);

	pos = s.find(100);
	if (pos != s.end())
		cout << *pos<< endl;
	else
		cout << "不存在" << endl;

}
int main()
{
	test_find();
	return 0;
}

image-20230410173305337

==count==:计算树里面的一个元素有多少个（但是因为set的每一个元素都是唯一的！所以只会返回1）

lower_bound/upper_bound

==这两个接口都是用于找边界==

int main()
{
	std::set<int> myset;
	std::set<int>::iterator itlow, itup;

	for (int i = 1; i < 10; i++) //10 20 30 40 50 60 70 80 90 100
		myset.insert(i * 10);
	itlow = myset.lower_bound(30);//找到第一个不认为是小于30的元素，即等于30或者第一个大于30的元素
	//如果没有30返回的应该是40
    //所以这个是大于等于
	itup = myset.upper_bound(60);//找到第一个大于60的节点！—— 所以返回的应该是70！
    //这个是大于
	myset.erase(itlow, itup);
    //为什么要这样呢？因为我们迭代器的区间的都是左闭右开的！
    //所以两个是要配合使用的！
	std::cout << "myset contains:";
	for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
		std::cout << ' ' << *it;
	std::cout << '\n';

	return 0;
}

image-20230410205816790

equal_range

image-20230410210734724

返回值是一个pair

image-20230410210959569

==第一个迭代器的范围就是和lower_bound一样第一个大于等于参数的值，第二个参数和upper_bound一样第一个大于该参数的值！==

#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;

  for (int i=1; i<=5; i++) myset.insert(i*10);   // myset: 10 20 30 40 50

   //myset.erase(30);
    //如果我们移除掉30就会返回大于30的值就是40
  std::pair<std::set<int>::const_iterator,std::set<int>::const_iterator> ret;
  ret = myset.equal_range(30);

  std::cout << "the lower bound points to: " << *ret.first << '\n';
  std::cout << "the upper bound points to: " << *ret.second << '\n';

  return 0;
}

image-20230410211241482

迭代器

image-20230410114238978

multiset

count

==上面我们看到了一个很不明所以的函数接口count——为什么set不允许存在相同元素会存在这个接口？看起来很没有什么意义！==

==就是因为这个mutiset，这个multiset是可以存在键值冗余的set，这时候count就可以发挥用处了！==——对于set意义不大！==但是对于multiset就很重要的！==

image-20230410122950395

void test_insert()
{
	multiset<int> s;
	s.insert(100);
	s.insert(17);
	s.insert(19);
	s.insert(89);
	s.insert(99);
	s.insert(99);
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//相当于就是一个排序！但是不去重！
	cout << s.count(99) << endl;
}
int main()
{
	test_insert();
	return 0;

}

image-20230410173844635

==其他接口和set几乎没有什么不同！==——除了find！

find

==find对于树里面的相同元素！它找的是中序遍历的里面的第一个元素！==

我们可以验证一下

void test_find()
{
	multiset<int> s;
	s.insert(100);
	s.insert(17);
	s.insert(19);
	s.insert(89);
	s.insert(99);
	s.insert(99);
	s.insert(99);
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
    
	it = s.find(99);
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	//相当于就是一个排序！但是不去重！
}
int main()
{
	test_find();
	return 0;

}

image-20230410174527149

我们可以看到就是从中序的第一个相同元素开始的！

map

==map其实和set的区别不大！底层也是一个搜索二叉树！只不过set是一个k模型！而map是一个kv模型！==

image-20230410211458622

image-20230410214225459

==库中的map中一般会将pair类型重命名为 value_type==

==map的key是不可以修改的！但是value是可以修改！从上面我们也可以看出来！==

因为map和set其实底层和接口都是差不多的！==我们这里就介绍一下用法较为不同的接口！==

insert

image-20230410214559870

我们可以看到map的insert==第一个函数重载参数value_type——就是一个pair类型的别名！==

int main()
{
	map<string, string> dict;
	dict.insert(pair<string, string>("sort", "排序"));
 //此时用匿名对象来进行插入是一个好的选择！
	dict.insert(pair<string, string>("right", "右边"));
	dict.insert(pair<string, string>("left", "左边"));

 //上面的写法还是太长了！插入太麻烦了！
 //所以有一个简化的写法！
	dict.insert(make_pair("字符串", "string"));

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

 //或者这样写
	map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		//cout << *it << endl;
		//operator* 返回的是一个pair类型！
		//因为C++不支持返回两个参数！这就是为什么要有pair类型的原因！
		//因为pair不支持流插入和流提取的重载所以不可以直接解引用然后打印！
		cout << (*it).first <<";" << (*it).second<<endl;
     cout << it->first <<";" << it->second<<endl;
     //pair类型有支持operator->进行重载
		//这样写才是对的！
 }
 //但是追求方便用范围for比较合适
	return 0;
}

==make_pair其实就是==

image-20230410215655808

==就是做了一个封装！其实返回的也是一个匿名对象！但是它是一个函数模板！我们不需要显示的去写类型！他会根据我们传参后自动的去推导！==

image-20230410215928883

==insert的第一个函数重载的返回值看起来很奇怪==

image-20230411091324132

image-20230411091259480

==返回的是一个pair类型的变量,pair里面first是一个迭代器，second是一个bool类型的变量==

==迭代器要么指向新插入的一个元素，要么指向与这个新插入的元素key值等的元素！==

==如果成功的插入新元素，那么bool类型变量就会被设置成true！如果插入的元素（即key值相同）已经存在那么bool类型的变量就会被设置成false==

map的应用

统计水果出现次数

int main()
{
	std::string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
		"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countmap;
	for (auto& e : arr)
	{
		auto it = countmap.find(e);
		if (it == countmap.end())
			countmap.insert(make_pair(e, 1));
		else
			it->second++;
	}
	for (auto &e : countmap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

image-20230411083058203

map的operator[]重载——重点

==上面的水果统计其实有一个更加简单写法！==

int main()
{
	std::string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
		"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countmap;
	for (auto& e : arr)
	{
		countmap[e]++;
	}
	for (auto &e : countmap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

==[]的重载是map接口学习中很重要的一部分！==

按照我们以前的理解！[]是用来支持随机访问的！==但是map里面的[]不是这样的！==

==像是vector/deque/array的方括号里面都是下标！但是map的[]里面好像不是下标而是我们的字符串？——或者说是key值==

那么这究竟是怎么实现的呢？

image-20230411090013473

==我们看一下operator[]的参数和返回值，这两个分别又是什么？==

image-20230411090338698

==传参的是第一个模板类型的参数，返回的是第二个模板类型参数==

==也就是说——传入的参数是key，返回的参数是value！==

调用这个函数等于下面这个写法

image-20230411090554310

mapped_type& operator[] (const key_type& k)
{
	return (*((this->insert(make_pair(k,mapped_type()))).first)).second;
}

这一看看起来好像很吓人！但是里如果我们仔细分析一下

image-20230411112610177

==我们返回的是second的别名我们就可以进行修改！==

现在我们重新看一下这个代码

int main()
{
	std::string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
		"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countmap;
	for (auto& e : arr)
	{
		countmap[e]++;
	}
}

开始的时候e如果不在map里面，那么就充当插入+查找的功能！

返回int类型的second的别名，int()是初始化为0，如果是新元素，那么我们++就是 从 0变1，

如果e存在，那么就充当find功能，返回这个存在节点的int类型的second的别名，在原有的次数上++。

==所以这个[]充当了——插入/修改/查找的功能！==——要小心，查找功能要保证这个值一定存在于map里面！否则就会变成插入！

应用

==有了[]之后其实我们也有了新的插入修改手段！==

int main()
{
	map<string, string> dict;
	dict.insert(make_pair("字符串", "string"));
	dict.insert(make_pair("字符串", "xxx"));//这句话就是相当于插入失败，只比较key相不相同，value不管
	dict["sort"] = "排序";//插入+修改！
	dict["right"] = "右边";
	dict["left"] = "上边";
	dict["insert"]; //如果只是这样子！那么就相当于value是"" 是一个空字符串
	//因为string的默认构造就是初始化为空字符串！那么那个缺省值也会被初始化为空字符符！

	for (auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	dict["left"] = "左边";//修改
	for (auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << dict["left"] << endl;//这个就充当了查找的功能！
	//但是要小心！一定要保证存在！才能查找！
	return 0;
}

image-20230411153035434

at

image-20230411153643132

at和[]的用法差不多

int main ()
{
  map<std::string,int> mymap = {
                { "alpha", 0 },
                { "beta", 0 },
                { "gamma", 0 } };

  mymap.at("alpha") = 10;
  mymap.at("beta") = 20;
  mymap.at("gamma") = 30;
  for (auto& x: mymap)
  {
    cout << x.first << ": " << x.second << '\n';
  }

  return 0;
}

==唯一的区别就是如果没有匹配的元素那么就会直接抛异常！而不是插入！==

multimap

==multimap其实和map没有什么不同！就是像set与multiset一样允许键值冗余！==

只不过multimap就没有了[]与at——==因为一个键值可能会对应多个value！==那么那时候应该返回什么？==所以不提供[]与at==

==multimap的find和multiset的find是一样的！如果有多个！那么就找中序的第一个！==

map的count也是在multimap的时候才有用处！

int main()
{
	multimap<string, string> dict;
	dict.insert(make_pair("字符串", "str"));
	dict.insert(make_pair("左边", "left"));
	dict.insert(make_pair("右边", "right"));
	dict.insert(make_pair("左边", "xxx"));
	for (const auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
    
	//multimap也可以统计次数！
	std::string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
		"苹果", "香蕉", "苹果", "香蕉" };
	multimap<string, int> countmap;
	for (auto& e : arr)
	{
		auto it = countmap.find(e);
		if (it == countmap.end())
			countmap.insert(make_pair(e, 1));//因为并不是持续的插入！在插入之前还有一个查找！只有找不到才会进行插入！
		else
			it->second++;
	}
	for (auto& e : countmap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	return 0;
}

image-20230411155318149

标签：map,set,cout,insert,STL,dict,pair
From： https://blog.51cto.com/u_15835985/8015606

相关文章

  • Git 克隆错误 error: RPC failed; curl 28 Recv failure: Connection was reset
    在网络情况不稳定下克隆项目时，可能会出现下图中的错误。问题原因：http缓存不够或者网络不稳定等。我也是找了好多博客资料，终于解决了解决方法打开cmd，修改git配置（加大httpBuffer）即可。gitconfig--globalhttp.postBuffer524288000  我在解决这个问题之前clone一......
  • MapStruct详解
    1啥玩意？MapStruct是一个代码生成器，它基于约定优于配置的方法极大地简化了Javabean类型之间映射的实现。生成的映射代码使用简单的方法调用，因此速度快、类型安全且易于理解。2为什么？多层应用程序通常要在不同对象模型（如entities和DTO）之间映射。编写映射代码是乏味易出错......
  • 2014腾讯校园招聘实习技术类笔试题目/STL小结
    STL就是StandardTemplateLibrary，标准模板库。这可能是一个历史上最令人兴奋的工具的最无聊的术语。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其它一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作......
  • java动态创建es 及mapping
    publicCreateIndexResponsecreateIndexWithMapping(Stringindex,Map<String,String>mapping){CreateIndexResponseresponse=null;try{CreateIndexRequestrequest=newCreateIndexRequest(index);request.settings(Settings.b......
  • FAST协议详解4 存在图PMap
    一、概述存在图是比较基础但又非常重要的一个设定，如果存在图没搞对后面的解析肯定是有问题的。但要说清楚存在图又必须先搞明白各种数据类型、操作符、可空属性，所以存在图虽然在FAST数据流的最前面但又不得不放到最后来说。 二、存在图的基本设定存在图主要与操作符类型强相关，但又......
  • Java HashMap类
    HashMap是我们使用非常多的Collection，它是基于哈希表的Map接口的实现，以key-value的形式存在。HashMap实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该......
  • Pset_SpaceOccupancyRequirements
    Pset_SpaceOccupancyRequirements空间占用要求：与在一个或一组类似的空间结构元素内发生或预计发生的工作活动有关的属性。 NameTypeDescriptionOccupancyTypeP_SINGLEVALUE / IfcLabelNutzungsartNutzungsartdesRaumsgemäßdergültigenRaumnutzungstabe......
  • [924] ArcGIS Pro Mapping Module - arcpy.mp
    ref:Introductiontoarcpy.mpref:Gettingstartedwitharcpy.mptutorialref:Guidelinesforarcpy.mpref:Alphabeticallistofarcpy.mpfunctionsref:Alphabeticallistofarcpy.mpclassesref:SQLreferenceforqueryexpressionsusedinArcGISThefol......
  • 更改Kali Linux系统语言以及安装zenmap
    更改KaliLinux系统语言以及安装zenmap在使用kali的过程中，会遇到许多问题，其中一个就是看不懂英语，下面是如何更换语言的步骤。更改KaliLinux系统语言首先，打开kali，以root用户打开终端，如图1-1所示，然后输入密码kali，如图1-2所示，再打开终端如图1-3所示，最后就看到如图1-4所示。 图......
  • Set 和 Map 数据结构
    Set基本用法ES6提供了新的数据结构Set。它类似于数组，但是成员的值都是唯一的，没有重复的值。Set本身是一个构造函数，用来生成Set数据结构。consts=newSet();[2,3,5,4,5,2,2].forEach(x=>s.add(x));for(letiofs){console.log(i);}//2354上面代码通......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99