C++ set、map、multiset和multimap容器

前言

1. 关联式容器和序列式容器

关联式容器

序列式容器

主要区别

2. 键值对

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

2.1 set

2.1.1 介绍

2.1.2 构造函数

2.1.3 迭代器

2.1.4 修改操作

2.1.5 容量相关

2.2 multiset

2.3 map

2.3.1 介绍

2.3.2 构造函数

2.3.3 迭代器

2.3.4 修改操作

2.3.5 容量与元素访问

2.4 multimap

总结

前言

本文将重点探几种种基于树形结构的关联式容器set、multiset、map和multimap。这这四种容器在C++标准库中占据着重要地位，它们不仅提供了强大的数据存储和检索功能，还各自具备独特的特性，如自动排序、键值对的存储以及多键值的支持。接下来，我们将详细介绍他们的特性和用法，帮助读者更好地理解和运用树形结构关联式容器。

1. 关联式容器和序列式容器

在C++等编程语言中，关联式容器（Associative Containers）和序列式容器（Sequential Containers）是两种主要的容器类型，它们在存储元素的方式和性能特点上有所不同。

关联式容器

关联式容器的主要特点是它们可以快速地通过关键字（key）来查找和访问元素。常见的关联式容器包括：

set：存储不重复的元素集合，元素自动按照关键字排序。
map：存储键值对，每个键是唯一的，可以根据键快速找到对应的值。
multiset：与set类似，但允许重复的元素。
multimap：与map类似，但允许重复的键。

特点：

元素是按照关键字来存储和检索的。
通常通过平衡二叉搜索树（如红黑树）实现，保证了查找、插入和删除操作的时间复杂度为对数级，通常是O(log n)。
不支持快速随机访问。

序列式容器

序列式容器存储元素的方式是按照元素的插入顺序来组织的。常见的序列式容器包括：

vector：可以动态扩展的数组。
list：双向链表。
deque：双端队列，可以在两端快速插入和删除。
forward_list：单向链表，从C++11开始引入。

特点：

元素是按照插入顺序来存储和检索的。
支持快速随机访问（除了list和forward_list）。
对于vector和deque，在容器的末尾添加或删除元素效率较高，但在中间插入或删除元素则可能较低。
对于list，在任何位置插入和删除元素的效率都比较高。

主要区别

数据组织方式：关联式容器基于关键字，序列式容器基于插入顺序。
访问元素：关联式容器通常通过关键字访问，而序列式容器可以通过位置或迭代器访问。
性能：关联式容器在查找、插入和删除操作上通常有更好的性能保证，尤其是当元素数量较多时；序列式容器在元素的顺序处理上有优势。
用途：关联式容器适用于需要快速查找和访问元素的情况，而序列式容器适用于元素的处理顺序很重要的情况。

2. 键值对

键值对（Key-Value Pair）是一种数据结构，它将一个键（Key）与一个值（Value）关联起来。在键值对中，键是用于唯一标识或查找值的部分，而值是实际存储的数据。现实生活中有许多例子，比如用户账号和用户密码关联形成键值对，英汉词典中的英文都有相对应的中文，构成键值对。

以下是一些关于键值对的要点：

唯一性：在一个键值对集合中，每个键通常是唯一的，这意味着你不能有两个具有相同键的键值对。
查找操作：键值对常用于实现映射或关联数组，其中键用于快速查找对应的值。
数据类型：键和值可以是任意数据类型，但通常键是字符串、数字或其他可以唯一标识值的类型。
常见用途：键值对在多种编程语言和数据库中广泛使用，特别是在实现字典、哈希表、关联数组、映射等数据结构时。

C++中，就有一种模版容器pair，它可以存储两个值，这两个值可以是不同的数据类型。常用于表示一个键值对，或者在需要返回两个结果的情况下使用。这个类有两个成员变量，成员变量类型分别是T1和T2。

make_pair函数可以构造一个pair对象，第一个元素设置为x，第二元素设置为y。

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

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

在STL中，关联式容器总共有两种实现方式：树形结构和哈希结构。树形结构的关联式容器主要有四种：map、set、multimap、multiset。这四个容器的底层结构都是用红黑树实现的，红黑树是一个二叉平衡搜索树。

如果有查找C++11之前相关的语法和容器，可以上这个网址查找-->cplusplus.com - The C++ Resources Network

2.1 set

2.1.1 介绍

set文档介绍的内容如下：

集合是按照特定顺序存储唯一元素的容器。
在set中，元素的值也标识它(值本身就是键，类型为T)，并且每个值必须是唯一的。set中元素的值在容器中不能被修改一次(元素总是const类型)，但是可以从容器中插入或删除它们。
在内部，集合中的元素总是按照其内部比较对象(类型为Compare)所指示的特定严格弱排序标准进行排序。
Set容器在按键访问单个元素时通常比unordered_set容器慢，但它们允许根据顺序直接迭代子集。
集合通常以二叉搜索树的形式实现。(红黑树实现)

下面是set的模版参数列表

T：set中存放的元素类型，在底层存储<value,value>键值对。
Compare：控制set的比较规则，默认按照小于的方式比较，即升序。
Alloc：set中元素空间的管理方式，默认使用STL提供的空间配置管理器。

map中存储的是真正的键值对<key，value>。set中value就是key。

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

2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：$log_2 n$
7. set中的元素不允许修改(为什么?)
8. set中的底层使用二叉搜索树(红黑树)来实现。

2.1.2 构造函数

默认构造函数，构造一个没有元素的容器。
range构造函数，构造一个包含与[first,last)范围相同数量元素的容器，每个元素都由该范围内的相应元素构造。
拷贝构造函数，拷贝同类型x对象中的内容进行构造。
initializer_list构造函数，类似数组花括号，进行构造。

void test_set1()
{//默认构造函数set<int> s1;//range构造vector<int> v = { 5,3,6,2,9,4,8 };set<int> s2(v.begin(), v.end());//拷贝构造set<int> s3(s2);//initializer_list构造set<int> s4 = { 3,8,1,5,3,7, };
}

2.1.3 迭代器

set的迭代器类型是双向迭代器，可以正向或者反向遍历，还有const类型迭代器。但是一般使用普通正向迭代器。set的底层是用红黑树（二叉平衡搜索树）实现，迭代器遍历走的是中序，可以得到有序序列。

下面是迭代器遍历，还有范围for遍历。

void test_set2()
{set<int> s = { 3,8,1,5,3,7 };set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (const auto& e : s){cout << e << " ";}cout << endl;
}

运行结果如下：

2.1.4 修改操作

修改操作如下：

insert操作

set中插入单个元素，实际插入的是<x,x>构成的键值对。如果插入成功，返回该<该元素的迭代器，true>。如果插入失败，说明x在set中已经存在，返回<x的迭代器，false>。
with hint插入函数，第一个参数是提示新元素所在位置，提高插入效率，返回插入元素所在位置的迭代器，如果这个元素已经存在，就返回这个元素的迭代器。
range和initializer_list类型插入函数，根上面的构造函数类似。

void test_set2()
{set<int> s;s.insert(5);s.insert(2);s.insert(7);//用相同类型接受插入函数的返回值，查看是否插入成功pair<set<int>::iterator, bool> in= s.insert(5);cout << in.second <<endl;s.insert(4);s.insert(4);s.insert(5);s.insert(9);s.insert(1);Print(s);set<int> s1;vector<int> v = { 5,3,6,2,9,4,8 };s1.insert(v.begin(), v.end());Print(s1);set<int> s2;s2.insert({ 5,3,6,2,9,4,8 });Print(s2);
}

运行结果如下，打印0，说明插入失败，不允许插入相同元素。因此set可以用来去重。

erase操作

删除迭代器指向的元素。
删除set中值为x的元素，返回删除元素的个数。
删除set中[first，last)区间中的元素。

void test_set4()
{set<int> s1 = { 5,3,6,2,9,4,8 };Print(s1);s1.erase(s1.begin());Print(s1);s1.erase(4);Print(s1);s1.erase(s1.begin(), s1.end());Print(s1);cout << "end";
}

运行结果如下：

返回set中值为val的迭代器

交换set中的元素

将set中的元素清空

返回set中值为val的元素的个数。

下面是测试代码

void test_set5()
{set<int> s1 = { 5,3,6,2,9,4,8 };Print(s1);set<int> s2 = { 8,4,10,11,3,5,7 };Print(s2);s1.swap(s2);Print(s1);Print(s2);cout << endl;set<int>::iterator pos = s1.find(5);s1.erase(pos);Print(s1);s2.clear();Print(s2);cout << "end";
}

运行结果如下：

2.1.5 容量相关

empty函数判断容器是否为空。
size函数返回容器元素个数。

2.2 multiset

cplusplus网站multiset文档内容：

multiset是按照特定顺序存储元素的容器，其中多个元素可以具有相同的值。
在multiset容器中，元素的值也能标识它(值本身就是键，类型为T)。在容器中，multiset元素的值不能修改一次(元素总是const类型)，但可以从容器中插入或删除它们。
在内部，multiset中的元素总是按照其内部比较对象(类型为Compare)所指示的特定严格弱排序标准进行排序。
在按键访问单个元素时，Multiset容器通常比unordered_multiset容器慢，但它们允许根据顺序直接迭代子集。
多集通常以二叉搜索树的形式实现

multiset是可以有相同值元素重复出现。接口可以借鉴set。

void test_multiset()
{multiset<int> ms = { 2,1,3,9,6,0,5,8,4,9,7,2,1,6 };multiset<int>::iterator it = ms.begin();while (it != ms.end()){cout << *it << " ";++it;}cout << endl;//打印9元素出现的次数cout << ms.count(9) << endl;
}

运行结果如下：

2.3 map

2.3.1 介绍

map是一种关联容器，用于存储由键值和映射值按照特定顺序组合而成的元素。
在map中，键值通常用于对元素进行排序和唯一标识，而映射值存储与此键相关的内容。键和映射值的类型可以不同，并在成员类型value_type中组合在一起，value_type是将两者组合在一起的pair类型:typepedef pair<const Key, T> value_type;
在内部，map中的元素总是按照其内部比较对象(类型为Compare)所指示的特定严格弱排序标准的键进行排序。（升序）
Map容器在按键访问单个元素时通常比unordered_map容器慢，但它们允许根据顺序对子集进行直接迭代。
map中的映射值可以使用括号操作符((operator[])通过对应的键直接访问。
map通常以二叉搜索树的形式实现。（红黑树）

Key:键值对中的key的类型
T：键值对中value的类型
Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于比较。一般情况下该参数不需要传递，如果无法比较，需要用户自己显示传递比较器。（使用仿函数）
Alloc：空间配置器

2.3.2 构造函数

构造函数有默认构造，range构造和拷贝构造函数。可以参照set构造函数。需要注意的是，initializer_list函数插入的值是一个pairKey, value>类对象，这是一个结构体。insert函数会介绍几种传参的方法。

2.3.3 迭代器

map迭代器接口跟可以参照set容器。

需要注意的是，对it解引用得到的是pair<key, value>类型的值，这是一个自定义类型值，不能使用cout直接打印，有下面两种操作。

void test_iterator()
{map<string, string> dict = { { "string", "字符串"}, {"insert", "插入"}, {"right", "右边"},{"left", "左边"} };map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << (*it).first << ":" << (*it).second << endl;++it;}cout << endl;it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}
}

2.3.4 修改操作

插入函数类型与set相同。插入单个pair类型对象，有好几种方法。

先创建一个pair类型对象，插入该对象。
匿名对象的生命周期只有这一行，使用pair匿名对象进行插入。
还可以借助make_pair函数返回pair对象。
使用多参数隐式类型转换成pair临时对象。

void test_map1()
{map<string, string> dict;//显示对象插入pair<string, string> kv1("left", "左边");dict.insert(kv1);//匿名对象dict.insert(pair<string, string>("right", "右边"));//make_pair函数返回pair对象值dict.insert(make_pair("insert", "插入"));//多参数隐式类型转换成pair类型dict.insert({ "string", "字符串" });
}

下面是map使用initializer_list构造对象。使用迭代器访问，其中需要注意解引用it得到的是pair类型的值，是一个自定义类型，可以使用operator->符号访问key和value值。

下面是通过key值访问对应的value值。

void test_map2()
{map<string, string> dict = { { "string", "字符串"}, {"insert", "插入"}, {"right", "右边"},{"left", "左边"} };map<string, string>::iterator it = dict.begin();while (it != dict.end()){//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (auto& e : dict){cout << e.first << ":" << e.second << endl;}test_map3(dict);
}void test_map3(map<string, string>& dict)
{cout << "test_map3():" << endl;string str;while (cin >> str){auto ret = dict.find(str);if (ret != dict.end()){cout << "->" << ret->second << endl;}else{cout << "重新输入" << endl;}}
}

运行结果如下：

2.3.5 容量与元素访问

operator[]函数，如果k与map中某个元素的key值匹配，则该函数返回其对应的value值的引用，可以通过operator[]对value进行修改和访问。
如果k与map中任何元素的可抑制不匹配，则该函数用该k值插入一个新元素，并返回其对应value的引用。map容器的大小增加一，即使没有value值赋给元素，会调用默认构造函数。
at()函数也用访问功能，但是出现不匹配的key值，会直接抛异常。

void Printmap(const map<string, string>& dict)
{for (auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;
}void test_map4()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("insert", "插入"));Printmap(dict);dict["left"] += ",剩余";dict["string"];Printmap(dict);
}

运行结果如下：

empty函数判断容器是否为空。
size函数返回容器元素个数。

总结

map的元素是键值对。
map中的key值是唯一的，不能进行修改。
map中使用迭代器实际上是走二叉搜索树的中序遍历，会得到有序序列。
map的底层是一个二叉平衡搜索树（红黑树），查找效率比较高，时间复杂度为O( $\log_{2}n$ )
可以使用[]操作符，operator[]实际使用插入函数进行插入元素。

2.4 multimap

multimap文档介绍如下：

Multimaps是一种关联容器，用于存储按特定顺序由键值和映射值组合而成的元素，其中多个元素可以具有相同的键。（一个key值可以对应多个value值）
在multimap中，键值通常用于对元素进行排序和唯一标识，而映射值存储与该键相关的内容。键和映射值的类型可以不同，并在成员类型value_type中组合在一起，value_type是将两者组合在一起的pair类型: typepedef pair<const Key, T> value_type;
在内部，multimap中的元素总是按照其内部比较对象(类型为Compare)所指示的特定严格弱排序标准的键进行排序。
在按键访问单个元素时，Multimap容器通常比unordered_multimap容器慢，但它们允许根据顺序对子集进行直接迭代。
Multimaps通常以二叉搜索树的形式实现。（红黑树）

下面代码展示multimap可以插入相同键值的元素。

void PrintMultimap(const multimap<string, string>& dict)
{for (auto& e : dict){cout << e.first << ":" << e.second << endl;}cout << endl;
}void test_multimap()
{multimap<string, string> dict = { { "string", "字符串"}, {"interest", "兴趣"}, {"right", "右边"},{"hot", "热的"} };PrintMultimap(dict);dict.insert({ "interest", "利益" });dict.insert({ { "hot", "活跃的" } });PrintMultimap(dict);
}

运行结果如下：