我们这章所学的map / set 系列和后续会讲解的 unordered_map / unordered 系列都属于是关联式容器。

那么什么是关联式容器？ 关联式容器用于存储 键值对 (<key, value>)，与序列式容器不同，关联式容器的元素通过 键 来查找、插入和删除。它们通常采用 平衡二叉搜索树（如 map、set 的红黑树实现）或 哈希表（如 unordered_map、unordered_set）来实现，因此在 查找、插入和删除 等操作时，比序列式容器更高效，时间复杂度通常为对数级别（O(log n) 或 O(1)）。常见的关联式容器包括 map、set、multimap、multiset 以及使用哈希表实现的 unordered_map 和 unordered_set。 它的底层逻辑结构是非线性的，两个位置的储存值之间是紧密关联的，如果交换他们的值就会破坏其储存结构。

二、键值对（pair）

1.认识

键值对（Key-Value Pair）是指由 键（Key）和 值（Value）组成的元素结构。键是唯一标识元素的标志，而值则是与该键相关联的数据。常见的关联式容器（如 map、unordered_map）存储的就是这种键值对结构。

• 键（Key）：用于唯一标识元素。每个键在容器中是唯一的，不会重复。
• 值（Value）：与键相关联的数据，键对应的值可以是任何数据类型。
• 例如，map<int, string> 存储的键值对可能是 {1, "apple"}，其中 1 是键，"apple" 是与该键相关的值。通过键，我们可以快速查找到对应的值。
• 简而言之，键值对 是容器中元素的基本组成单元，键用来查找和访问数据，值存储实际的数据内容。

 

pair的基本结构

代码语言：javascript

AI代码解释

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;  // 定义第一个类型的别名
    typedef T2 second_type; // 定义第二个类型的别名

    T1 first;   // 第一个元素
    T2 second;  // 第二个元素

    // 默认构造函数，使用默认构造函数初始化 first 和 second
    pair() : first(T1()), second(T2()) {}

    // 带参数的构造函数，用给定的值初始化 first 和 second
    pair(const T1& a, const T2& b) : first(a), second(b) {}
};

---

2.构造函数

 

在这里插入图片描述

默认构造

代码语言：javascript

AI代码解释

// 默认构造函数：初始化 `first` 和 `second` 成员为各自类型的默认值
pair();

// 实现：通过默认构造函数初始化 `first` 和 `second` 成员
pair() : first(T1()), second(T2()) {}
// `T1()` 和 `T2()` 是类型 T1 和 T2 的默认构造函数，
// 它们会被调用来初始化 `first` 和 `second`。
// 如果 `T1` 或 `T2` 是类类型，默认构造函数会被调用。
// 如果是基本类型（如 `int`），则 `first` 和 `second` 会被初始化为 0。

拷贝构造

代码语言：javascript

AI代码解释

// 拷贝构造函数：通过拷贝另一个 `pair` 对象来初始化当前对象
template<class U, class V> 
pair(const pair<U, V>& pr);

// 实现：用另一个 `pair<U, V>` 对象的 `first` 和 `second` 成员来初始化当前 `pair` 对象
pair(const pair<U, V>& pr) : first(pr.first), second(pr.second) {}
// `pr.first` 和 `pr.second` 分别是传入的 `pair` 对象的 `first` 和 `second` 成员。
// 当前对象的 `first` 和 `second` 会被初始化为这些值。
// 注意：`U` 和 `V` 是临时 `pair` 对象的类型，可以不同于当前 `pair` 的类型，但必须能够赋值。

带参数构造

代码语言：javascript

AI代码解释

// 带参数构造函数：用指定的值初始化 `first` 和 `second` 成员
pair(const first_type& a, const second_type& b);
// `first_type` 和 `second_type` 是 `pair` 中 `first` 和 `second` 成员的类型。
// `a` 和 `b` 分别是初始化这两个成员的值。

---

3.make_pair

 

1. pair是一个模板类，需要我们显示的传入两个类型（T1 和 T2）来实例化 pair<T1 , T2>对象。而使用map或者其他的关联式容器的时候，我们需要为每个元素都传入一个键值对。每次插入到map中，显示构造pair的对象的时候就会显的很繁琐。

代码语言：javascript

AI代码解释

//手动构造
std::map<int, std::string> m;
m.insert(std::pair<int, std::string>(1, "apple"));

 

1. 为了简化这种操作，C++标准库提供了一个非常方便的工具——std::make_pair 函数模板。使用时，我们不需要显示指定 pair 的类型，它会自动推导类型，减少显示传递类型的繁琐性。

代码语言：javascript

AI代码解释

std::map<int, std::string> m;
m.insert(std::make_pair(1, "apple"));

---

总结

1. 容器分类

• 序列式容器：线性序列结构，存储元素本身，元素位置独立
• 关联式容器：非线性结构，存储键值对，元素通过键访问，操作效率更高

1. 键值对(pair)特性

• 组成：键(key) + 值(value)，键用于唯一标识，值存储实际数据
• 优势：提供快速查找、插入和删除操作
• 时间复杂度：通常为O(log n)或O(1)

1. pair的实用工具

make_pair函数：自动推导类型，简化pair对象的创建

使用对比：

代码语言：javascript

AI代码解释

// 繁琐的手动构造
m.insert(std::pair<int, std::string>(1, "apple"));

// 简化的自动推导
m.insert(std::make_pair(1, "apple"));

关联式容器及其键值对机制是C++中实现高效数据检索的重要工具，特别适用于需要快速查找的场景。