【045】C++中map和multimap容器全面解析：深入学习，轻松掌握

这里写目录标题

• 一、介绍
• 二、map和multimap容器的基本概念
• 三、map和multimap容器的基本操作
• • 3.1、常用的接口函数API
  • 3.2、使用示例
  • 3.3、性能分析
• 四、map和multimap容器的高级操作
• 五、代码实践
• 总结

一、介绍

在C++中，map和multimap容器是非常重要的数据结构，它们提供了一种键值对的映射关系，可以高效地组织和访问数据。map容器中的每个元素都包含一个键和一个值，而multimap容器允许键重复。

这两种容器在实际项目中广泛应用，特别适合需要快速查找和插入元素的场景。其底层实现采用了红黑树等高效的数据结构，map和multimap容器在处理大量数据时具有良好的性能表现。它们也提供了丰富的操作方法和函数，可以轻松地对容器中的数据进行插入、删除、查找和遍历操作。

深入理解map和multimap容器的使用方法和性能特点可以设计高效的数据结构和算法，提高程序的性能和可维护性。

二、map和multimap容器的基本概念

map的特性是，所有元素都会根据元素的键值自动排序。map所有的元素都是pair，同时拥有实值和键值，pair的第一元素被视为键值,第二元素被视为实值，map 不允许两个元素有相同的键值。我们可以通过map的迭代器改变map的键值吗?答案是不行，因为 map的键值关系到 map元素的排列规则，任意改变map键值将会严重破坏map数据组织。如果想要修改元素的实值，那么是可以的。

map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。

map容器提供了快速的查找、插入和删除操作，时间复杂度为O(log n)。

multimap与map类似，也是键-值对的容器，不同之处在于它允许重复的键。multimap容器同样是有序的，使用红黑树来组织数据，提供了快速的查找、插入和删除操作，时间复杂度为O(log n)。

map容器：每个元素都是键值-实值成对存储，自动根据键值排序，键值不能重复，不能修改。

multimap和map的操作类似，唯一区别 multimap键值可重复。map和multimap都是以红黑树为底层实现机制。

三、map和multimap容器的基本操作

3.1、常用的接口函数API

（1）构造函数：

// 默认构造
map m;		//默认构造一个空的map，键的类型为Key，值的类型为T。
multimap mm;//默认构造一个空的multimap，键的类型为Key，值的类型为T。

// 带有比较函数参数的构造函数：
map m (const Compare& comp);		//通过指定比较函数comp来构造map。
multimap mm (const Compare& comp);//通过指定比较函数comp来构造multimap。

// 区间构造函数：
map m (InputIterator first, InputIterator last);		//使用迭代器范围[first, last)内的元素来构造map。
multimap mm (InputIterator first, InputIterator last)	//使用迭代器范围[first, last)内的元素来构造multimap。

//拷贝构造函数：
map m (const map& x);				//拷贝构造一个map，其元素和x相同。
multimap mm (const multimap& x);	//拷贝构造一个multimap，其元素和x相同。

//移动构造函数（C++11引入）：
map m (map&& x);			//移动构造一个map，取得x的资源但留下x为空。
multimap mm (multimap&& x);//移动构造一个multimap，取得x的资源但留下x为空。

（2）赋值操作：

// 赋值运算符：
map& operator=(const map& x);			//赋值运算符重载，用x的内容替换当前map的内容。
multimap& operator=(const multimap& x);	//赋值运算符重载，用x的内容替换当前multimap的内容。
// swap函数：
void swap(map& x);		//交换当前map和map x的内容。
void swap(multimap& x);	//交换当前multimap和multimap x的内容。

（3）大小操作：

// size函数：
size_type size() const;	//返回map或multimap中元素的个数。
// empty函数：
bool empty() const;		//如果map或multimap为空，则返回true，否则返回false。

（4）插入数据元素操作：

// insert函数：
pair insert(const value_type& val);			//在map中插入val，返回一个pair，第一个元素是一个迭代器，指向新插入的元素或者已存在的相同键的元素，第二个元素是一个bool值，表示插入是否成功。
iterator insert(iterator position, const value_type& val);	//在position位置插入val，并返回插入元素的迭代器。

// emplace函数：使用传入的参数构造元素并插入map中，返回一个pair，
// 第一个元素是一个迭代器，指向新插入的元素或者已存在的相同键的元素，第二个元素是一个bool值，表示插入是否成功。
template  pair emplace(Args&&... args);

// insert_or_assign函数（C++17及以上版本）：如果k存在，则将其关联的值替换为obj，如果不存在则创建一个新的键值对，并返回一个pair，
// 第一个元素是一个迭代器，指向新插入或修改的元素，第二个元素是一个bool值，表示是插入还是修改操作。
- template  pair insert_or_assign(const key_type& k, M&& obj);

（5）删除操作：

// erase函数：
iterator erase(iterator position);				//删除指向位置position的元素，并返回指向被删元素之后的下一个元素的迭代器。
size_type erase(const key_type& k);				//删除所有键为k的元素，并返回被删除的元素的数量。
iterator erase(iterator first, iterator last);	//删除[first, last)范围内的所有元素，并返回指向被删元素之后的下一个元素的迭代器。

// clear函数：删除map或multimap中的所有元素。
void clear();

（6）查找操作：

// find函数：
iterator find(const key_type& k);				//查找键为k的元素，并返回指向该元素的迭代器，如果未找到则返回指向尾部的迭代器。
const_iterator find(const key_type& k) const;	//在const map或multimap中查找键为k的元素，并返回指向该元素的const迭代器。

// count函数：返回map或multimap中键等于k的元素的个数。
size_type count(const key_type& k) const;

// lower_bound函数：返回一个迭代器，指向第一个不小于k的元素。
iterator lower_bound(const key_type& k);

// upper_bound函数：返回一个迭代器，指向第一个大于k的元素。
iterator upper_bound(const key_type& k);

// equal_range函数：返回一个pair，包含两个迭代器，第一个迭代器指向键值等于k的第一个元素，第二个迭代器指向键值大于k的第一个元素。
pair equal_range(const key_type& k);

（7）访问元素：

• operator[]：通过键访问对应的值。
• at(key)：通过键访问对应的值，如果不存在会抛出out_of_range异常。
• find(key)：查找键为key的元素，返回指向该元素的迭代器。

3.2、使用示例

（1）创建和初始化map和multimap容器：

#include 
#include 

（2）插入和删除元素：

#include 
#include 

（3）查找和访问元素：

#include 
#include 

（4）遍历容器的所有元素：

#include 
#include 

3.3、性能分析

map和multimap都是关联容器，它们都基于红黑树实现。它们之间的主要区别在于：

• map中的每个键都是唯一的，而multimap允许多个具有相同键的元素存在。
• multimap中的元素在树中是按键值排序的，而map中的元素则按照键的比较函数进行排序。

从性能上来说，map通常比multimap具有更好的性能，因为map中的键是唯一的，可以更快地进行查找和访问操作。

如何选择：

• 要保持键的唯一性，应该选择map。
• 要允许多个具有相同键的元素存在，那么就应该选择multimap。

四、map和multimap容器的高级操作

（1）自定义比较函数和排序：在默认情况下，map和multimap容器使用元素的键值进行排序，但是有时候要根据不同的标准进行排序，这就需要自定义比较函数。

自定义比较函数需要满足严格弱顺序（Strict Weak Ordering）的要求：

1. 反对称性：如果 a 不小于 b 且 b 不小于 a，则 a 等于 b。
2. 传递性：如果 a 小于 b 且 b 小于 c，则 a 也小于 c。
3. 可以相等：两个元素可以相等。

示例：

#include 
#include 

（2）处理重复键（multimap）：遍历查找特定键的所有值。

std::multimap myMultimap;
myMultimap.insert({1, "one"});
myMultimap.insert({2, "two"});
myMultimap.insert({1, "first"}); // 在键为1的位置再插入一个值

int keyToFind = 1;
auto range = myMultimap.equal_range(keyToFind);
for (auto it = range.first; it != range.second; ++it) {
    std::cout <first << " : " <second << std::endl;
}

（3）对map和multimap容器中的数据进行排序：

1. 对 map 容器进行元素值排序：可以将 map 中的键值对元素复制到一个 vector 中，然后使用自定义的比较函数对 vector 进行排序：

   std::map myMap = {
       {2, "two"},
       {1, "one"},
       {3, "three"}
   };
   
   std::vector<std::pair> vec(myMap.begin(), myMap.end());
   std::sort(vec.begin(), vec.end(), 
             [](const std::pair& a, const std::pair& b) {
                 return a.second < b.second;
             });
   

2. 对 multimap 容器进行元素值排序：由于 multimap 允许重复的键值，我们可以使用相似的方法将 multimap 中的元素复制到一个 vector 中，并使用自定义的比较函数对 vector 进行排序：

   std::multimap myMultiMap = {
       {2, "two"},
       {1, "one"},
       {3, "three"},
       {2, "second"}
   };
   
   std::vector<std::pair> vec(myMultiMap.begin(), myMultiMap.end());
   std::sort(vec.begin(), vec.end(), 
             [](const std::pair& a, const std::pair& b) {
                 return a.second < b.second;
             });
   

这样就可以使用自定义的比较函数对 map 和 multimap 容器中的元素值进行排序。在需要按照元素值而不是键值进行排序时，这些方法都比较有用。

五、代码实践

（1）map容器的使用。

#include 
#include 

输出：

FLY,100,100.1
Lion3,101,100.1
Lion2,102,100.1
Lion,103,100.1
***********************
,0,0
FLY,100,100.1
Lion3,101,100.1
Lion2,102,100.1
Lion,103,100.1
,0,0

（2）multimap的示例。

#include 
#include 

总结

map和multimap是C++标准库中非常重要且常用的容器类型，它们都是关联式容器（Associative Containers），用于实现键值对映射。

1. map和multimap容器使用红黑树实现，因此能够在O(log n)的时间复杂度内进行查找和检索操作，这使得它们非常适合于需要快速查找特定键值的应用场景。

2. 这两种容器中的元素默认按照键值进行排序，map要求键值唯一，而multimap允许键值重复。这使得它们非常适合于建立有序的键值对映射，使得对数据的处理更加方便。

3. 由于其快速查找和自动排序的特性，map和multimap容器可以应用于各种类型的问题，如数据存储、索引管理、关联规则等。

4. map和multimap容器提供了各种方法来插入、删除和修改元素，同时它们还提供了丰富的迭代器接口和算法，对数据的操作更加灵活和方便。