【C++】数据结构的恶龙set和map来了~

下一篇AVL树难点中的难点~

文章目录

前言
一、set的介绍
二、map的介绍
题目练习
总结

前言

1.关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、

forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面

存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其 里面存储的是 <key, value> 结构的

键值对，在数据检索时比序列式容器效率更高

2.键值对

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

表键值， value 表示与 key 对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然

有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应

该单词，在词典中就可以找到与其对应的中文含义。

3.树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。 树型结

构的关联式容器主要有四种： map 、 set 、 multimap 、 multiset。这四种容器的共同点是：使

用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一

个容器。

一、set的介绍

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

2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。

set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。

3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行

排序。

4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对

子集进行直接迭代。

5. set在底层是用二叉搜索树(红黑树)实现的。

set的注意事项：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放

value，但在底层实际存放的是由<value, value>构成的键值对。

2. set中插入元素时，只需要插入value即可，不需要构造键值对。

3. set中的元素不可以重复(因此可以使用set进行去重)。

4. 使用set的迭代器遍历set中的元素，可以得到有序序列

5. set中的元素默认按照小于来比较。

6. set中查找某个元素，时间复杂度为：O(n)

7. set中的元素不允许修改(为什么?)

8. set中的底层使用二叉搜索树(红黑树)来实现

下面我们来使用一下set:

void test_set1()
{
	set<int> st;
	st.insert(1);
	st.insert(2);
	st.insert(3);
	st.insert(1);
	st.insert(3);
	st.insert(4);
	set<int>::iterator it = st.begin();
	while (it != st.end())
	{
		cout << *it << " ";
		++it;
	}
}
int main()
{
	test_set1();
	return 0;
}

set的使用与我们之前学的容器相差不大，大家只需要记住set的作用是排序+去重，当然set既然支持迭代器那么也肯定支持范围for了。

在这里我们要注意，set是不支持修改里面的值的，因为一旦修改了就不能保持搜索二叉树的特性了。下面我们演示一下set中的find和count接口：

void test_set2()
{
	set<int> st;
	st.insert(1);
	st.insert(2);
	st.insert(3);
	st.insert(1);
	st.insert(3);
	st.insert(4);
	auto it = st.find(4);
	if (it != st.end())
	{
		cout << "要查询的值存在：" << *it << endl;
	}
	else
	{
		cout << "不存在" << endl;
	}
}
int main()
{
	//test_set1();
	test_set2();
	return 0;
}

void test_set2()
{
	set<int> st;
	st.insert(1);
	st.insert(2);
	st.insert(3);
	st.insert(1);
	st.insert(3);
	st.insert(4);
	if (st.count(4))
	{
		cout << "要查询的值存在" << endl;
	}
	else
	{
		cout << "不存在" << endl;
	}
}

在set中我们确认一个值用count接口会比find更方便，因为如果存在那么count一定是1，如果不存在则是0.count这个接口是为了和multiset中的count对应。

下面我们来看看multiset:

void test_set3()
{
	multiset<int> st;
	st.insert(1);
	st.insert(2);
	st.insert(3);
	st.insert(1);
	st.insert(3);
	st.insert(4);
	for (auto& e : st)
	{
		cout << e << " ";
	}
	
}

通过结果我们可以看到multiset的功能仅仅是排序，并不会去重，下面我们看看刚刚说到的multiset中的count:

void test_set3()
{
	multiset<int> st;
	st.insert(1);
	st.insert(2);
	st.insert(3);
	st.insert(1);
	st.insert(3);
	st.insert(4);
	for (auto& e : st)
	{
		auto it = st.find(e);
		if (it != st.end())
		{
			cout << e << "的个数为:" << st.count(e) << endl;
		}
		else
		{
			cout << "找不到" << endl;
		}
	}
	
}

我们可以看到在multiset中count可以准确的计算元素的数量，下面我们看看find接口：

void test_set3()
{
	multiset<int> st;
	st.insert(1);
	st.insert(1);
	st.insert(1);
	st.insert(1);
	st.insert(1);
	st.insert(1);
	auto it = st.find(1);
	while (it != st.end()&&*it == 1)
	{
		cout << *it << " ";
		++it;
	}
}

对于find接口来讲，查找到的元素一定是中序遍历的第一个元素，如果不是这样的原则我们上面的打印是不会将所有1打印出来的。

set的其他接口我们就不再演示了，因为与其他STL容易相差并不大，只需要记住几个有差异的接口就可以了。

二、map的介绍

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元

素。

2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的

内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型

value_type绑定在一起，为其取别名称为pair:

typedef pair<const key, T> value_type;

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

4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序

对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。

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

6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

我们前面已经说过了，map里面存的是键值对，下面我们演示一下map的使用：

void test_map1()
{
	map<string, string> mp;
	mp.insert(make_pair("string", "字符串"));
	mp.insert(make_pair("left", "左边"));
	mp.insert(make_pair("right", "右边"));
	mp.insert(make_pair("erase", "删除"));
	mp.insert(make_pair("string", "字符串2"));
	auto it = mp.begin();
	while (it != mp.end())
	{
		cout << (*it).first << ":" << (*it).second << endl;
		++it;
	}
}

我们可以看到map同样是排序+去重，当然如果看不懂make_pair是什么那么我们写的再原始一点：

如上图所示绿色的是原始的pair插入，对于打印为什么是first和second呢？因为pair这个结构里存的就是K,V键值对，并且first代表key,second代表value.当然还记得我们在写反向迭代器的时候重载的那个->符号吗，在这里也有哦：

在这里->本来要用两次，因为首先访问到结构体，其次再访问到结构体里的first或者second,但是现在一个->就搞定了因为重载了->符号。下面我们讲一下在map中最重要的[]符号：

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

还记得我们学二叉搜索树的时候用的水果的例子吗？当我们树中已经存在这个水果了我们就让水果的count++，如果不存在这个水果我们就让插入并且count值为1，如今有了方括号我们1行代码就能搞定：

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

是不是很神奇呢？下面我们来重点介绍一个[]运算符：

从文档中我们可以知道[]有多个作用，首先我们要看懂[]的返回值，如果要插入的值在当前树中不存在我们就插入，如果存在（如何判断是否存在是因为插入有一个bool值）就返回second的值（准确来说是引用），这也就解释了我们刚刚那个代码，因为当要插入的水果不存在的时候就直接帮我们插入了，并且插入后返回了此种水果的次数，然后我们后置++让这个水果变成了1次，后面如果发现这种水果已经被插入了就不在插入了但是返回值返回的是水果的次数的引用所以我们会再次++让次数变成2，然后重复。也就是说[]有四个作用：1.插入 2.修改 3.插入+修改 4.查找

void test_map1()
{
	map<string, string> mp;
	mp.insert(make_pair("string", "字符串"));
	mp.insert(make_pair("right", "右边"));
	mp.insert(make_pair("erase", "删除"));
	mp["left"];   //仅仅插入
	mp["second"] = "第二";   //插入加修改 因为返回值是second,我们将默认的second修改为"第二"
	mp["string"] = "字符串2";   //修改
	cout << mp["string"] << endl;  //查找
	auto it = mp.begin();
	while (it != mp.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
}

如果我们仅仅想要用[]插入，这个时候插入的是key模型，value会使用缺省值，比如我们方面的插入left，最后打印发现left的value值为空，这就可以验证当value的类型为字符串时缺省值为空字符串，当我们想要插入加修改时，因为[]的返回值为value的引用，所以相当于我们把缺省值修改为自己想要的value值，如果仅仅要对某个key的value值修改我们可以借助[]的返回值进行修改，以上就是map的一些知识，下面我们讲解multimap的知识：

1. Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key,

value>，其中多个键值对之间的key是可以重复的。

2. 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内

容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，

value_type是组合key和value的键值对: typedef pair<const Key, T> value_type;

3. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对

key进行排序的。

4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代

器直接遍历multimap中的元素可以得到关于key有序的序列。

5. multimap在底层用二叉搜索树(红黑树)来实现。

注意： multimap 和 map 的唯一不同就是： map 中的 key 是唯一的，而 multimap 中 key 是可以

重复的。

multimap与multiset一样，都是支持键值冗余，也可以理解为仅仅排序不去重，与map不同的是，由于multimap的键值不再是一一对应的关系了，所以multimap没有了[]运算符重载。下面我们演示一下：

void test_map1()
{
	multimap<string, string> mp;
	mp.insert(make_pair("string", "字符串1"));
	mp.insert(make_pair("string", "字符串2"));
	mp.insert(make_pair("string", "字符串3"));
	mp.insert(make_pair("left", "左边"));
	mp.insert(make_pair("right", "右边"));
	for (auto& e : mp)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

当然multimap虽然没有了[]运算符，但是count还是比较有用的：

void test_map1()
{
	multimap<string, string> mp;
	mp.insert(make_pair("string", "字符串1"));
	mp.insert(make_pair("string", "字符串2"));
	mp.insert(make_pair("string", "字符串3"));
	mp.insert(make_pair("left", "左边"));
	mp.insert(make_pair("right", "右边"));
	if (mp.count("string"))
	{
		cout << "string的个数：" << mp.count("string") << endl;
	}
}

在multimap和multiset中count都可以计算出某个key的个数，以上就是map和set的基本用法以及一些重要功能的讲解，下面我们讲一道题练习一下map和set。

三.题目练习

力扣：前K个高频单词

力扣链接：力扣

看到这道题大家应该首先想到的就是map了吧，毕竟题目已经很明显的说了KV键值对，下面我们说一下思路：首先我们用mp的[]功能统计出每个单词出现的次数以及对应的每个单词，然后我们将前K个这样的单词放入向量中，然后打印即可：

class Solution {
public:
    struct compare
    {
        bool operator()(const pair<string,int>& k1,const pair<string,int>& k2)
        {
            return k1.second>k2.second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> mp;
        for (auto& e:words)
        {
            mp[e]++;
        }
        vector<pair<string,int>> v(mp.begin(),mp.end());
        sort(v.begin(),v.end(),compare());
        vector<string> result;
        for (int i = 0;i<k;i++)
        {
            result.push_back(v[i].first);
        }
        return result;
    }
};

首先我们用一个map来计算单词以及单词的次数，然后用一个vector来保存这些键值对（vector的类型一定是pair），然后我们用sort函数排序vector,由于pair默认的排序方式是以K值进行排序的，所以我们必须写一个仿函数来用键值对中的value值比较，比较完成后我们用另一个vector来接收前K个字符串，最后我们只需要返回string即可所以是v[i].first。但是如果我们发现没有通过，如下图：

发现错误的原因是单词的顺序不对，当出现相同次数的单词需要用字典序来排序，所以这个时候我们就想到了排序的稳定性，如果一个排序稳定的话相同的值的相对顺序是不变的，本题给的测试列表本来也是按照字典序排好的，所以我们直接换一个稳定排序就解决了，在算法中有一个稳定排序：

下面我们就换上这个稳定排序：

这样我们就通过了，那么如果我们还有其他办法解决刚刚的顺序问题吗？答案是当然有，要知道我们写仿函数的目的就是为了控制比较方式：

当然我们也可以用我们刚刚学的的set来进行比较，因为我们的set和map也是支持控制比较方式的：

class Solution {
public:
    struct compare
    {
        bool operator()(const pair<string,int>& k1,const pair<string,int>& k2) const
        {
            return k1.second>k2.second||(k1.second==k2.second)&&k1.first<k2.first;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> mp;
        for (auto& e:words)
        {
            mp[e]++;
        }
        set<pair<string,int>,compare> st(mp.begin(),mp.end());
        vector<string> v;
        auto it = st.begin();
        while (k--)
        {
            v.push_back(it->first);
            ++it;
        }
        return v;
    }
};

在这里大家要注意：