大家好，我是店小二！今天为大家带来 C++ STL 树形结构容器全解析：map、set、multimap、multiset 的使用与区别。本次分享主要聚焦于这几种容器的使用方法，帮助大家了解它们的基本功能和常用接口。需要提前说明的是，今天的内容偏重实用性，旨在让大家快速上手，没有深入探讨底层原理。希望能对大家有所帮助！

?个人主页：是店小二呀
?C语言笔记专栏：C语言笔记
?C++笔记专栏： C++笔记
?初阶数据结构笔记专栏： 初阶数据结构笔记
?Linux笔记专栏： Linux笔记

?喜欢的诗句:无人扶我青云志 我自踏雪至山巅

一、序列式容器与关联式容器

• 序列式容器:底层为线性序列的数据结构，里面存储的是元素本身，单纯的存储数据，存储的数据和数据之间没有啥关联，比如，vector、list、deque等容器
• 关联式容器:也是用于存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。不仅仅是存储数据，一般还可以查找数据，存储的数据和数据之间很强关联性

二、键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，其中key代表健值，而value表示与key对应的信息。比如:字典中必然存在英文单词与其对应的中文含义

三、树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，采用中序遍历，容器中的元素是一个有序的序列

四、set

4.1 set介绍

[set文档介绍](set - C++ Reference (cplusplus.com)):

1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的，对此插入元素时，只需要插入value即可，不需要构造键值对
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序
4. set中的元素不可以重复(因此可以使用set进行去重)
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：O(logn)
7. set中的元素不允许修改，保证数据排序和搜索树结构
8. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代
9. 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对
10. set中的底层使用二叉搜索树(红黑树)来实现

3.2 set相关接口使用

提前声明:set和map容器接口在使用方面是类型的，在set和map章节对于学习过的知识点不会过于展开描述，展示几个常见的接口。

map的模板参数说明：

• T: set中存放元素的类型，实际在底层存储的键值对。
• Compare：set中元素默认按照小于来比较，仿函数
• Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
• set属于K模型搜索，具有去重和排序的功能。

3.2.1 set构造函数

1.set无参构造

int main()
{
	set<int> s1;
	s1.insert(1);
	s1.insert(2);
	s1.insert(3);
	s1.insert(1);

	set<int> ::iterator it = s1.begin();
	while (it != s1.end())
	{
		//*it = 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

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

其中需要知道set中的元素不允许修改，保证数据排序和搜索树结构。

2.set迭代器区间构造

int main()
{
    vector<int> v = { 3, 2, 8, 1, 10, 2 };
    set<int> s(v.begin(), v.end());

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

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

3.调用列表初始化

int main()
{
    set<int> s3 = { 3,2,8,1,10,2 };
    for (auto e : s3)
    {
        cout << e << " ";
    }
    cout << endl;
    s3.erase(8);
    s3.erase(18);
    for (auto e : s3)
    {
        cout << e << " ";
    }
    cout << endl;

    auto pos = s3.find(10);
    if (pos != s3.end())
    {
        cout << *pos << endl;
        s3.erase(pos);
    }
    else
    {
        cout << "找不到" << endl;
    }
    for (auto e : s3)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

• 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

3.2.2 set常见接口

#include 
void TestSet()
{
    // 用数组array中的元素构造set
    int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
                   6, 8, 0 };
    set<int> s(array, array+sizeof(array)/sizeof(array));
    cout << s.size() << endl;
    // 正向打印set中的元素，从打印结果中可以看出：set可去重
    for (auto& e : s)
        cout << e << " ";
    cout << endl;
    // 使用迭代器逆向打印set中的元素
    for (auto it = s.rbegin(); it != s.rend(); ++it)
        cout << *it << " ";
    cout << endl;
    // set中值为3的元素出现了几次
    cout << s.count(3) << endl;
}

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

3.3 set相关题目练习

我们需要知道，set是间接实现去重操作，如果存在该值就不再插入到set里面。

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> v;
        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 > *it2) it2++;
            else if(*it1 < *it2) it1++;
            else if(*it1 == *it2)
            {
                v.push_back(*it1);
                it1++;it2++;
            }
        }
        return v;
    }
};这里拿出来的目的是体现了set的排序和去重的作用，在这种情况下可以帮助我们快速的做题。

• 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

五、multiset

5.1 multiset介绍

multiset当作可以set使用，同样属于key模型，区别在于muliset允许数据冗余也就是不去除重复数据。muliset是一种允许元素重复出现的集合类型，你可以像使用set一样使用它，但它会保留重复的元素并且不进行去重操作。

5.2 multiset使用

int main()
{
	multiset<int> s1;
	s1.insert(1);
	s1.insert(11);
	s1.insert(3);
	s1.insert(1);
	s1.insert(4);
	s1.insert(2);
	s1.insert(4);
	s1.insert(2);
	s1.insert(1);
	s1.insert(2);
	s1.insert(1);

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

	auto pos = s1.find(2);
	while (pos != s1.end() && *pos == 2)
	{
		cout << *pos << " ";
		++pos;
	}
	return 0;
}

• 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

六、map

6.1 map介绍

[map文档介绍](map - C++ Reference (cplusplus.com)):

• map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素
• 在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。
• 键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair value_type;
• 在内部，map中的元素总是按照键值key进行比较排序的。
• map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
• map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
• map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

map的模板参数说明：

• key: 键值对中key的类型
• T： 键值对中value的类型
• Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
• Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
• 注意：在使用map时，需要包含头文件

key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair value_type;的意思就是说，之前key和value是单个单个的存储的，现在将key和value存在一个结构中。

6.2 掌握pair与make_pair

6.2.1 pair

在 C++ 中，pair 确实是一个模板类，允许用户将两个不同类型的数据组合在一起。模板的关键特性是它能够为不同类型的元素提供通用的实现，因此 pair 能够处理任意类型的两个数据项。

pair底层实现逻辑

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;

    //Key
	T1 first;
    //value
	T2 second;
	
	pair():first(T1(), 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
• 14
• 15
• 16

6.2.2 make_pair

make_pair 是 C++ 标准库中的一个函数模板，用于简化 std::pair 对象的创建。它可以自动推导出 pair 的类型，因此在构造 pair 对象时，无需显式地指定模板参数类型。

6.2.3 pair与make_pair区别

相对于pair使用中需要明确数据类型，而make_pair是函数模板可以自动去推类型

• 函数模板：支持类型推导，编译器根据传递的参数自动推导模板参数。
• 类模板：不支持类型推导，必须显式指定模板参数类型，因为类的结构和使用方式更复杂，无法通过简单的参数推导出类型。

6.3 map对象多种插入场景

int main()
{
    map<string, string> dict;
    pair<string, string> kv1("sort", "排序"); dict.insert(kv1);

    //使用匿名对象
    dict.insert(pair<string, string>("left", "左边"));

    //使用make_pair,省略类型的书写
    dict.insert(make_pair("right", "右边"));

    //隐式类型转化
    pair<string, string> kv2("string", "字符串");
    dict.insert({ "string", "字符串" });

    //初始化列表
    map<string,string> dic2 = { {"string", "字符串"}, {"left", "左边"}, {"right", "右边"} };
    return 0;
}

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

**关于以上两种map初始化的方式，推荐使用第一种写法。**同时需要注意的是dict.insert({ "string", "字符串" });这里不是列表初始化initializelist，而是调用pair构造函数，强制类型转化为pair类型插入数据。

6.3.1 map当中列表初始化

而对于map dic2 = { {"string", "字符串"}, {"left", "左边"}, {"right", "右边"} };属于初始化列表， std::map 的构造函数接受一个std::initializer_list> 类型的参数。所以当你使用 {"i", "dd"} 进行初始化时，它会被转换为 std::pair 类型，然后添加到 map 中。

6.4 将数据存在结构体

我们知道map中的元素类型是pair或make_pair，但是为什么map不分开来存储数据呢？而是需要将数据放在一个结构体中，通过结构体间接访问这些对象。

//map::iterator it = dict.begin();
//auto的作用就重复体现到了
auto it = dict.begin();
while (it != dict.end())
{
    // iterator key不能修改 value可以修改
    // const_iterator key不能修改 value不能修改
    //it->first += 'x';
    it->second += 'x';
    ++it;
}
cout << endl;

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

关于key不是能被修改的。在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。对此key是不能随意修改的，可能会破坏搜索树结构，但key所对的内容value是支持修改的。

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

• 1
• 2
• 3
• 4
• 5
• 6

对于如果不将key和value放在同一个结构体中，operator *只能返回一个值，但是我们希望可以得到key也可以得到value的值，对此将这两个变量放在结构体中，间接调用这两个变量，就会不出现冲突。对于上面的写法过于麻烦，这里喜欢使用→来解引用。

底层是调用operator ->接口，这里编译器会省略一个箭头进行优化，使得使用更加便捷。

6.5 map相关接口使用

6.5.1 erase

这里使用insert不会出现迭代器实现的问题，而erase可能会出现迭代器失效的问题，这里搜索树可以看成链表的加强版。

6.5.2 operaor[]

首先这里operator不是通过下标进行访问，而是通过key来进行访问对应value。关于operator[]实现不是通过find来实现而是通过insert来实现。

6.5.3 insert实现operator[]

解释上面两段话

• key存在，插入失败，返回 ->pair < 存在的key所在节点的迭代器，false>
• key不存在，插入成功，返回 ->pair < 新插入key所在节点的迭代器，true>

对此我们可以看出来，insert在find功能基础上增加了插入的功能。这里insert的功能就是查找 + 插入(如果该元素存在，就是查找)

6.5.4 operaort[] 底层逻辑

V& operator[](const K& key)
{
    // 不管插入成功还是失败，pair中iterator始终指向key所在节点的iterator
    //这个V()就是调用默认构造，不是一个明确的数值
    pair<iterator, bool> ret = this->insert(make_pair(key, V()));
    iterator it = ret.fisrt;
    return it->second;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

八、map使用方面

8.1 operator[]使用

int main()
{
    map<string, string> dict;
    dict.insert({ "string", "字符串" });

    // 插入（一般不会这么用，单纯的插入）
    dict["right"];

    // 插入left + 修改 left对应内容
    dict["left"] = "左边";

    // "查找"
    cout << dict["string"] << endl;

    // 修改
    dict["right"] = "右边";

    string str;
    cin >> str;
    if (dict.count(str))
    {
        cout << "在" << endl;
    }
    else
    {
        cout << "不在" << endl;
    }
    return 0;
}

• 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

8.2 如何统计水果出现的次数并排序（map用法和排序稳定性）

瑕疵版本

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
                "苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
map<string, int> countMap;
for (auto& e : arr)
{
    auto it = countMap.find(e);
    if (it != countMap.end())
    {
    	it->second++;
    }
    else
    {
    	//const pair& val = { e, 1 };
    	countMap.insert({ e, 1 });
    }
}

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

优化版本

通过operator[]学习，我们可以对上面代码进行优化。

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

	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

通过次数来排序

只需将countMap的first和second位置数据，分别存放在sortMap的second和first位置上就行了

	map<int, string> sortMap;
	for (auto& kv : countMap)
	{
		//sortMap[kv.second] = kv.first;
		sortMap.insert({ kv.second, kv.first });
	}
	cout << endl;

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

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

这里问题就是香蕉不见。对此我们知道map底层是通过搜索树实现的，而二叉搜索树是不允许冗余数据，并且是通过K对比较的，如果出现重复的K不会进行插入操作。（现在是次数对内容，而不是内容对次数，搞清楚K现在是谁)

multimap允许冗余

真的需要排序，可以使用multimap 允许冗余.

8.3 前K个高频单词

如果是单纯排序话，可以符合按照次数进行排序，但是无法满足第二个需求，对此我们改写排序内部逻辑。

将内容插入map时完成了按照字典序排序的需求，但是接下来的快速排序属于不稳定排序，会破坏之前元素之间的相对位置，我们也可以将问题转换为使用一个稳定性好的排序，比如归并排序，map也提供了一个接口stable是稳定排序。

九、multimap

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

multimap使用事项:

1. Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对，其中多个键值对之间的key是可以重复的
2. 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，
3. value_type是组合key和value的键值对:typedef pair value_type;
4. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
5. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
6. multimap在底层用二叉搜索树(红黑树)来实现。
7. multimap中的key是可以重复的。
8. multimap中的元素默认将key按照小于来比较
9. multimap中没有重载operator[]操作，允许数据冗余，那么查找有冲突
10. 使用时与map包含的头文件相同

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！