关联式容器：map和set

引言：

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

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

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

一、关联式容器

关联式容器的几个特征

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

二、 键值对

简介

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)
{}
};

std::pair<T1, T2> p(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. 树形结构的关联式容器

set

简介：

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

特性

1. 唯一性：在set中，所有的元素都是唯一的，不能有重复的元素。
2. 自动排序：set中的元素总是按照特定的顺序排序，默认是升序排序。这是通过元素的关键字进行比较来完成的，通常使用<运算符。
3. 基于红黑树实现：在大多数实现中，set是基于红黑树来实现的，这意味着操作如插入、删除和查找都具有对数时间复杂度，即O(log n)。
4. 非顺序访问：与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中的所有元素。

关键：

注意：

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中的元素构造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;
}

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;
    }

    // 遍历 map
    std::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 中

这里的value_type（一个K/V对）等介绍

当然也可以make_pair("sort", "排序“)

map的key不希望被修改，但是value可以

数据的遍历

需要注意的是，由于 operator[] 在键不存在时会插入一个新的元素，因此如果键的类型没有默认构造函数，或者默认构造的值不是期望的，那么直接使用 operator[] 可能会导致意外的行为。在这种情况下，应该使用 find 或 insert 方法来更安全地处理元素。

multimap

multimap不支持[]，他不知道返回哪一个键值的val的引用

std::multimap 是 C++ 标准库中的一个关联容器，它存储键值对，其中每个键可以与多个值相关联。与 std::map 不同，std::map 中每个键只能有一个对应的值，而 std::multimap 允许键有多个副本，每个副本都与不同的值相关联。

以下是 std::multimap 的一些详细信息：

特点

• std::multimap 中的元素总是按键的升序排列。
• 它使用红黑树实现，确保了元素的有序性。
• 每个键可以出现多次，每个键关联的值可以不同。
• 不支持通过键直接访问单个元素，因为可能有多个元素具有相同的键。
• 查找、插入和删除操作的时间复杂度为 O(log n)，其中 n 是容器中元素的数量。

成员函数

• insert：插入一个或多个元素。
• erase：删除一个或多个元素。
• find：查找具有特定键的元素。
• count：返回具有特定键的元素的数量。
• lower_bound 和 upper_bound：返回一个迭代器，分别指向第一个不小于（或等于）给定键的元素和第一个大于给定键的元素。
• equal_range：返回一个迭代器对，表示具有特定键的所有元素的范围。

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在底层用二叉搜索树(红黑树)来实现。

注意：

1. multimap中的key是可以重复的。

2. multimap中的元素默认将key按照小于来比较

3. multimap中没有重载operator[]操作。

4. 使用时与map包含的头文件相同：