WHCSRL 技术网

C++_STL_map(map.insert返回值,三种统计次数,按照key值排序,按照value值排序(vector/multimap/multiset/优先级队列))

1.利用map是搜索二叉树特性统计次数

具体思路:先查找搜索树里面有没有这个key值。如果有就使对应的value值(表示个数)++。如果没有key值,就插入这个key并且表示数量的value设置为1
eg:统计水果出现的次数

#include<iostream>
#include<map>
#include<string>
#include<vector>

using namespace std;

void CoutByMap()
{
	vector<string>ArrStr = { "柚子","柚子","香蕉","苹果","香蕉","哈密瓜","哈密瓜","哈密瓜","柚子","柚子","榴莲","苹果" };
	map<string, int>coutMap;
	//计数方法1
	for (const auto& str : ArrStr)
	{
		map<string, int>::iterator cout = coutMap.find(str);
		if (cout != coutMap.end())//找到了,表示数量的second++
		{
			cout->second++;
		}
		else//找不到插入这种水果
		{
			coutMap.insert(make_pair(str, 1));
		}
	}
	//打印搜索树
	//(默认按照string的大小比较规则从小到大排列)
	map<string, int>::iterator ptr = coutMap.begin();

	while (ptr != tmp.end())
	{
		cout << ptr->first << "->" << ptr->second << endl;//打印时要分别指明key和value
		ptr++;
	}
	cout << endl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

按照string从小到大排列
在这里插入图片描述

2.STL_map.insert()返回值

map.insret()返回的是一个pair类型
这个pair的first为插入位置的迭代器,second位置为bool类型数据
即返回pair<map<T1,T2>::iterator,bool>类数据
其中T1,T2是模板参数

当map中没有key值,插入成功返回的bool会被设置为true.同时也会接受到插入位置的迭代器
当map中有key值,插入失败返回的bool被设置为false.同时也会接受到这个重复key位置的迭代器

利用map.insert()的返回值来统计次数

先将获得的所有水果的value都设为1.并且将其插入map中
检查pair<map<string, int>::iterator, bool>中的bool,如果bool为false说明这个水果在map中出过,通过pair的first就可以找到这个位置的迭代器,使其表示个数的值++即可

eg:统计水果出现的次数

void Cout2(const vector<string>& ArrStr, map<string, int>& coutMap)
{
	for (const auto& str : ArrStr)
	{
		//先将所有水果插入,检查ret的bool
		pair<map<string, int>::iterator, bool>ret = coutMap.insert(make_pair(str, 1));
		//auto ret=coutMap.insert(make_pair(str,1));
		if (ret.second == false)//水果出现过
		{
			ret.first->second++;//表示水果数量的值++
		}
	}

	//打印map
	for (const auto& e : coutMap)
	{
		cout << e.first << "->" << e.second << endl;
	}
}

//map统计次数,并按照次数排序
void CoutByMap()
{
	vector<string>ArrStr = { "柚子","柚子","香蕉","苹果","香蕉","哈密瓜","哈密瓜","哈密瓜","柚子","柚子","榴莲","苹果" };
	map<string, int>coutMap;
	Cout2(ArrStr, coutMap);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

在这里插入图片描述

3.利用[]运算符重载统计次数

void Cout3(const vector<string>& ArrStr, map<string, int>& coutMap)
{
	for (const auto& str : ArrStr)
	{
		coutMap[str]++;
	}
	//打印map
	for (const auto& e : coutMap)
	{
		cout << e.first << "->" << e.second << endl;
	}
}


//map统计次数,并按照次数排序
void CoutByMap()
{
	vector<string>ArrStr = { "柚子","柚子","香蕉","苹果","香蕉","哈密瓜","哈密瓜","哈密瓜","柚子","柚子","榴莲","苹果" };
	map<string, int>coutMap;
	Cout3(ArrStr, coutMap);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

在这里插入图片描述

map中[]运算符重载

在这里插入图片描述
下面为其重载内容
(*((this->insert(make_pair(k,mapped_type()))).first)).second

带入具体的例子分析
上面统计水果为例子
在这里插入图片描述
上面例子中
[]运算符最后返回的是map中second的引用,++表示记录水果个数的数字+1
coutMap[str]相当于调用

coutMap.operator[](str)

当水果不存在时插入返回value的引用。
当水果存在时插入失败,返回value的引用

所以上面[]运算符重载在类中,可以写为

mapped_type& operator[] (const key_type& k)
{
	pair<iterator,bool>ret=insert(make_pair(k,mapped_type()));
//在类中可以直接使用iterator
	return ret.first->second;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

4.map按照value排序

我们都知道map搜索二叉树默认是按key值从小到大排序的。
但就按照上面的例子,当想按照水果出现的次数来排序时就不可以利用map这种默认的性质了

方法一:创建map迭代器数组,调用sort自定义排序规则排序(不稳定)

sort要排序数据,首先这些数据要支持比较大小

而我们将map的迭代器放到数组中,要对这个数组排序就必须自己写出迭代器比较大小的规则

按照上面的例子:
这个比较规则有两种写法。

函数指针法:

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

void Cout(const vector<string>& ArrStr, map<string, int>& coutMap)
{
	for (const auto& str : ArrStr)
	{
		coutMap[str]++;
	}
	//打印map
	for (const auto& e : coutMap)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;
}

//函数指针法自定义排序规则
bool CompMapStrInt(map<string, int>::iterator x, map<string, int>::iterator y)
{
	return x->second > y->second;//排降序,从大到小
}

void PrintSort(map<string, int>& coutMap)
{
	vector<map<string, int>::iterator>Arr;
	//将数据放入Arr中
	map<string, int>::iterator ptr = coutMap.begin();
	while (ptr != coutMap.end())
	{
		Arr.push_back(ptr);
		ptr++;
	}
	//排序
	std::sort(Arr.begin(), Arr.end(), CompMapStrInt);
	//打印map
	for (const auto& e : Arr)
	{
		cout << e->first << "->" << e->second << endl;
	}
}

//map统计次数,并按照次数排序
void CoutByMap()
{
	vector<string>ArrStr = { "柚子","柚子","香蕉","苹果","香蕉","哈密瓜","哈密瓜","哈密瓜","柚子","柚子","榴莲","苹果" };
	map<string, int>coutMap;
	Cout(ArrStr, coutMap);
	PrintSort(coutMap);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56

在这里插入图片描述

匿名对象

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

void Cout(const vector<string>& ArrStr, map<string, int>& coutMap)
{
	for (const auto& str : ArrStr)
	{
		coutMap[str]++;
	}
	//打印map
	for (const auto& e : coutMap)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;
}

struct CompMapStrInt2
{
	bool operator()(map<string, int>::iterator x, map<string, int>::iterator y)
	{
		return x->second > y->second;//排降序,从大到小
	}
};

void PrintSort(map<string, int>& coutMap)
{
	vector<map<string, int>::iterator>Arr;
	//将数据放入Arr中
	map<string, int>::iterator ptr = coutMap.begin();
	while (ptr != coutMap.end())
	{
		Arr.push_back(ptr);
		ptr++;
	}
	//排序
	/*std::sort(Arr.begin(), Arr.end(), CompMapStrInt);*/
	std::sort(Arr.begin(), Arr.end(), CompMapStrInt2());
	//打印map
	for (const auto& e : Arr)
	{
		cout << e->first << "->" << e->second << endl;
	}
}

//map统计次数,并按照次数排序
void CoutByMap()
{
	vector<string>ArrStr = { "柚子","柚子","香蕉","苹果","香蕉","哈密瓜","哈密瓜","哈密瓜","柚子","柚子","榴莲","苹果" };
	map<string, int>coutMap;
	Cout(ArrStr, coutMap);
	PrintSort(coutMap);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

在这里插入图片描述

方法二:利用multimap/multiset来改变排序的key(稳定)

multimap相比于map它的key键值可以冗余,这样就避免了map因为水果次数相同导致插入失败的情况
而且因为multimap在键值相同的时候查找优先返回第一个键值相同的位置,用multimap从小到大排序是稳定的
eg:

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>

void Cout(const vector<string>& ArrStr, map<string, int>& coutMap)
{
	for (const auto& str : ArrStr)
	{
		coutMap[str]++;
	}
	//打印map
	for (const auto& e : coutMap)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;
}

void PrintSort2(map<string, int>& coutMap)
{
	multimap<int, string>coutMapInt;
	for (const auto& str : coutMap)
	{
		coutMapInt.insert(make_pair(str.second, str.first));
	}
	//打印coutMapInt
	for (const auto& str : coutMapInt)
	{
		cout << str.first << "->" << str.second << endl;
	}
}

//map统计次数,并按照次数排序
void CoutByMap()
{
	vector<string>ArrStr = { "柚子","柚子","香蕉","苹果","香蕉","哈密瓜","哈密瓜","哈密瓜","柚子","柚子","榴莲","苹果" };
	map<string, int>coutMap;
	Cout(ArrStr, coutMap);
	PrintSort2(coutMap);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

在这里插入图片描述

控制multimap和multiset的键值排序方式(仿函数)

紧跟上题,如果我们想用multimap排序,因为multimap默认是二叉搜索树,其排序方式为从小到大排序。如果我们还想利用multimap,但是要从大到小排序,我们可以用反向迭代器解决,也可以改变multimap/map的排序规则,此时就要在定义multimap/map的位置传入仿函数

eg:

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>//仿函数头文件(greater/less)

void Cout(const vector<string>& ArrStr, map<string, int>& coutMap)
{
	for (const auto& str : ArrStr)
	{
		coutMap[str]++;
	}
	//打印map
	for (const auto& e : coutMap)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;
}

void PrintSort3(map<string, int>& coutMap)
{
	multimap<int, string,greater<int>>coutMapInt;//排升序
	for (const auto& str : coutMap)
	{
		coutMapInt.insert(make_pair(str.second, str.first));
	}
	//打印coutMapInt
	for (const auto& str : coutMapInt)
	{
		cout << str.first << "->" << str.second << endl;
	}
}

//map统计次数,并按照次数排序
void CoutByMap()
{
	vector<string>ArrStr = { "柚子","柚子","香蕉","苹果","香蕉","哈密瓜","哈密瓜","哈密瓜","柚子","柚子","榴莲","苹果" };
	map<string, int>coutMap;
	Cout(ArrStr, coutMap);
	PrintSort3(coutMap);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

在这里插入图片描述

方法三:利用优先级队列保存map迭代器指针来对map的value排序(堆排序不稳定)

因为优先级队列本质是堆,所以其为不稳定排序。

使用优先级队列要传比较函数,这里比较函数只能通过对象的方式给

同时我们选择数组作为优先即队列的实现

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<queue>

using namespace std;

void Cout(const vector<string>& ArrStr, map<string, int>& coutMap)
{
	for (const auto& str : ArrStr)
	{
		coutMap[str]++;
	}
	//打印map
	for (const auto& e : coutMap)
	{
		cout << e.first << "->" << e.second << endl;
	}
	cout << endl;
}

struct CompMapStrInt2
{
	bool operator()(map<string, int>::iterator x, map<string, int>::iterator y)
	{
		return x->second < y->second;//从大到小 建小堆
	}
};

void PrintSort4(map<string, int>& coutMap)
{
	typedef map<string, int>::iterator MapIter;
	priority_queue<MapIter, vector<MapIter>, CompMapStrInt2>pq;
	map<string, int>::iterator ptr = coutMap.begin();
	while (ptr != coutMap.end())
	{
		pq.push(ptr);
		ptr++;
	}
	//打印pq
	int Size = pq.size();
	for (int i = 0; i < Size; i++)
	{
		MapIter tmp= pq.top();
		cout << tmp->first << "->" << tmp->second << endl;
		pq.pop();
	}
}

//map统计次数,并按照次数排序
void CoutByMap()
{
	vector<string>ArrStr = { "柚子","柚子","香蕉","苹果","香蕉","哈密瓜","哈密瓜","哈密瓜","柚子","柚子","榴莲","苹果" };
	map<string, int>coutMap;
	Cout(ArrStr, coutMap);
	PrintSort4(coutMap);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

在这里插入图片描述