---

前言

在C++编程的浩瀚宇宙中，标准模板库（STL）犹如一颗璀璨的星辰，为开发者们提供了强大的数据结构和算法支持。而在STL的众多容器中，Map与Set无疑是两颗尤为耀眼的明珠，它们以高效、有序的方式管理着数据，让键值对和集合的处理变得轻松自如。
本文将带你一起深入探索C++ STL中的Map与Set容器，揭开它们高效数据管理的神秘面纱。从基本用法到底层实现原理，再到实际应用中的

---

➰一、关联式容器

在C++的编程世界中，关联式容器是数据结构领域中的瑰宝，它们不仅提供了高效的数据存储和检索功能，还通过键值对的映射机制，极大地丰富了程序设计的灵活性和多样性。本文将深入探讨C++关联式容器的核心特性、工作原理以及创新应用，为您揭开这些强大工具的神秘面纱。

1.1 关联式容器的概述

C++标准库中的关联式容器主要包括std::map、std::set、std::multimap和std::multiset等。它们共同的特点是基于键值对（key-value）或纯键（key-only）进行存储和检索，支持高效的查找、插入和删除操作。

• std::map：基于红黑树实现的有序关联数组，支持高效的键值对查找、插入和删除。
• std::set：基于红黑树实现的有序集合，只存储唯一的键，支持高效的查找、插入和删除。
• std::multimap：与std::map类似，但允许键的重复。
• std::multiset：与std::set类似，但允许键的重复。

1.2 关联式容器的工作原理

关联式容器内部通常使用平衡二叉树（如红黑树）来实现高效的查找、插入和删除操作。这些操作的时间复杂度通常为O(log n)，其中n是容器中元素的数量。平衡二叉树通过自动调整树的结构来保持平衡，从而确保操作的高效性。

1.3 关联式容器的核心特性

1. 有序性：关联式容器中的元素按照键的顺序进行存储，这使得它们非常适合用于需要排序的场景。
2. 唯一性：std::map和std::set中的键是唯一的，这确保了数据的唯一性和一致性。
3. 键值对映射：std::map和std::multimap通过键值对的方式存储数据，这使得它们能够轻松地实现数据的映射和查找。
4. 范围查询：关联式容器支持基于键的范围查询，可以方便地查找某个范围内的所有元素。

➰二、键值对

在C++中，键值对（Key-Value Pair）是一种常见的数据结构，它由一个键（Key）和一个值（Value）组成。这种结构在编程中非常有用，因为它允许你通过键来快速查找、更新或删除与之关联的值。

2.1 键值对的基本概念

• 键（Key）：键是唯一的标识符，用于访问与之关联的值。在C++中，键通常是某种数据类型（如整数、字符串等）的实例。
• 值（Value）：值是存储在键值对中的实际数据。值可以是任何数据类型，包括基本数据类型（如整数、浮点数、字符等）和复杂数据类型（如对象、结构体等）。

2.2 键值对在C++中的实现

在C++中，键值对通常通过以下几种方式实现：

1. std::map 和 std::unordered_map：
   • std::map 是一个关联容器，它存储键值对，并根据键的排序顺序自动排序这些对。默认情况下，std::map 使用 < 运算符来比较键。
   • std::unordered_map 是另一个关联容器，它也存储键值对，但不保证元素的顺序。它使用哈希表来实现快速查找、插入和删除操作。
2. std::pair：
   • std::pair 是一个模板类，它创建了一个包含两个数据成员的对象。这两个数据成员分别被称为 first 和 second，可以分别用作键和值。虽然 std::pair 本身不直接实现键值对的存储和查找功能，但它经常与 std::map、std::unordered_map 或其他容器一起使用来存储键值对。
3. 自定义数据结构：
   • 在某些情况下，你可能需要创建自己的数据结构来存储键值对。这通常涉及到定义一个类，该类包含两个成员变量（一个用于键，一个用于值），以及必要的成员函数来访问和修改这些成员。

➰三、树形结构的关联式容器

3.1 树形结构的特点

这些树形结构的关联式容器具有以下特点：

• 有序性：元素根据键的排序顺序进行存储，因此可以像数组一样进行顺序遍历。
• 平衡性：使用平衡二叉树（如红黑树）来维护元素，从而保证了查找、插入和删除操作的时间复杂度为O(log n)。
• 自动排序：在插入新元素时，容器会自动将其插入到正确的位置，以保持元素的排序顺序。
• 键的唯一性（对于std::map和std::set）：这些容器保证键的唯一性，即不允许插入具有相同键的多个元素（对于std::multimap和std::multiset则允许键的重复）。

3.2 使用场景

树形结构的关联式容器在C++中有广泛的应用场景，包括但不限于：

• 字典和映射：std::map和std::multimap可以用于实现字典和映射，其中键是单词或标识符，值是相应的定义或数据。
• 集合操作：std::set和std::multiset可以用于实现集合操作，如并集、交集和差集等。
• 排序和去重：这些容器可以用于对元素进行排序和去重操作。
• 查找和替换：由于这些容器提供了快速的查找操作，因此它们可以用于实现查找和替换功能。

总之，树形结构的关联式容器是C++标准库中非常强大且灵活的数据结构，它们提供了高效的查找、插入和删除操作，并且保证了元素的排序顺序和键的唯一性（对于std::map和std::set）。

➰四、set的使用与定义

4.1 set的基本特性

• 存储不重复元素：set中的每个元素都是唯一的，不允许有重复值。
• 自动排序：set中的元素会按照一定的顺序排列，可以是自然顺序或者根据自定义的比较函数进行排序。
• 元素不可修改：set中的元素值不能直接被改变，因为元素值就是其键值，关系到set元素的排列规则。
• 高效操作：set支持快速的查找、插入和删除操作，时间复杂度通常为O(log n)，这是由于其底层实现采用红黑树这种平衡二叉搜索树结构。

4.2 set的声明与构造

• 声明：set<typename> name;，其中typename可以是任何基本类型（如int、double、char等），也可以是STL标准容器（如vector、set、queue等）。
• 构造：
  • 默认构造函数：set<typename> name;，创建一个空的set。
  • 拷贝构造函数：set<typename> name(const set<typename>& other);，创建一个新的set，它是现有set的副本。
  • 初始化列表构造：set<typename> name{val1, val2, ...};，使用初始化列表来构造set。
  • 范围构造：set<typename> name(first, last);，使用一个迭代器范围[first, last)来构造set。

4.3 set的成员函数

• 插入元素：
  • insert(const typename& value);：将一个元素插入到set中。如果元素已存在，则插入操作将被忽略。
  • pair<iterator, bool> insert(const typename& value);：返回一个pair，其中iterator指向插入的位置，bool表示插入是否成功。
• 删除元素：
  • erase(iterator pos);：删除迭代器pos指向的元素。
  • erase(const typename& value);：删除值为value的元素。
  • erase(iterator first, iterator last);：删除范围[first, last)内的所有元素。
• 查找元素：
  • find(const typename& value);：查找值为value的元素，返回一个指向该元素的迭代器。如果未找到，则返回end()。
  • count(const typename& value);：返回值为value的元素在set中出现的次数。对于set来说，返回值只能是0或1。
• 其他成员函数：
  • size();：返回set中元素的个数。
  • empty();：判断set是否为空。如果为空，返回true；否则返回false。
  • clear();：清空set中的所有元素。
  • begin();：返回一个指向set中第一个元素的迭代器。
  • end();：返回一个指向set末尾的迭代器（注意，这是一个“尾后迭代器”，不指向任何实际元素）。
  • lower_bound(const typename& value);：返回指向第一个不小于value的元素的迭代器。
  • upper_bound(const typename& value);：返回指向第一个大于value的元素的迭代器。
  • equal_range(const typename& value);：返回一个pair，表示value在set中的范围（即[lower_bound, upper_bound)）。

4.4 set的迭代器

set的迭代器是双向迭代器，支持正向和反向遍历。由于set中的元素是有序的，所以迭代器的遍历顺序也是有序的。此外，set的迭代器是const_iterator，这意味着不能通过迭代器直接修改元素的值。

4.5 set的使用示例

以下是一个简单的使用示例，展示了如何创建set、插入元素、查找元素和遍历元素：

#include <iostream>  
#include <set>  using namespace std;  // set的基本使用
void test_set1() {// 排序+去重set<int> s;s.insert(2);s.insert(4);s.insert(5);s.insert(1);s.insert(7);s.insert(7); // 去重原理：一个值已经有了，我们就不插入auto it = s.begin();while (it != s.end()) {cout << *it << " ";++it;}cout << endl;for (auto e : s) {cout << e << " ";}cout << endl;/*auto pos = s.find(3);if(pos != s.end())s.erase(pos);*/s.erase(1);for (auto e : s) {cout << e << " ";}cout << endl;
}// set迭代器的使用
void test_set2() {set<int> myset;set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90// 删除[30 60]，但是迭代器是左闭右开itlow = myset.lower_bound(30);                // 下限 >=     itup = myset.upper_bound(60);                 // 上限 >// [itlow, itup)cout << *itlow << endl;cout << *itup << endl;myset.erase(itlow, itup);for (auto e : myset) {cout << e << " ";}cout << endl;
}int main(){test_set1();cout << endl << endl;test_set2();return 0;
}

综上所述，C++中的set是一种非常实用的容器，它提供了高效的查找、插入和删除操作，并且保证了元素的唯一性和有序性。

➰五、multiset的定义与使用

在C++中，multiset是一种非常有用的标准模板库（STL）容器，它用于存储一组按照特定顺序排列的元素，并且允许元素重复。以下是对multiset的详细介绍：

5.1 multiset基本特性

1. 存储重复元素：与set容器不同，multiset允许存储重复的元素。
2. 自动排序：multiset中的元素会根据一定的顺序（默认是升序）自动进行排序。
3. 元素不可直接修改：multiset中的元素值在插入后不能直接被修改，因为元素值就是其键值，直接修改会破坏容器的有序性。不过，可以通过删除旧元素并插入新元素的方式来间接修改。
4. 底层实现：multiset的底层通常使用红黑树这种平衡二叉搜索树结构来实现，以确保高效的查找、插入和删除操作。

5.2 multiset的声明与构造

1. 声明：multiset<typename> name;，其中typename表示要存储的元素类型。
2. 构造：
   • 默认构造函数：multiset<typename> name;，创建一个空的multiset。
   • 拷贝构造函数：multiset<typename> name(const multiset<typename>& other);，创建一个新的multiset，它是现有multiset的副本。
   • 初始化列表构造：multiset<typename> name{val1, val2, ...};，使用初始化列表来构造multiset。
   • 范围构造：multiset<typename> name(first, last);，使用一个迭代器范围[first, last)来构造multiset。

5.3 multiset的成员函数

multiset提供了丰富的成员函数来操作容器中的元素，包括但不限于：

1. 插入元素：
   • insert(const typename& value);：将一个元素插入到multiset中。如果元素已存在，则会在保持有序性的前提下，将新元素插入到已有元素的后面（因为允许重复）。
   • iterator insert(const_iterator position, const typename& value);：在指定位置position前插入一个元素，并返回指向新插入元素的迭代器。如果position是end()迭代器，则元素会被添加到容器的末尾。
   • 还有其他形式的insert函数，如使用范围插入、使用初始化列表插入等。
2. 删除元素：
   • erase(iterator pos);：删除迭代器pos指向的元素。
   • erase(const typename& value);：删除值为value的所有元素。
   • erase(iterator first, iterator last);：删除范围[first, last)内的所有元素。
3. 查找元素：
   • find(const typename& value);：查找值为value的元素，返回一个指向该元素的迭代器。如果未找到，则返回end()迭代器。
   • count(const typename& value);：返回值为value的元素在multiset中出现的次数。
4. 其他成员函数：
   • size();：返回multiset中元素的个数。
   • empty();：判断multiset是否为空。如果为空，返回true；否则返回false。
   • clear();：清空multiset中的所有元素。
   • begin();和end();：分别返回一个指向multiset中第一个元素和末尾元素的迭代器（尾后迭代器）。
   • rbegin();和rend();：分别返回一个指向multiset中最后一个元素和第一个元素前面的位置的逆向迭代器。
   • lower_bound(const typename& value);：返回指向第一个不小于value的元素的迭代器。
   • upper_bound(const typename& value);：返回指向第一个大于value的元素的迭代器。
   • equal_range(const typename& value);：返回一个pair，表示value在multiset中的范围（即[lower_bound, upper_bound)）。

5.4 multiset的自定义排序

默认情况下，multiset中的元素会按照其类型的默认比较函数（通常是<运算符）进行排序。如果需要自定义排序规则，可以在声明multiset时提供一个自定义的比较函数或比较类。例如：

struct Compare {  bool operator()(const int& a, const int& b) const {  return a > b; // 降序排序  }  
};  multiset<int, Compare> myMultiset;

在这个例子中，我们定义了一个比较类Compare，它重载了operator()来指定降序排序规则。然后，我们使用这个比较类来创建一个multiset对象myMultiset，它将按照降序对元素进行排序。

5.5 multiset的使用示例

以下是一个简单的使用示例，展示了如何创建multiset、插入元素、查找元素和遍历元素：

#include <iostream>  
#include <set>  using namespace std;  int main() {  multiset<int> myset;multiset<int>::iterator itlow, itup;// 插入元素，允许重复myset.insert(1);myset.insert(3);myset.insert(1);myset.insert(4);myset.insert(1);myset.insert(1);for (auto e : myset) {cout << e << " ";}cout << endl;// count返回1的个数cout << myset.count(1) << endl;// 返回一个pair，表示value在multiset中的范围（即[lower_bound, upper_bound)）。auto ret = myset.equal_range(1);itlow = ret.first;itup = ret.second;// 删除区间内的所有1myset.erase(itlow, itup);for (auto e : myset) {cout << e << " ";}cout << endl;return 0;  
}

➰六、map的定义与使用

在C++中，map是一种非常有用的标准模板库（STL）容器，它用于存储键值对（key-value pairs），其中每个键都是唯一的，并且与一个特定的值相关联。以下是map的使用与定义的详细介绍：

6.1 map的定义

map的定义通常使用以下语法：

map<KeyType, ValueType> mapName;

其中，KeyType表示键的类型，ValueType表示值的类型，mapName是map对象的名称。

例如，定义一个存储字符串到整数的映射的map：

map<string, int> myMap;

6.2 map的插入元素

向map中插入元素有多种方法：

1. 使用insert成员函数：

myMap.insert(pair<string, int>("key1", 100));

或者：

myMap.insert(make_pair("key2", 200));

1. 使用下标运算符[]直接赋值（如果键不存在，则插入新键值对；如果键已存在，则更新对应的值）：

myMap["key3"] = 300;

举例：

void test_map1() {map<string, string> dict;// 1.有名对象pair<string, string> kv1("insert", "插入");dict.insert(kv1);// 2.匿名对象dict.insert(pair<string, string>("sort", "排序"));// 3.make_pairdict.insert(make_pair("string", "字符串"));// 4.C++11 多参数的构造函数的隐式类型转换：构造+拷贝构造优化成一步dict.insert({ "list", "双向链表" });auto it = dict.begin();while (it != dict.end()) {cout << it->first << ":" << it->second << " ";++it;}cout << endl;
}

6.3 map的查找元素

可以使用find成员函数来查找元素：

auto it = myMap.find("key1");  
if (it != myMap.end()) {  cout << "Found: " << it->first << " => " << it->second << endl;  
} else {  cout << "Key not found." << endl;  
}

find函数返回一个迭代器，如果找到了指定的键，则迭代器指向该元素；否则，迭代器等于end()。

6.4 map的遍历元素

可以使用迭代器来遍历map中的所有元素：

for (auto it = myMap.begin(); it != myMap.end(); ++it) {  cout << it->first << " => " << it->second << endl;  
}

或者使用范围for循环（C++11及以上）：

for (const auto& pair : myMap) {  cout << pair.first << " => " << pair.second << endl;  
}

6.5 map的删除元素

可以使用erase成员函数来删除元素：

1. 通过键删除：

myMap.erase("key1");

1. 通过迭代器删除：

auto it = myMap.find("key2");  
if (it != myMap.end()) {  myMap.erase(it);  
}

1. 删除一个范围内的元素（通过两个迭代器）：

auto it_begin = myMap.find("key_start");  
auto it_end = myMap.find("key_end");  
if (it_begin != myMap.end() && ++(it_end.first) != myMap.end()) {  myMap.erase(it_begin, it_end);  
}

注意：在删除范围内的元素时，需要确保迭代器是有效的，并且it_end应该指向要删除范围之外的第一个元素的位置（因此需要对it_end的迭代器进行自增操作，但这里需要注意it_end可能是end()迭代器，此时不能自增）。然而，上面的代码示例在逻辑上是有问题的，因为find返回的是单个元素的迭代器，而不是一个可以表示范围的迭代器对。正确的做法应该是使用其他方式来确定要删除的范围，比如使用lower_bound和upper_bound函数。

6.6 map的其他成员函数

map还提供了其他有用的成员函数，如：

• size()：返回map中元素的个数。
• empty()：判断map是否为空。
• clear()：清空map中的所有元素。
• count(const Key& key)：返回键为key的元素个数（对于map来说，返回值只能是0或1，因为键是唯一的）。
• lower_bound(const Key& key)和upper_bound(const Key& key)：分别返回指向第一个不小于（大于）key的元素的迭代器。
• equal_range(const Key& key)：返回一个pair，表示key在map中的范围（即[lower_bound, upper_bound)）。

6.7 map的自定义排序

默认情况下，map中的元素会按照键的升序进行排序。如果需要自定义排序规则，可以在声明map时提供一个自定义的比较函数或比较类。例如：

struct Compare {  bool operator()(const int& a, const int& b) const {  return a > b; // 降序排序  }  
};  map<int, string, Compare> myMap;

在这个例子中，我们定义了一个比较类Compare，它重载了operator()来指定降序排序规则。然后，我们使用这个比较类来创建一个map对象myMap，它将按照降序对键进行排序。

6.8 map的的使用样例

#include <iostream>
using namespace std;void test_map2() {map<string, string> dict;dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("insert", "插入"));// 不插入，不覆盖，只看key，右值value不相同无所谓dict.insert(make_pair("insert", "xxxxx"));auto it = dict.begin();while (it != dict.end()) {// cout << (*it).first << ":" << (*it).second;cout << it->first << ":" << it->second << " ";++it;}cout << endl;for (const auto& kv : dict) {cout << kv.first << ":" << kv.second << " ";}
}// map.operator[]，通过key，返回value
void test_map3() {// 统计次数string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countmap;for (auto e : arr) {/*auto it = countmap.find(e);if (it == countmap.end()) {countmap.insert(make_pair(e, 1));}else {it->second++;}*/// value_type& operator[](const key_type k)countmap[e]++;}for (const auto& kv : countmap){cout << kv.first << ":" << kv.second << endl;}
}void test_map4()
{map<string, string> dict;dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("insert", "插入"));cout << dict["sort"] << endl; // 查找和读dict["map"];                  // 插入dict["map"] = "映射,地图";     // 修改dict["insert"] = "xxx";       // 修改dict["set"] = "集合";         // 插入+修改for (const auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}
}int main() {test_map2();cout << endl << endl;cout << endl << endl;test_map3();cout << endl << endl;cout << endl << endl;test_map4();cout << endl << endl;cout << endl << endl;return 0;
}

综上所述，map在C++中是一个功能强大的容器，它提供了方便的键值对存储和查找功能，并且支持自定义排序规则。

➰七、multimap的定义与使用

在C++中，multimap是一个关联容器，它与map相似，但允许键值对中的键可以重复。以下是对multimap的定义与使用的详细介绍：

7.1 multimap的定义

multimap的定义通常使用以下语法：

multimap<KeyType, ValueType> multimapName;

其中，KeyType表示键的类型，ValueType表示值的类型，multimapName是multimap对象的名称。

例如，定义一个存储字符串到整数的映射的multimap：

multimap<string, int> myMultimap;

7.2 multimap插入元素

向multimap中插入元素有多种方法，通常使用insert成员函数：

myMultimap.insert(pair<string, int>("key1", 100));

或者：

myMultimap.insert(make_pair("key2", 200));

由于multimap允许键重复，因此可以插入多个具有相同键的元素。

7.3 multimap查找元素

查找元素时，可以使用find成员函数，但需要注意的是，find函数只返回第一个找到的具有指定键的元素。如果需要查找所有具有相同键的元素，可以使用equal_range、lower_bound和upper_bound成员函数。

• find成员函数：

auto it = myMultimap.find("key1");  
if (it != myMultimap.end()) {  cout << "Found: " << it->first << " => " << it->second << endl;  
} else {  cout << "Key not found." << endl;  
}

• equal_range成员函数：返回一个pair，其中first成员是指向第一个不小于给定键的元素的迭代器，second成员是指向第一个大于给定键的元素的迭代器。这可以用于查找所有具有相同键的元素。

auto range = myMultimap.equal_range("key1");  
for (auto it = range.first; it != range.second; ++it) {  cout << it->first << " => " << it->second << endl;  
}

• lower_bound和upper_bound成员函数：分别返回指向第一个不小于（大于）给定键的元素的迭代器。

auto lb = myMultimap.lower_bound("key1");  
auto ub = myMultimap.upper_bound("key1");  
for (auto it = lb; it != ub; ++it) {  cout << it->first << " => " << it->second << endl;  
}

7.4 multimap遍历元素

可以使用迭代器来遍历multimap中的所有元素：

for (auto it = myMultimap.begin(); it != myMultimap.end(); ++it) {  cout << it->first << " => " << it->second << endl;  
}

或者使用范围for循环（C++11及以上）：

for (const auto& pair : myMultimap) {  cout << pair.first << " => " << pair.second << endl;  
}

7.5 multimap删除元素

可以使用erase成员函数来删除元素：

1. 通过键删除（删除所有具有指定键的元素）：

myMultimap.erase("key1");

1. 通过迭代器删除：

auto it = myMultimap.find("key2");  
if (it != myMultimap.end()) {  myMultimap.erase(it); // 注意：这将只删除找到的第一个元素，如果有多个相同键的元素，需要额外处理  
}

注意：上面的代码只会删除找到的第一个具有指定键的元素。如果需要删除所有具有相同键的元素，应该使用equal_range或lower_bound和upper_bound来找到所有相关元素，并逐个删除。

1. 删除一个范围内的元素（通过两个迭代器）：

auto it_begin = myMultimap.lower_bound("key_start");  
auto it_end = myMultimap.upper_bound("key_end");  
myMultimap.erase(it_begin, it_end);

7.6 multimap的其他成员函数

multimap还提供了其他有用的成员函数，如：

• size()：返回multimap中元素的个数。
• empty()：判断multimap是否为空。
• clear()：清空multimap中的所有元素。
• count(const Key& key)：返回键为key的元素个数（对于multimap来说，这个值可能大于1）。

7.7 注意事项

• multimap中的元素是按照键的顺序存储的，默认情况下是按照键的升序进行排序。如果需要自定义排序规则，可以在声明multimap时提供一个自定义的比较函数或比较类。
• 由于multimap允许键重复，因此在插入、查找和删除元素时需要特别注意处理多个相同键的情况。

综上所述，multimap在C++中是一个功能强大的容器，它提供了方便的键值对存储和查找功能，并且支持自定义排序规则和处理多个相同键的情况。

---

结语

最后，需要强调的是，虽然Map与Set提供了高效的数据管理方式，但在使用时仍需注意其性能特点和适用场景。只有深入了解并合理利用这些容器的特性，我们才能在程序中充分发挥它们的作用，实现更加高效、稳定的数据管理。希望本文能够为你提供有益的参考和帮助，让你在C++编程的道路上更加游刃有余。

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！