• map和set的使用

    一、容器分类

    • 序列式容器：vector list
    • 关联式容器：map set

    二、键值对

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    三、set

    set的insert

    single element (1)	pair<iterator,bool> insert (const value_type& val);
with hint 	   (2)	iterator insert (iterator position, const value_type& val);
range 		   (3) 	template </class InputIterator>
					void insert (InputIterator first, InputIterator last);

    • 1
    • 2
    • 3
    • 4
    void testset1()
{
	set<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);
	s.insert(5);
	s.insert(5);

	// 搜索树默认遍历是中序
	// 排序+去重
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
 }

    • 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

    set的erase

    void erase (iterator position);  
size_type erase (const value_type& val); 
void erase (iterator first, iterator last);

    • 1
    • 2
    • 3
    void testset2()
{
	set<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);

	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	set<int>::iterator pos = s.find(5);
	if (pos != s.end())
	{
		s.erase(pos);
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
}

    • 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

    四、multiset

    multiset允许键值重复，其余操作与set几乎相同

    multiset的insert

    void testmultiset1()
{
	// 最大区别就是允许插入同样的值
	multiset<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);

	multiset<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

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

    multiset的find

    void testmultiset2()
{
	multiset<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	multiset<int>::iterator pos = s.find(5);
	// 这里找到是中序的第一个5
	/*if (pos != s.end())
	{
		s.erase(pos);
	}*/
	while (pos != s.end())
	{
		cout << *pos << " ";
		++pos;
	}
}

    • 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

    multiset的erase

    void testmultiset3()
{
	multiset<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	multiset<int>::iterator pos = s.find(5);
	// 这里找到是中序的第一个5
	 
	
	// 第一种就是删除所有的5迭代器
	//while (pos != s.end()&&*pos==5)
	//{
	//	// 如果直接删除，就会导致迭代器失效
	//	auto next = pos;
	//	next++;
	//	s.erase(pos);
	//	pos = next;
	//}

	// 第二种就是直接删除值
	cout << s.erase(5) <<endl;

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

    • 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

    五、map

    map的insert

    single element (1)	pair<iterator,bool> insert (const value_type& val);
with hint 	   (2)	iterator insert (iterator position, const value_type& val);
range 		   (3)	template <class InputIterator>
  					void insert (InputIterator first, InputIterator last);

    • 1
    • 2
    • 3
    • 4

    数据类型：

    key_type | The first template parameter (Key)
    mapped_type | The second template parameter (T)
    value_type | pair

    pair的构造函数：

    default 		(1)	pair();
copy 			(2)	template<class U, class V> pair (const pair<U,V>& pr);
initialization  (3)	pair (const first_type& a, const second_type& b);

    • 1
    • 2
    • 3

    make_pair较于pair的优势就是它是一个函数模板，可以自动推导参数的类型

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

    • 1
    • 2
    • 3
    • 4
    • 5
    void testmap1()
{
	// 字典
	map<string, string> dict;
	// 1、直接构造对象
	pair<string, string> kv1("sort", "排序");
	dict.insert(kv1);

	// 2、匿名对象进行构造
	dict.insert(pair<string, string>("study", "学习"));

	// 3、make_pair是一个函数模板，本质也是\
	返回一个pair的匿名对象,可以自动推导类型
	dict.insert(make_pair("test", "测试"));

	auto it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ": " << it->second << endl;
		//cout << (*it).first << ": " << (*it).second << endl;
		++it;
	}
}

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

    重点operator[ ]

    统计水果出现的次数

    // 第一种：通过查找的方式统计
void testmap2()
{
	string fruits[] = { "香蕉","香蕉",
	"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	//key是水果名称，value是该水果出现的次数
	map<string, int> countMap;
	for (auto& str : fruits)
	{
		auto ret = countMap.find(str);
		if (ret == countMap.end())
		{
			// 没找到，说明要插入
			countMap.insert(make_pair(str, 1));
		}
		else
		{
			ret->second++;
		}
	}
	//范围for相当于 kv=*it 这个操作
	for (auto& kv : countMap)
	{
		cout << kv.first <<" : " << kv.second << endl;
	}
	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

    这种方法的统计有缺陷，就是第一次会查找该值在不在map中，如果在直接value++，如果不在会进行插入操作，插入时又会进行一次查找操作，不免效率会低一点

    改进
    利用如下insert函数

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

    • 1

    利用这个insert，它会返回一个pair对象，其成员pair::first设置为一个迭代器，指向新插入的元素或映射中具有等效键的元素。如果插入了新元素，则对键值对中的pair::second元素设置为true ，如果已存在等效键，则设置为false 。

    如果不存在，则返回新插入位置的迭代器，second设置为true
    如果已存在，则返回已经存在位置的迭代器，second设置为false

    // 第二种：改进第一种
void testmap3()
{
	string fruits[] = { "香蕉","香蕉",\
	"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	//key是水果名称，value是该水果出现的次数
	map<string, int> countMap;
	for (auto& str : fruits)
	{
		//pair insert(const value_type & val);
		auto pair = countMap.insert(make_pair(str,1));
		if (pair.second == false)
		{
			pair.first->second++;
		}
	}

	//范围for相当于 kv=*it 这个操作
	for (auto& kv : countMap)
	{
		cout << kv.first << " : " << kv.second << endl;
	}
	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

    使用operator[ ]

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

    • 1
    // 第三种：operator[]
void testmap4()
{
	string fruits[] = { "香蕉","香蕉",\
	"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	map<string, int> countMap;

	for (auto& str : fruits) 
	{
		countMap[str]++;//一句代码即可统计
	}

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

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

    以前的[ ]都是数组行为，这里的[ ]的传入的是key，返回的是value的引用，进一步看看[ ]的调用等价于：

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

//简化一下
mapped_type& operator[] (const key_type& k)
{
	pair<iterator,bool> ret =insert(make_pair(k,mapped_type()));
	return ret.first->second;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在这里插入图片描述
    这里统计次数second给的模板参数是int( )，为0，++过后变为1了，所以虽然刚开始新插入的int为0，返回值是value的引用，所以可以统计次数了。
    1、水果第一次出现，插入+修改
    2、水果不是第一次出现，查找+修改

    总结一下[ ]的作用

    • 插入
    • 查找
    • 修改
    void testmap5()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("test", "测试"));
	dict.insert(make_pair("left", "左边"));

	dict["left"] = "剩余";// 修改left
	dict["hello"];// 没有此key，充当插入的作用 
	cout << dict["sort"] << endl;// 有这个key，充当查找
	dict["C++"] = "C加加";// 充当插入+修改
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    六、multimap

    与map使用几乎相同，它允许key冗余，但是没有operator[ ]

    multimap的insert

    void testmultimap()
{
	// 允许key冗余
	multimap<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("test", "测试"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "留下"));
	for (auto& kv : dict)
	{
		cout << kv.first << " : " << kv.second << endl;
	}
	cout << endl;

	// 计数
	cout << dict.count("left") << endl;
}

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

    七、OJ题

    1. 本公司现在要给公司员工发波福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多，但是却又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的k种水果，并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数，并且求出大家最喜欢吃的前k种水果。

    第一种：

    //OJ题
//统计最相爱的前k个水果
struct CountVal
{
	bool operator()(const pair<string,int>& l, const pair<string, int>& r)
	{
		return l.second > r.second;
	}
};
void GetFavoriteFruit1(const vector<string>& fruits,size_t k) 
{
	map<string, int> countMap;

	// 统计次数
	for (auto& str : fruits)
	{
		countMap[str]++;
	}
	
	// 找前k个——topk问题
	//1、数据量不大，我们可以排序
	// 首先我们想要使用sort，必须传入随机迭代器的容器\
	所以我们把数据插入到vector>中
	vector<pair<string, int>> sortV;
	for (auto& kv : countMap)
	{
		sortV.push_back(kv);
	}
	sort(sortV. begin(), sortV.end(),CountVal());

	for (int i = 0; i < k; i++)
	{
		cout << sortV[i].first << ":" << sortV[i].second << endl;
	}
}
void test1()
{
	vector<string> fruits = { "香蕉","香蕉","梨",\
	"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit1(fruits,3);
}

    • 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

    第一种改进的版本：

    struct CountIterator
{
	bool operator()(const map<string, int>::iterator& l, map<string, int>::iterator& r)
	{
		return l->second > r->second;
	}
};
void GetFavoriteFruit1(const vector<string>& fruits,size_t k) 
{
	map<string, int> countMap;

	// 统计次数
	for (auto& str : fruits)
	{
		countMap[str]++;
	}
	
	// 找前k个——topk问题
	// 改进：在vector中存map的迭代器，迭代器比pair小，更加节省空间
	vector <map<string, int>::iterator> sortV;
	auto it = countMap.begin();
	while (it != countMap.end())
	{
		sortV.push_back(it);
		it++;
	}
	sort(sortV.begin(), sortV.end(), CountIterator());
	for (int i = 0; i < k; i++)
	{
		cout << sortV[i]->first << ":" << sortV[i]->second << endl;
	}
}
void test1()
{
	vector<string> fruits = { "香蕉","香蕉","梨","香蕉",
		"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit1(fruits,3);
}

    • 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

    第二种：

    //2、可以使用multimap
void GetFavoriteFruit2(const vector<string>& fruits, size_t k)
{
	map<string, int> countMap;
	// 统计次数
	for (auto& str : fruits)
	{
		countMap[str]++;
	}
	
	multimap<int, string,greater<int>> sortMap;
	for (auto& kv : countMap)
	{
		sortMap.insert(make_pair(kv.second, kv.first));
	}

	auto it = sortMap.begin();
	while (it != sortMap.end())
	{
		cout << it->second << " : " << it->first << endl;
		it++;
	}
}
void test1()
{
	vector<string> fruits = { "香蕉","香蕉","梨","香蕉",
		"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit2(fruits,3);
}

    • 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

    第三种：

    struct CountVal
{
	bool operator()(const pair<string,int>& l, const pair<string, int>& r)
	{
		return l.second < r.second;
	}
};
void GetFavoriteFruit3(const vector<string>& fruits, size_t k)
{
	map<string, int> countMap;
	// 统计次数
	for (auto& str : fruits)
	{
		countMap[str]++;
	}
	//3、可以使用priority_queue
	priority_queue<pair<string, int>, vector<pair<string, int>>, CountVal> qp;
	for (auto& kv : countMap)
	{
		qp.push(kv);
	}
	while (k--)
	{
		cout << qp.top().first << ":" << qp.top().second << endl;
		qp.pop();
	}
}
void test1()
{
	vector<string> fruits = { "香蕉","香蕉","梨","香蕉",
		"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit3(fruits,3);
}

    • 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

    第三种改进版本：

    struct CountIterator
{
	bool operator()(const map<string, int>::iterator& l, map<string, int>::iterator& r)
	{
		//return l->second > r->second;
		return l->second < r->second;
	}
};
void GetFavoriteFruit3(const vector<string>& fruits, size_t k)
{
	map<string, int> countMap;

	// 统计次数
	for (auto& str : fruits)
	{
		countMap[str]++;
	}
	
	priority_queue<map<string, int>::iterator, vector<map<string, int>::iterator>, CountIterator> pq;
	auto it = countMap.begin();
	while (it != countMap.end())
	{
		pq.push(it);
		++it;
	}

	while (k--)
	{
		cout << pq.top()->first << ":" << pq.top()->second << endl;
		pq.pop();
	}
}
void test1()
{
	vector<string> fruits = { "香蕉","香蕉","梨","香蕉",
		"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit3(fruits,3);
}

    • 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
    1. 前K个高频单词
      给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
      返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字典顺序排序。

    示例 1：
    输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
    输出: [“i”, “love”] 解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 “i” 在 “love” 之前。

    sort的底层是快速排序，它是不稳定的一个排序，可能OJ过不了。
    我们可以选择一个稳定的排序:std::stable_sort，下面所使用的的是multimap来进行排序操作的，也可以完成。

    class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> countMap;
        // 统计次数
        for(auto &str: words)
        {
            countMap[str]++;
        }

        // 排序操作
        // 按照value来排序，排降序传入greater
        multimap<int,string,greater<int>> sortMap;
        for(auto & kv: countMap)
        {
            sortMap.insert(make_pair(kv.second,kv.first));
        }

        // 拿到前k个
        vector<string> v;
        auto it=sortMap.begin();
        while(k--)
        {
            v.push_back(it->second);
            ++it;
        }
        return v;
    }
};

    • 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
  • 相关阅读:
    递归回溯实战+思想
    网课答案公众号搭建！小白教程！内附网课题库接口！
    进入docker容器内部使用命令行工具
    【freeRTOS】操作系统之五.-内存管理
    CRM与销售能力自动化SFA的关系
    flyway7.1.1适配人大金仓postgres版本
    Unity程序员如何提升自己的能力
    【Dotnet 工具箱】JIEJIE.NET - 强大的 .NET 代码混淆工具
    MyBatis配置及单表操作
    【教3妹学算法-每日1题】按字典序排在最后的子串
  • 原文地址：https://blog.csdn.net/weixin_57675461/article/details/126338026