C++——map和set的基本使用

目录

一，关联式容器

二，键值对

三，set的使用

3.1 set介绍

3.2?set的插入和删除

3.3 set的pair

3.4 multiset

四，map的使用

4.1 map介绍

4.2 map实现简易字典

?4.3 map实现统计次数

4.4 map的[]

五，使用map或set解决部分OJ题

5.1 复杂链表的复制

5.2?前K个高频单词

5.2.1 解法一：使用sort算法排序

5.2.2 使用multimap解决

?5.2.3 使用set的特性加仿函数解决

?5.3 两个数组的交集

---

一，关联式容器

在前面的文章里，我们以及接触过STL的部分容器，包括：vector，list，deque等，这些容器同称为序列式容器，因为其底层为线性序列的数据结构，里面存的是元素本身。

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

二，键值对

键值对是用来表示居于一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value。key代表监事，value表示与key对应的信息。比如建一个英汉互译的字典，所以这个字典中，英语单词与其含义是一一对应的关系，即通过该单词可以在字典中找到对应的中文含义

下面是STL中关于键值对pair的定义

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的使用

3.1 set介绍

①set是按照一定次序存储元素的容器

②在set中，元素的value也标识它（value就是key，类型为T），并且每个value必须是唯一的

③在内部，set中的元素总是按照其内部比较对象所指示的特点排序准则进行排序

④set在底层是用红黑树实现的

3.2?set的插入和删除

void test_set1()
{
	//set<int> s = {1,2,1,6,3,8,5};//列表初始化
	int a[] = { 1,2,1,6,3,8,5 };
	set<int> s(a, a + sizeof(a) / sizeof(int));//set支持通过迭代器区间初始化
	//set<int,greater<int>> s(a, a + sizeof(a) / sizeof(int));可以自行控制这颗树

	//set间接完成了  排序+去重，因为set底层是一个搜索二叉树
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		//搜索树不允许修改key，可能会破坏搜索的规则
		//*it += 1;
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//删除
	//方法1
	s.erase(1);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	//方法2
	set<int>::iterator pos = s.find(2);
	if (pos != s.end())//判断有没有找到
	{
		s.erase(pos);
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	//count()返回数据个数，但由于set默认去重只能返回0或1，所以一般用作判断该数是否存在
	cout << s.count(3) << endl;  //判断在不在，并且返回个数
	cout << s.count(30) << endl;
}

?

void test_set2()
{
	set<int> myset;
	set<int>::iterator itlow, itup;
	for (int i = 0; i < 10; i++)
		myset.insert(i * 10);  //10 20 30 40 50 60 70 80 90
	itlow = myset.lower_bound(25);//返回的是>=val的第一个值，此处返回30
	itup = myset.upper_bound(60);//返回的是>val的第一个值，此处返回70
	cout << "[" << *itlow << "," << *itup << "]" << endl;

	myset.erase(itlow, itup);//删除这两个值所代表的范围之间的数
}

?

3.3 set的pair

void test_set3()//pair用来记录一对数据
{
	set<int> myset;
	for (int i = 1; i <= 5; i++)
		myset.insert(i * 10);//10 20 30 40 50 
	pair<set<int>::const_iterator, set<int>::const_iterator> ret;
	ret = myset.equal_range(40);

	cout << "the lower bound points to : " << *ret.first << endl;
	cout << "the upper bound points to : " << *ret.second << endl;
}

?

3.4 multiset

void test_multiset()//multiset与set不一样的是，multiset允许有重复值
{
	int a[] = { 3,1,2,1,6,3,8,3,5,3,1 };
	multiset<int> s(a, a + sizeof(a) / sizeof(int));

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << s.count(1) << endl;//这里的count就是记录个数了

	auto pos = s.find(3);
    //find时如果有多个值，返回中序的第一个位置,如果想找第二个3，把迭代器++一下就是第二个3
	while (pos != s.end())
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;
	s.erase(3);//如果要删除的值有多个，删除所有的值
	for (auto e : s)
	{
		cout << e << " ";
	}
}

四，map的使用

4.1 map介绍

①map是关联容器，它按照特点的次序（按照key来比较）存储由简直key和value组合而成的元素

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

③在内部，map中的元素总是按照键值key进行比较排序的

④map支持下标访问符，即在[]中放入key，就可以找到与key对应的value

4.2 map实现简易字典

void test_map1()
{
	map<string, string> dict;
	pair<string, string> kv1("sort","排序");//隐式类型转换
	dict.insert(kv1);
	//但是上面有点麻烦，所以这时候“匿名对象”就排上用场了
	dict.insert(pair<string, string>("test", "测试"));
	dict.insert(pair<string, string>("string", "字符串"));

	typedef pair<string, string> DictkV;
	dict.insert(DictkV("string", "xxx"));//只看king相不相同,所以这里不用xxx替换“字符串”，king已经有了，所以直接插入失败
	//大家也不喜欢用typedef，喜欢用下面这个东东
	dict.insert(make_pair("left", "左边"));
	/*template<class T1,class T2>
	pair<T1, T2> make_pair(T1 x, T2 y)
	{
		return (pair<T1, T2>(x, y));
	}*/

	//map遍历
	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		//cout << *it << endl;//报错，pair不支持流插入，迭代器的解引用是去调用operator*，set只有king就返回king的引用，pair有两个值first和secong，一个函数的调用用不允许返回两个值
		
		//cout << (*it).first << (*it).second << endl;虽然这样可以排序，但是map不喜欢这样搞
		cout << it->first << it->second << endl;//这里的it是指针，->经过重载，it->返回pari*，然后再->就可以找到first，但是就变成了it->->太难看了，所以编译器优化掉了一个->
		++it;
	}
	cout << endl;

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

?

?4.3 map实现统计次数

void test_map2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
	//统计次数
	//map<string, int> countMap;
	//for(auto & str : arr)
	//{
	//	//map<string, int>::iterator it = countMap.find(str);
	//	//if (it != countMap.end()) //找到了
	//	//{
	//	//	//说明该水果是有的
	//	//	//(*it).second++;
	//	//	it->second++;
	//	//}
	//	//else //没找到
	//	//{
	//	//	//说明是一个新水果，插入一个
	//	//	countMap.insert(make_pair(str, 1));
	//	//}
	//}
	//上面的是常规的统计次数的方法，但是太麻烦了，我们一般用[]将查找插入修改一并完成
	map<string, int> countMap;
	for (auto& str : arr)
	{
		countMap[str]++; //重载的operator[]
		//1,str不在countMap中，插入pair(str,int()),然后再返回++                                   key已经在map中，返回pair(key_iterator,false);
		//2,str在countMap中，直接返回value的引用再++                                              key不在map中，返回pair(new_key_iterator,true);
	}
	map<string, int>::iterator it = countMap.begin();
	while (it != countMap.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}

	/*V& operator[](const K& key)
	{
		pair<iterator, bool> ret = insert(make_pair(key, V()); //insert完成了查找，bool表示插入是否成功
		return ret.first->second
	}*/
}

?

4.4 map的[]

void test_map3()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("count", "计数"));

	dict["left"];                   //插入 
	dict["right"] = "右边";         //插入+修改
	dict["string"] = "（字符串）";  //修改
	cout << dict["string"] << endl; //查找，打印 "（字符串）"

	map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
}

五，使用map或set解决部分OJ题

5.1 复杂链表的复制

题目出处：LCR 154. 复杂链表的复制 - 力扣（LeetCode）

class Solution
{
public:
	Node* copyRandomList(Node* head)
	{
		map<Node*,Node*> copyNodeMap;
		Node* cur = head;
		Node* copyhead, *copytail;
		copyhead = copytail = nullptr;
		while (cur)
		{
			Node* copy = new Node(cur->val);
			copyNodeMap[cur] = copy;
			if (copytail == nullptr)
			{
				copytail = copyhead = copy;
			}
			else
			{
				copytail->next = copy;
				copytail = copytail->next;
			}
			cur = cur->next;
		}
		cur = head;
		Node* copy = copyhead;
		while (cur)
		{
			if (cur->random == nullptr)
			{
				copy->random = nullptr;
			}
			else
			{
				copy->random = copyNodeMap[cur->random];
			}
			cur = cur->next;
			copy = copy->next;
		}
		return copyhead;
	}
};

5.2?前K个高频单词

题目出处：692. 前K个高频单词 - 力扣（LeetCode）

5.2.1 解法一：使用sort算法排序

class Solution {
public:
	//比较大小仿函数
	struct Compare
	{
		bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
		{
			return kv1.second > kv2.second || kv1.second == kv2.second && kv1.first < kv2.first;
		}
	};
	vector<string> topKFrequent(vector<string>& words, int k) {
		map<string, int> countMap;
		for (auto& str : words)
		{
			countMap[str]++; //统计次数
		}
		//因为需要使用sort排序，而map是一个双向迭代器，不是随机迭代器也就是不能通过下标访问元素
		//所以我们先把值放进vector中排序
		vector<pair<string, int>> v(countMap.begin(), countMap.end());
		//stable_sort(v.begin(),v.end(),Compare()); //C++提供的稳定的排序函数
		sort(v.begin(), v.end(), Compare());
		vector<string> v1;
		for (size_t i = 0; i < k; i++)
		{
			v1.push_back(v[i].first);
		}
		return v1;
	}
};

5.2.2 使用multimap解决

class Solution {
public:
	/*struct Compare
	{
		bool operator()(const int& key1, const int& key2) const
		{
			return key1 > key2;
		}
	};*/
	vector<string> topKFrequent(vector<string>& words, int k) {
		map<string, int> countMap;
		for (auto& str : words)
		{
			countMap[str]++; //统计次数
		}
		//直接使用multimap进行排序
		//multimap<int, string, Compare> sortMap;
		multimap<int, string, greater<int>> sortMap; //巧合，题目给的测试用例插入的顺序刚好符合要求
		//当次数相同时，红黑树插入时插入在右边，如果插到左边就不行了
		for (auto& kv : countMap)
		{
			sortMap.insert(make_pair(kv.second, kv.first));
		}

		vector<string> ret;
		auto it = sortMap.begin();
		while (k--)
		{
			ret.push_back(it->second);
			++it;
		}
		return ret;
	}
};

?5.2.3 使用set的特性加仿函数解决

class Solution3 {
public:
	struct Compare
	{
		bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const
		{
			return kv1.second > kv2.second || kv1.second == kv2.second && kv1.first < kv2.first;
		}
	};
	vector<string> topKFrequent(vector<string>& words, int k) {
		map<string, int> countMap;
		for (auto& str : words)
		{
			countMap[str]++; //统计次数
		}
		//这里默认是升序，暂时我们要降序，所以加仿函数
		set<pair<string, int>, Compare> sortSet(countMap.begin(), countMap.end());
		vector<string> ret;
		auto it = sortSet.begin();
		while (k--)
		{
			ret.push_back(it->first);
			++it;
		}
		return ret;
	}
};

?5.3 两个数组的交集

题目出处：349. 两个数组的交集 - 力扣（LeetCode）

class Solution {
public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
	{
		//先去重
		set<int> s1(nums1.begin(), nums1.end());
		set<int> s2(nums2.begin(), nums2.end());
		auto it1 = s1.begin();
		auto it2 = s2.begin();
		vector<int> ret;
		//前面完成了去重，不相等也就不是交集，小的值的迭代器++，相等，拿出相等值然后两个迭代器同时++
		while (it1 != s1.end() && it2 != s2.end())
		{
			if (*it1 < *it2)
			{
				it1++;
			}
			else if (*it2 < *it1)
			{
				it2++;
			}
			else
			{
				ret.push_back(*it1);
				it1++;
				it2++;
			}
		}
		return ret;
		//如果要找差集，那么相等时同时++，不相等，小的就是差集
		//如果一个走完了，另一个没有走完，那么没走完的剩下的值也是差集
	}
};