文章目录
- 一、引言
- 二、关联式容器的中的 pair
- a.pair 的创建及使用
- b.pair 间的比较
- 三、 map 与 set 详解
- 1. map 的基本操作
- 2. set 的基本操作
- 3.关联式容器的迭代器
- 四、 multimap 与 multiset 的特性
- 五、关联式容器的使用技巧与注意事项
- 1. 键值类型的选择与设计
- 2. 自定义比较函数与排序规则
- 3.其他注意事项
一、引言
1. 关联式容器的概念与重要性
关联式容器是C++标准库中的一种重要数据结构，它允许我们存储键值对（key-value pair）或单独的元素，并基于键（key）来快速访问或检索对应的值（value）或元素。关联式容器在多种场景下发挥着至关重要的作用，特别是在需要高效查找、插入和删除元素时。它们为程序员提供了便捷的工具，可以简化复杂的操作，并优化程序性能。
关联式容器通过内部的数据结构（如红黑树）来维护元素的顺序，这使得它们能够在常数时间内完成元素的查找、插入和删除操作。与顺序容器（如vector、list）相比，关联式容器在处理大量数据时具有更高的效率。
2. 关联式容器与序列式容器的区别
关联式容器与序列式容器的主要区别在于它们对元素的存储和访问方式的不同。序列式容器按照元素在容器中的位置来存储和访问元素，而关联式容器则是根据元素的键来存储和访问元素。
序列式容器（如vector、list、deque等）其底层为线性序列的数据结构，通过索引或迭代器来访问元素，里面存储的是元素本身。它们提供了对元素的顺序访问。
关联式容器则通过使用平衡搜索树（即红黑树）作为其底层结果，容器中的元素是一个有序的序列。因此，使得元素的存储和访问更加灵活和高效。它们允许我们根据键来快速查找、插入和删除元素。
⚠️关联容器不支持顺序容器的位置相关操作，例如 push_back或 push_front。原因是关联容器中元素是根据关键字存储的，这些操作对其没有意义。而且，关联式容器也不支持构造函数或插入操作这些接收一个元素在和一个数量值的操作。
3. 常见的关联式容器概览
C++标准库提供了多种关联式容器，每种容器都有其特定的用途和特性。以下是一些常见的关联式容器及其简要描述：
- std::map：存储键值对的关联容器，键是唯一的，元素按照键的值进行排序。
- std::set：只存储键的关联容器，键是唯一的，元素按照键的值进行排序。
- std::multimap：存储键值对的关联容器，允许有多个具有相同键的元素。
- std::multiset：只存储键的关联容器，允许有多个相同的元素。
这些关联式容器提供了丰富的操作函数，如插入、查找、删除和遍历等，使得我们可以方便地使用它们来管理数据。通过选择适合的关联式容器，我们可以优化程序的性能并简化代码的实现。
后续C++11又提供了哈希结构的关联式容器，我们将在之后的文章做讲解。
二、关联式容器的中的 pair
在介绍关联容器之前，我们需要了解名为 pair的标准库类型，它定义在头文件 utility 中。
a.pair 的创建及使用
一个pair保存两个数据成员。类似容器，pair是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。下面我们来看SGI-STL中关于键值对的定义：
template 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对象包含两个数据成员：first和second，分别对应键和值。pair的模板参数指定了这两个成员的类型，即我们必须提供两个类项名。⚠️两个类型不要求一致！
例如，你可以创建一个pair，其中first是一个字符串类型的键，而second是一个整数类型的值。
#include // for std::pair int main() { std::pair myPair; myPair.first = "apple"; myPair.second = 10; // 也可以使用构造函数初始化 std::pair anotherPair("banana", 20); return 0; }在关联容器中，pair扮演着非常重要的角色。关联容器（如smap、set、multimap和multiset）的元素类型实际上就是pair。对于map和multimap，每个元素都是一个pair，其中first成员是键，second成员是与该键关联的值。
初始化一个 pair 可以使用构造函数，也可以使用 make_pair：
构造一个 pair 对象，其中第一个元素设置为 x，第二个元素设置为 y。通过传递参数给 make_pair，可以隐式推断模板类型，无需显式指定。
当我们向map或multimap插入元素时，我们实际上是在插入一个pair对象。同样地，当我们从map或multimap中检索元素时，我们得到的是一个指向pair的迭代器。
b.pair 间的比较
其中，、= 四个运算符会先比较两个 pair 中的第一个变量，在第一个变量相等的情况下再比较第二个变量。
每个操作符重载，都需要传入两个 std::pair 对象 lhs 和 rhs，它们都具有相同的模板类型 。这些操作符重载的返回值都是 bool 类型。它们的定义如下：
- operator==：判断两个 std::pair 对象是否相等。如果它们的第一个元素和第二个元素都相等，则返回 true，否则返回 false。
- operator!=：判断两个 std::pair 对象是否不相等。如果它们的第一个元素或第二个元素有一个不相等，则返回 true，否则返回 false。
- operator=：判断一个 std::pair 对象是否大于或等于另一个 std::pair 对象。如果一个对象大于另一个对象或两个对象相等，则返回 true，否则返回 false。
这些操作符的重载使得可以方便地比较 std::pair 对象的成员，例如在使用容器时进行查找、排序等操作。
三、 map 与 set 详解
关联式容器定义类如下表示容器关键字和值的类型：
类型别名 解释 key_type 此容器类型的关键字类型 mapped_type 每个关键字关联的类型 ； 仅适用于map value_type 对于set，与key_type 相同；
对于map ，为 pair对于set 类型，key_type 和 value_type 是一样的；set 中保存的值就是关键字。在一个map中，元素是键值对。即，每个元素是一个pair 对象，包含一个关键之都一个关联的值。由于我们不能改变一个元素的关键字，因此这些 pair 的关键字部分是const 的。
只有 map 家族的类型才有 mapped_type。
1. map 的基本操作
map是C++标准库中的一个关联容器，它存储的元素都是键值对，并且根据键的值自动排序。下面我们将详细讨论std::map的基本操作，包括插入与访问元素、查找元素、删除元素以及遍历元素。
template class map;
Key：表示 map 中键的类型，即 map::key_type。T：表示 map 中值的类型，即 map::mapped_type。
Compare：用于定义键之间的比较方式，默认是 std::less，即默认情况下按照键的升序进行排序。可以根据需要传入自定义的比较函数对象。
Alloc：表示分配器类型，用于管理内存分配。默认情况下，使用 allocator 作为默认的内存分配器。
- 插入元素
插入元素到std::map中通常使用insert成员函数。你可以通过make_pair函数或者初始化列表来创建键值对，也可以添加一个元素的范围：
#include #include #include using namespace std; int main() { map myMap; // 插入元素 myMap.insert(make_pair("apple", 10)); myMap.insert({"pear",30}); myMap.insert(pair("orange",40)); myMap.insert(map::value_type("cherry",50)); myMap["banana"] = 20; // 使用下标操作符插入 // 访问元素 cout map myMap.erase(it); } return 0; } std::map std::cout
- 插入元素
