深入解析C++树形关联式容器：map、set及其衍生容器的使用与原理

---

一、引言

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 <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对象包含两个数据成员：first和second，分别对应键和值。pair的模板参数指定了这两个成员的类型，即我们必须提供两个类项名。⚠️两个类型不要求一致！

例如，你可以创建一个pair<string, int>，其中first是一个字符串类型的键，而second是一个整数类型的值。

#include <utility> // for std::pair  
int main() {  std::pair<std::string, int> myPair;  myPair.first = "apple";  myPair.second = 10;  // 也可以使用构造函数初始化  std::pair<std::string, int> 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，它们都具有相同的模板类型 <T1, T2>。这些操作符重载的返回值都是 bool 类型。

• operator==：判断两个 std::pair 对象是否相等。如果它们的第一个元素和第二个元素都相等，则返回 true，否则返回 false。
• operator!=：判断两个 std::pair 对象是否不相等。如果它们的第一个元素或第二个元素有一个不相等，则返回 true，否则返回 false。
• operator<：判断一个 std::pair 对象是否小于另一个 std::pair 对象。首先比较它们的第一个元素，如果第一个元素小于另一个对象的第一个元素，则返回 true；如果第一个元素相等，再比较第二个元素，如果第二个元素也小于另一个对象的第二个元素，则返回 true；否则返回 false。
• operator<=：判断一个 std::pair 对象是否小于或等于另一个 std::pair 对象。如果一个对象小于另一个对象或两个对象相等，则返回 true，否则返回 false。
• operator>：判断一个 std::pair 对象是否大于另一个 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<const key_type,mapped_type>

对于set 类型，key_type 和 value_type 是一样的；set 中保存的值就是关键字。在一个map中，元素是键值对。即，每个元素是一个pair 对象，包含一个关键之都一个关联的值。由于我们不能改变一个元素的关键字，因此这些 pair 的关键字部分是const 的。

只有 map 家族的类型才有 mapped_type。

1. map 的基本操作

map是C++标准库中的一个关联容器，它存储的元素都是键值对，并且根据键的值自动排序。下面我们将详细讨论std::map的基本操作，包括插入与访问元素、查找元素、删除元素以及遍历元素。

template < class Key,                                     // map::key_typeclass T,                                       // map::mapped_typeclass Compare = less<Key>,                     // map::key_compareclass Alloc = allocator<pair<const Key,T> >    // map::allocator_type> class map;

Key：表示 map 中键的类型，即 map::key_type。T：表示 map 中值的类型，即 map::mapped_type。
Compare：用于定义键之间的比较方式，默认是 std::less<Key>，即默认情况下按照键的升序进行排序。可以根据需要传入自定义的比较函数对象。
Alloc：表示分配器类型，用于管理内存分配。默认情况下，使用 allocator<pair<const Key, T>> 作为默认的内存分配器。

• 插入元素

插入元素到std::map中通常使用insert成员函数。你可以通过make_pair函数或者初始化列表来创建键值对，也可以添加一个元素的范围：

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {map<string, int> myMap;// 插入元素myMap.insert(make_pair("apple", 10));myMap.insert({"pear",30});myMap.insert(pair<string, int>("orange",40));myMap.insert(map<string,int>::value_type("cherry",50));   myMap["banana"] = 20; // 使用下标操作符插入// 访问元素cout << "The value of apple is: " << myMap["apple"] << endl;cout << "The value of banana is: " << myMap.at("banana") << endl;return 0;
}

⚠️insert函数可以接收一对迭代器，也可以接收一个初始化列表，这两种行为类似的对应构造函数。对于一个给定的关键字，只有第一个带此关键字的元素才被插入到容器中。

要注意insert函数的返回值（c++98）：

insert返回的值依赖于容器类型和参数：

1. 单个元素插入：
   • 这种形式会尝试将值为 val 的元素插入到容器中。如果插入成功（即容器中原先没有与 val 相等的元素），则返回一个指向新插入元素的迭代器和 true；如果插入失败（容器中已经有一个与 val 相等的元素），则返回一个指向已存在元素的迭代器和 false。
2. 带有提示位置的插入：
   • 这种形式会尝试将值为 val 的元素插入到 position 所指定的位置之前。如果插入成功，则返回指向新插入元素的迭代器；如果插入失败，则返回一个指向已存在元素的迭代器**
3. 范围插入：
   • 这种形式用于一次性插入范围 [first, last) 中的元素。该方法接受两个迭代器参数，分别指向要插入元素范围的起始和结束位置。

• 访问元素

访问元素则可以通过下标操作符[]或者at成员函数，如果键不存在，下标操作符会创建一个新元素，而at则会抛出一个异常。都是通过键找到与键对应的值然后返回其引用：

//map::at
mapped_type& at (const key_type& k);
const mapped_type& at (const key_type& k) const;//operator[]
mapped_type& operator[] (const key_type& k);
//使用 operator[] 函数的调用等效于以下操作：
(*((this->insert(make_pair(k,mapped_type()))).first)).second;

这个操作首先通过 make_pair(k, mapped_type()) 创建一个新的 key-value 对，并将其插入到容器中。然后，insert 方法返回一个指向新插入元素的迭代器，通过解引用 (*...) 操作获取此元素，并使用 .second 获取对应映射值的引用。

因此，对于一个map使用下标操作，其行为与数字和 vector上的下标操作不同。，通过使用 operator[]，可以轻松地访问和更新 map 容器中的元素，如果元素不存在，则可以在访问时插入新元素。

• 查找元素

对于不允许重复关键字的容器，可能使用find还是count 没什么区别。但对于允许重复关键字的容器，count还会做更多的工作。如果元素在容器中，它还会统计有多少个元素有相同的关键字。如果不需要计数，最好使用find。它返回一个迭代器，指向找到的元素，如果未找到元素，则返回end()迭代器。此外，count成员函数可以用来检查键是否存在于map中：

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {map<string, int> myMap;myMap["apple"] = 10;myMap["banana"] = 20;// 查找元素auto it = myMap.find("apple");if (it != myMap.end()) cout << "Found apple with value: " << it->second << endl;else cout << "Apple not found." << endl;// 检查键是否存在if (myMap.count("banana") > 0) cout << "Banana exists in the map." << endl;else cout << "Banana does not exist in the map." << endl;return 0;
}

• 删除元素

与顺序容器一样，我们可以通过传递给erase传入一个常量迭代器，或传入两个常量迭代器，表示一个范围。这两个版本的 erase 与对应的顺序容器的操作非常相似：指定的元素被删除，函数返回 void。关联容器提供一个额外的erase操作，它接受一个key_type 参数。此版本删除所有匹配给定关键字的元素(如果存在的话)，返回实际删除的元素的数量。对于保存不重复关键字的容器，erase的返回值总是0或1。若返回值为0，则表明想要删除的元素并不在容器中。

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {map<std::string, int> myMap;myMap["apple"] = 10;myMap["banana"] = 20;// 删除元素myMap.erase("apple"); // 删除键为"apple"的元素// 使用迭代器删除元素auto it = myMap.find("banana");if (it != myMap.end()) {myMap.erase(it);}return 0;
}

• 遍历元素

遍历std::map中的元素通常使用迭代器。由于map中的元素是排序的，因此遍历将按照键的顺序进行。

示例代码：

#include <iostream>
#include <map>
#include <string>int main() {std::map<std::string, int> myMap;myMap["apple"] = 10;myMap["banana"] = 20;myMap["cherry"] = 30;// 遍历元素for (const auto& kv : myMap) {std::cout << kv.first << ": " << kv.second << std::endl;}return 0;
}

在上面的代码中，我们使用了范围基于的for循环（C++11及以后版本）来遍历map中的每个键值对。kv是一个常量引用，它引用了map中的一个键值对。kv.first是键，kv.second是值。

---

2. set 的基本操作

template < class T,                        // set::key_type/value_typeclass Compare = less<T>,        // set::key_compare/value_compareclass Alloc = allocator<T>      // set::allocator_type> class set;

T：表示 set 中元素的类型，即 set::key_type 和 set::value_type。
Compare：用于定义元素之间的比较方式，默认是 less<T>，即默认情况下按照元素的升序进行排序。可以根据需要传入自定义的比较函数对象。
Alloc：表示分配器类型，用于管理内存分配。默认情况下，使用 allocator<T> 作为默认的内存分配器。

set与map几近相同，不再做赘述。

• 插入元素

与map相同都是使用insert进行插入。

set<int> s;  
s.insert(1);  
s.insert(2);  
s.insert(3);  
// 尝试插入已存在的元素，不会有任何效果  
s.insert(2);  

• 查找元素

与map类似，使用 find 成员函数来查找 set 中的元素。如果元素存在，find 将返回一个指向该元素的迭代器；如果元素不存在，则返回 end() 迭代器。

set<int> s = {1, 2, 3};  
auto it = s.find(2);  
if (it != s.end()) cout << "Element found: " << *it << endl;  
else cout << "Element not found" << endl;  it = s.find(4);  
if (it == s.end())  cout << "Element not found" << endl;  

• 删除元素

与map类似，使用 erase 成员函数来删除 set 中的元素。你可以通过值或迭代器来指定要删除的元素。set可以将序列中重复性的元素去除掉。因为set要保证其有序，因此set中元素不能被直接修改，若要修改可以先删除，在插入。

set<int> s = {1, 2, 3};  
// 通过值删除元素  
s.erase(2);  
// 或者通过迭代器删除元素  
auto it = s.find(3);  
if (it != s.end()) {  s.erase(it);  
} 

• 遍历元素

使用范围基于的 for循环或迭代器来遍历 set 中的元素。

#include <iostream>  
#include <set>  
using namespace std;
int main() {  set<int> s = {1, 2, 3};  //1、for (const auto& elem : s) cout << elem << endl;  //2、for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {  cout << *it << endl;  }  return 0;  
}

map中重载了[]运算符，因为其需要通过key获取value，而set中却没有。map中存储的是键值对，set中只储存了key。因map和set的底层结构都是红黑树，而红黑树是近似的平衡二叉搜索树，故查询时间复杂度为O(log N) 。

---

3.关联式容器的迭代器

当解引用一个关联容器选代器时，我们会得到一个类型为容器的 value_type 的的引用。

对map而言，valve_type 是一个 pair 类型，其 first 成员保存const的关键字，second 成员保存值。此处假设我们有一个名为 words 的 map：

map<string, int> words;		
auto map_it = words.begin();	// *map_it 是 pair<const string , int>对象的引用
cout << map_it->first << " " << map_it->second;
map_it->first = "another"; 		//错误:关键字是const的，不可改变
++map_it->second;				//正确:可以通过迭代器改变值

一个map 的 value_type 是一个 pair，我们可以改变 pair的值，但不能改变关键字成员的值。

虽然 set 类型同时定义了iterator和const_iterator 类型，但两种类型都只允许只读访问 set 中的元素。与不能改变一个 map 元素的关键字一样，一个 set 中的关键字也是const的。可以用一个set迭代器来读取元素的值，但不能修改：

set<int> s = { 0,1,2,3,4,5,6,8,9 };
set<int>::iterator set_it = s.begin();
if (set_it != s.end()) {*set_it = 42;				//错误:set中的关键字是只读的 cout << *set_it << endl;	//正确:可以输出
}

⚠️当我们使用一个迭代器遍历一个 map、multimap、set、multiset时，迭代器按关键字升序遍历元素。

---

四、 multimap 与 multiset 的特性

multimap 和 multiset 是 C++ 标准模板库 (STL) 中的两种容器，它们分别允许存储多个具有相同键的元素和多个重复的元素。这两种容器对于处理某些特定问题非常有用，尤其是当您需要存储多个具有相同键的值或当您想要允许集合中的元素重复时。

1. multimap

   特性：

   • 允许多值特性：与 map 不同，multimap 允许存储多个具有相同键的元素。

   主要操作：

   • 插入多个相同键值的元素：使用 insert 成员函数，可以插入具有相同键的多个元素。
   • 查找与遍历多值元素：可以使用 find 成员函数来查找具有特定键的第一个元素，然后使用迭代器来遍历所有具有该键的元素。

⚠️multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。且multimap中没有重载operator[]操作。

2. multiset

   特性：

   • 允许多重元素：与 set 不同，multiset 允许存储多个相同的元素。

   主要操作：

   • 插入多个相同元素：使用 insert 成员函数，可以插入多个相同的元素。
   • 查找与遍历元素：可以使用 find 成员函数来查找特定元素，然后使用迭代器来遍历所有元素。

🙉 对允许重复关键字的容器，使用 erase删除元素的数量可能大于1。

---

五、关联式容器的使用技巧与注意事项

关联式容器（如 map、set、multimap、multiset 等）在 C++ 标准库中提供了基于键值对存储元素的能力。在使用这些容器时，有一些重要的技巧和注意事项需要了解。

1. 键值类型的选择与设计

• 唯一性：确保键值是唯一的（对于 map 和 set），或者可以接受重复键值（对于 multimap 和 multiset）。
• 可比较性：键值类型必须支持比较操作，通常是通过定义 < 运算符或者提供一个自定义的比较函数。
• 内存和性能：选择占用内存较小且比较操作效率高的类型作为键值类型。
• 稳定性：如果键值类型包含动态分配的内存或资源，需要确保在键值比较和容器操作过程中这些资源的管理是安全的。

2. 自定义比较函数与排序规则

• 自定义比较函数：当标准比较不满足需求时，可以通过提供自定义的比较函数来定义键值对的排序规则。即，使用仿函数。
• 透明性：自定义比较函数应该保持透明性，即对于相等的键值，比较结果应该一致。
• 性能：自定义比较函数的性能会影响容器的插入、查找和删除操作的效率。

3.其他注意事项

• 迭代器失效：在修改关联式容器（如插入或删除元素）时，指向容器中元素的迭代器可能会失效。需要小心处理这种情况，避免使用失效的迭代器。
• 范围查询：关联式容器提供了基于键值的范围查询功能（如 lower_bound() 和 upper_bound()）。合理利用这些功能可以提高查询效率。

关联容器支持通过关键字高效查找和提取元素。对关键字的使用将关联容器和顺序容器区分开来，顺序容器中是通过位置访问元素的。