关联式容器：map和set

引言：

在计算机科学中，我们经常需要处理一系列具有关键字的元素，并希望对这些元素进行高效的查找、插入和删除操作。为了满足这些需求，我们可以使用BSTree来实现。BSTree作为一种基础的数据结构，它不仅能够帮助我们快速地定位元素，还可以方便地进行元素的插入和删除操作。

在此基础上，map和set这两种数据结构在BSTree的基础上进行了封装，提供了更为丰富的功能。

本文将通过三个方面，对map和set进入学习。

1. 关联式容器

2. 键值对

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

一、关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为 序列式容器，因为其底层为 线性序列的数据结构，里面

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

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

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

关联式容器的几个特征

元素根据特定的排序标准（通常是关键字）存储。
元素的位置与它们的关键字有关。
通常通过关键字来访问元素。
支持对关键字的范围查询和快速查找。
访问元素的时间复杂度通常是O(log n)，因为它们通常基于平衡二叉搜索树（如红黑树）实现。
set和map容器保证元素的唯一性。
multiset和multimap允许重复的元素。
不支持随机访问，因为元素是排序的。
支持快速的查找、插入和删除操作，尤其是基于关键字的操作。
自动保持元素的排序状态。
适用于需要根据关键字快速查找元素的情况。
适用于元素唯一性很重要的情况。

二、键值对

简介

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

这里的键值对通常是pair类和make_pair函数实现的。

pair类

pair 是一个模板类，它可以存储两个值，这两个值可以是不同的数据类型。当你需要将两个相关数据作为一个单元来处理时，pair 非常有用。

pair类存在<utility>这个头文件中，utility这个文件名就起名起的得很好，utility的意思是 实用。

确确实实pair是一个使用的类。

构造：

定义：

std::pair<T1, T2> p(value1, value2);

这里 T1 和 T2 是 pair 中两个元素的数据类型， value1 和 value2 是这两个元素的初始值。

示例：

#include <utility> // 引入 pair 的定义std::pair<int, double> p1(1, 2.3);
std::pair<std::string, int> p2("example", 10);

这里的p1和p2就是一个pair对象，是存储了两个值的小单元。可以通过p1.first p1.second这种形式来访问单元内部的成员。

make_pair函数

同样在<utility>中。make_pair 是一个函数模板，它用于从两个值创建一个 pair 对象。这个函数的目的是为了方便，它允许你不必显式指定 pair 的类型，函数会根据提供的参数自动推导出 pair 的类型。

定义：

std::pair<T1, T2> make_pair(T1 x, T2 y);

可以看出这个函数的返回值是一个pair对象。在我们使用的时候，只需要写出make_pair的参数即可，会自动推导出pair对象。这里 T1 和 T2 是从参数 x 和 y 的类型推导出来的。

使用示例：

#include <utility> // 引入 make_pair 的定义std::pair<int, double> p1 = std::make_pair(1, 2.3);
std::pair<std::string, int> p2 = std::make_pair("example", 10);

在返回类型设置为pair类型时，make_pair作返回十分好用！

区别

类型：pair 是一个类模板，用于定义存储两个值的对象；而 make_pair 是一个函数模板，用于创建 pair 对象。
使用方式：当你使用 pair 时，必须指定存储的数据类型；而使用 make_pair 时，数据类型可以从提供的参数中自动推导。
灵活性：make_pair 在某些情况下更灵活，尤其是当你不知道或不想明确指定 pair 的类型时。

怎么使用

当你需要创建一个 pair 对象并且知道类型时，可以直接使用 pair 的构造函数。
当你想让编译器自动推导 pair 的类型，或者代码更简洁时，可以使用 make_pair。

#include <iostream>
#include <utility> // 包含 pair 和 make_pair 的定义int main() {// 使用 pair 的构造函数std::pair<int, double> p1(1, 2.3);// 使用 make_pair 创建 pair 对象std::pair<std::string, int> p2 = std::make_pair("example", 10);// 输出 pair 的值std::cout << "p1: " << p1.first << ", " << p1.second << std::endl;std::cout << "p2: " << p2.first << ", " << p2.second << std::endl;return 0;
}

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

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

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

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

个容器。

set

简介：

在C++的STL（标准模板库）中，set是一种关联容器，它存储了由关键字组成的已排序的集合，并且每个关键字的值都是唯一的。以下是set的一些基本特性和用法简介：

特性

唯一性：在set中，所有的元素都是唯一的，不能有重复的元素。
自动排序：set中的元素总是按照特定的顺序排序，默认是升序排序。这是通过元素的关键字进行比较来完成的，通常使用<运算符。
基于红黑树实现：在大多数实现中，set是基于红黑树来实现的，这意味着操作如插入、删除和查找都具有对数时间复杂度，即O(log n)。
非顺序访问：与vector或deque不同，set不支持快速随机访问，因为它是基于树结构实现的。

常用成员函数

insert(const T& value)：在set中插入一个元素。如果元素已存在，则set保持不变。
erase(const T& value)：从set中删除指定的元素。
find(const T& value)：在set中查找元素，如果找到则返回指向元素的迭代器，否则返回end()。
size()：返回set中元素的数量。
empty()：检查set是否为空。
begin()：返回指向set中第一个元素的迭代器。
end()：返回指向set中最后一个元素之后位置的迭代器。
clear()：删除set中的所有元素。

set是一个非常有用的容器，当需要存储不重复的元素集合，并且经常进行元素的查找和删除操作时，它是一个很好的选择。

关键：

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

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

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

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

排序。

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

子集进行直接迭代。

5. 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中查找某个元素，时间复杂度为：$log_2 n$

7. set中的元素不允许修改(为什么?) --普通迭代器的内部是const迭代器。正确的方法是先删除旧元素，然后插入新元素。

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

set常规接口的使用

#include <set>
void TestSet()
{// 用数组array中的元素构造setint 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;
}

set复杂接口的分析

1.构造函数

2.operation系列

find接口

count接口

由于count返回1 或 0的特性，count也常用来查找某个元素在不在set中。

3.bound系列

lower_bound返回一个小于等于val的迭代器

An iterator to the the first element in the container which is not considered to go before val, or set::end if all elements are considered to go before val.

upper_bound返回一个大于val的迭代器

Return value

An iterator to the the first element in the container which is considered to go after val, or set::end if no elements are considered to go after val.

因此lower_bound, upper_bound可以理解为返回一个左闭右开的区间，

使用：

我们删除时，删除的是左闭右开的区间。因此删除30 40 50 60

equal_range接口

equal_range() 函数在 C++ 中的 std::set 或 std::multiset 容器中返回的是一个左闭右开的区间（返回的是一个pair）。该函数返回一对迭代器，第一个迭代器指向第一个不小于（对于 std::set 和 std::multiset 来说是等于）给定值的元素，第二个迭代器指向第一个大于给定值的元素。

multiset

允许插入相同值的变异的搜索树。插入相同的左边右边都一样。

当我们查找时：

查找相同的元素，返回中序的第一个2

multiset的接口根set也是大差不差

1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。

2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成

的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器

中进行修改(因为元素总是const的)，但可以从容器中插入或删除。

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

进行排序。

4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭

代器遍历时会得到一个有序序列。

5. multiset底层结构为二叉搜索树(红黑树)。

注意：

1. multiset中再底层中存储的是<value, value>的键值对

2. mtltiset的插入接口中只需要插入即可

3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的

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

map

std::map 是 C++ 标准库中的一个关联容器，它存储键值对，其中键是唯一的，而值则可以是重复的。std::map 会根据键的值自动排序，通常使用红黑树实现，这意味着在 std::map 中插入和删除操作通常具有对数时间复杂度（O(log n)）。

以下是 std::map 的一些关键特性：

基本属性

键值对存储：std::map 存储键值对（key-value 对），其中每个键都是唯一的，而值可以是重复的。
排序：std::map 根据键的值自动排序所有元素。
唯一性：不允许重复的键，每个键只能映射到一个值。
关联性：元素是根据键来访问的，而不是它们在容器中的位置。

主要成员函数

构造函数：创建一个空的 std::map 或者从一个已有的范围填充。
insert：插入一个新的键值对到 map 中，如果键已存在，则不会插入。
find：查找具有特定键的元素，如果找到返回一个迭代器，否则返回 end()。
erase：删除由迭代器或键指定的元素。
size：返回 map 中元素的数量。
empty：检查 map 是否为空。
clear：删除 map 中所有的元素。

示例代码

#include <iostream>
#include <map>int main() {std::map<int, std::string> students;// 插入键值对students.insert(std::pair<int, std::string>(1, "Alice"));students.insert(std::make_pair(2, "Bob"));students[3] = "Charlie"; // 使用下标操作符插入// 查找键为 2 的元素auto it = students.find(2);if (it != students.end()) {std::cout << "Student ID: " << it->first << ", Name: " << it->second << std::endl;}// 遍历 mapstd::cout << "All students:" << std::endl;for (const auto& pair : students) {std::cout << "Student ID: " << pair.first << ", Name: " << pair.second << std::endl;}// 删除键为 1 的元素students.erase(1);// 检查 map 是否为空if (students.empty()) {std::cout << "The map is empty." << std::endl;} else {std::cout << "The map is not empty." << std::endl;}return 0;
}

在这个示例中，我们创建了一个 std::map，用于存储学生的 ID 和姓名。我们展示了如何插入元素、查找元素、遍历 map 以及删除元素。由于 std::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的重要接口

1.构造

map提供了三种构造方式：1.空 2.迭代器范围 3.拷贝构造

2.operator[]

问题：当key不在map中时，通过operator获取对应value时会发生什么问题

注意：在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过

key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认

value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常 。

#include <iostream>
#include <map>int main() {std::map<int, std::string> studentGrades;// 插入或修改键值对studentGrades[1] = "A"; // 插入键为 1 的元素，值为 "A"studentGrades[2] = "B"; // 插入键为 2 的元素，值为 "B"studentGrades[1] = "A+"; // 修改键为 1 的元素的值// 使用 operator[] 访问元素std::cout << "Student ID 1 has grade: " << studentGrades[1] << std::endl;// 使用 operator[] 访问不存在的键，这将插入一个新的键值对// 假设 std::string 有一个默认构造函数，它将创建一个空字符串std::cout << "Student ID 3 has grade: " << studentGrades[3] << std::endl;// 打印所有学生的成绩std::cout << "All student grades:" << std::endl;for (const auto& pair : studentGrades) {std::cout << "Student ID: " << pair.first << ", Grade: " << pair.second << std::endl;}return 0;
}

支持迭代器范围for，但是这是个pair对象

map中元素的修改相关的接口

函数声明	功能简介
pair<iterator,bool> insert ( const value_type& x )	在 map 中插入键值对 x ，注意 x 是一个键值对，返回值也是键值对： iterator 代表新插入元素的位置， bool 代表释放插入成功
void erase ( iterator position )	删除 position 位置上的元素
size_type erase ( const key_type& x )	删除键值为 x 的元素
void erase ( iterator first, iterator last )	删除 [first, last) 区间中的元素
void swap ( map<Key,T,Compare,Allocator>& mp )	交换两个 map 中的元素
void clear ( )	将 map 中的元素清空
iterator find ( const key_type& x )	在 map 中插入 key 为 x 的元素，找到返回该元素的位置的迭代器，否则返回 end
const_iterator find ( const key_type& x ) const	在 map 中插入 key 为 x 的元素，找到返回该元素的位置的 const 迭代器，否则返回 cend
size_type count ( const key_type& x ) const	返回 key 为 x 的键值在 map 中的个数，注意 map 中 key 是唯一的，因此该函数的返回值要么为 0 ，要么为 1 ，因此也可以用该函数来检测一个 key 是否在 map 中