【C++】—— map 与 multimap

【C++】—— map 与 multimap

1 map1.1 map 和 multimap 参考文档1.2 map 类的介绍1.3 pair 类型介绍1.4 map的构造1.5 map的插入1.5.1 map 的插入方法1.5.2 验证1.5.3 再探pair1.5.4 make_pair 1.6 operator[]1.6.1 样例1.6.2 认识operator[]1.6.3 operator[] 的功能 1.7 map 的其余接口1.8 multimap 与 map 的差异

1 map

1.1 map 和 multimap 参考文档

 https://legacy.cplusplus.com/reference/map/

  

1.2 map 类的介绍

   m a p map map 的声明如下：
  Key 就是 m a p map map 底层 关键字 的类型，T 是 m a p map map 底层 value 的类型， m a p map map 默认要求 Key 支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第⼆个模版参数， m a p map map 底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。 m a p map map 底层是用红黑树实现，增删查改效率是 O(logN) ，迭代器遍历是走的中序，所以是按 Key 有序顺序遍历的。

template < class Key,                                     // map::key_type       class T,                                          // map::mapped_type       class Compare = less<Key>,                        // map::key_compare       class Alloc = allocator<pair<const Key, T> >      // map::allocator_type   > class map;

  

1.3 pair 类型介绍

  在讲解 m a p map map 的使用前，我们先来认识一下 p a i r pair pair 类型，因为 m a p map map 就是用 p a i r pair pair 来存储 k e y key key 和 v a l u e value value

   p a i r pair pair 是一个类模板，它将一对键值对耦合在一起，它有两个模板参数

template <class T1, class T2> struct pair;

  它里面有两个成员： f i r s t first first 和 s e c o n d second second； f i r s t first first 是 T 1 T1 T1 类型， s e c o n d second second 是 T 2 T2 T2 类型

  
   p a i r pair pair 的底层大致如下：

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){}template<class U, class V>pair(const pair<U, V>& pr) : first(pr.first), second(pr.second){}};

  在 m a p map map 中，我们插入数据都是插入 p a i r pair pair， T 1 T1 T1 是 c o n s t const const K e y Key Key， T 2 T2 T2 是 T T T（ v a l u e value value）

pair<const Key, T>

  也即 K e y Key Key 为 f i r s t first first， v a l u e value value 为 s e c o n d second second。
  

1.4 map的构造

   m a p map map 的构造我们关注以下几个接口即可。
   m a p map map 支持正向和反向迭代遍历，遍历默认按 k e y key key 的升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；⽀持迭代器就意味着支持范围 f o r for for，map 支持修改 value 数据，不支持修改 key 数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1) ⽆参默认构造explicit map(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器区间构造template <class InputIterator>map(InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type & = allocator_type());// copy (3) 拷⻉构造map(const map& x);// initializer list (5) initializer 列表构造map(initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// 迭代器是⼀个双向迭代器iterator->a bidirectional iterator to const value_type// 正向迭代器iterator begin();iterator end();// 反向迭代器reverse_iterator rbegin();reverse_iterator rend();

  

1.5 map的插入

1.5.1 map 的插入方法

   m a p map map 的插入方式有多种

例如： 我们创建一个字典

int main(){map<string, string> dict;//法一：插入有名pair对象pair<string, string> kv1("left", "左边");dict.insert(kv1);//法二：插入匿名pair对象dict.insert(pair<string, string>("right", "右边"));//法三：调用 make_pair 函数dict.insert(make_pair("insert", "插入"));//法四：C++11后支持多参数的隐式类型转换dict.insert({ "string", "字符串" });return 0;}

  很明显，法四是最简洁的

  

1.5.2 验证

  我们用迭代器遍历一遍

map<string, string>::iterator it = dict.begin();while (it != dict.end()){    //pair不支持流插入和流提取cout << (*it).first << ":" << it->second << endl;++it;}

  通过迭代器遍历，我们也能清楚为什么 m a p map map 的返回值是 p a i r pair pair，而不是把 k e y key key 和 v a l u e value value 分开。
  因为 C++ 只支持返回一个值。如果将 k e y key key 和 v a l u e value value 分开，我是返回 k e y key key 还是 v a l u e value value 呢？都不合适吧。
  如何才能同时返回 k e y key key 和 v a l u e value value 呢？我将他们用一个结构体封装起来，我们返回一个结构体不就可以了吗
  
  如果我们插入：

pair<string, string> kv1("left", "叶子");

   l e f t left left 的键值对会被修改吗？
  不会。插入的时候只会去看 k e y key key 相不相等，如果相等插入失败，与value无关

  

1.5.3 再探pair

  有细心的小伙伴可能会发现： i n s e r t insert insert 插入的类型是 v a l u e value value_ t y p e type type，而 v a l u e value value_ t y p e type type 是 pair<const key, T(value)>。

  但是上面例子我们插入的都是 pair<string, string> 类型。模板参数不同他们就是不同的类型，就像 v e c t o r vector vector< i n t int int> 和 v e c t o r vector vector< c h a r char char> 虽然他们都是同一个模板，但是他们模板参数不同，他们就不是同一个类型。那为什么 pair<string, string> 和 pair<const string, string> 是两个完全不同的类型，我们还能插入成功呢？

  玄机就出现在 p a i r pair pair 的构造函数上

  更准确的说问题出现在pair的拷贝构造上。

   p a i r pair pair 的拷贝构造不是写死的，而是写成了一个模板。前面我们说过：类模板中的函数可以继续是函数模板。

一起来理解一下：
   i n s e r t insert insert 需要传递的是 pair<const string, string> 类型，但是现在我们传的是 pair<string, string>。因此我们要用传递的 pair<string, string> 类型去构造一个 pair<const string, string> 类型。
  这里就能体现这个函数模板的巧妙了：

template<class U, class V> pair (const pair<U,V>& pr):first(pr.first),second(pr.second){}

  当前这个函数模版的两个模版参数实例化出的都是 s t r i n g string string 类型，可是整个类模板实例化出的两个模板参数是 c o n s t const const s t r i n g string string 和 s t r i n g string string 类型。
   即 p r pr pr. f i r s t first first 是 s t r i n g string string 类型， t h i s this this-> f i r s t first first 是 c o n s t const const s t r i n g string string，用 s t r i n g string string 去构造 c o n s t const const s t r i n g string string 类型。

  其实template<class U, class V> pair (const pair<U,V>& pr)已经不一定是拷贝构造了，如果传的类型相同是拷贝构造，如果类型不同则是直接构造

  我们还能这样给 p a i r pair pair 类型插入

dict.insert(pair<const char*, const char*>("left", "左边"));

  只要是相似的类型，都可以插入！

  

1.5.4 make_pair

   m a k e make make_ p a i r pair pair 是一个函数模板，可以用来生成 pair。函数模板有一个特点：可以自己推演模板参数
  我们将 K e y Key Key 和 v a l u e value value 传给 m a k e make make _ p a i r pair pair，它可以自动推导他们的类型，并返回对应的 p a i r pair pair 对象

m a k e make make_ p a i r pair pair 的底层如下：

template <class T1, class T2>inline pair<T1, T2> make_pair(T1 x, T2 y){return (pair<T1, T2>(x, y));}

dict.insert(make_pair("right", "右边");string s1("xxx"), s2("yyy");dict.insert(make_pair(s1, s2));

   m a k e make make _ p a i r pair pair 这里 m a k e make make _ p a i r pair pair 推演出来的类型一个是 p a i r < c o n s t pair<const pair<const c h a r ∗ , c o n s t char*, const char∗,const c h a r ∗ > char*> char∗> 和 p a i r < s t r i n g , s t r i n g > pair<string, string> pair<string,string>，为什么能成功插入？是因为上面所讲的 p a i r pair pair 的构造函数模板

  

1.6 operator[]

   o p e r a t o r [ ] operator[] operator[] 的声明如下

mapped_type& operator[] (const key_type& k);

  在讲 o p e r a t o r [ ] operator[] operator[] 之前，我们先来看一个样例：
  

1.6.1 样例

  我们要统计各个水果出现的次数

int main(){// 利⽤find和iterator修改功能，统计⽔果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",\"苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// 先查找⽔果在不在map中// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1}// 2、在，则查找到的节点中⽔果对应的次数++auto ret = countMap.find(str);if (ret == countMap.end()){countMap.insert({ str, 1 });} else{ret->second++;}}     for (const auto & e : countMap){cout << e.first << ":" << e.second << endl;} return 0;}

  
  但其实，中间的判断逻辑用一行代码countMap[str]++;就可以搞定

int main(){// 利⽤find和iterator修改功能，统计⽔果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",\"苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){countMap[str]++;}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}return 0;}

  

1.6.2 认识operator[]

  为什么只用countMap[str]++;就可以完成在和不在两种逻辑的判断呢？

  我们先来看 o p e r a t o r [ ] operator[] operator[] 底层的代码实现

mapped_type& operator[] (const key_type& k){return (*((this->insert(make_pair(k,mapped_type()))).first)).second；}

  其中 k e y key key_ t y p e type type 就是 k e y key key 的类型， m a p p e d mapped mapped_ t y p e type type 就是 v a l u e value value 的类型

  上述代码是将三步合成了一步，可能大家看不懂，没关系，我们拆开来看

mapped_type& operator[] (const key_type& k){pair<iterator, bool> tmp1 = ((*this).insert(make_pair(k, mapped_type()));iterator tmp2 = *(tmp1).first;return tmp2.second;}

一、insert(make_pair(k, mapped_type())
   首先是调用 i n s e r t insert insert函数 插入一对键值对。 k e y key key 就是我们的 k k k， v a l u e value value 调用 v a l u e value value 类型的默认构造函数

  这里我们要重新认识一下insert函数，其声明如下：

pair<iterator, bool> insert (const value_type& val);

  可以看到， i n s e r t insert insert 的返回值是一个 pair，而不是我们认为的 b o o l bool bool。 p a i r pair pair 的 f i r s t first first 是一个迭代器， s e c o n d second second 是 b o o l bool bool。
  如果插入成功，返回的 p a i r pair pair 中的 f i r s t first first 就是新插入的值的迭代器， s e c o n d second second 为 true
  如果插入失败，表明容器中已经有相同的 k e y key key 了，此时返回的 p a i r pair pair 中的 f i r s t first first 就是容器中已经存在的 key 的迭代器， s e c o n d second second 为 f a l s e false false
  
二、*(tmp1).first;
  再接着，就是取出 i n s e r t insert insert 返回值 p a i r pair pair 中的 f i r s t first first 成员，这里即容器的迭代器。容器的迭代器也是一个 p a i r pair pair。
  需要注意的是， i n s e r t insert insert 返回的 p a i r pair pair 和迭代器的 p a i r pair pair 不是同一个类型： i n s e r t insert insert 返回的是pair<iterator, bool>，而迭代器类型是 pair<key, value>
  
三、return tmp2.second;
  最后就是返回迭代器中的 value 值的引用
  

---

  了解了 operator[] 后，我们就可以看看为什么一句countMap[str]++;代码就能完成整个逻辑的判断啦

  首先是先调用 i n s e r t insert insert 进行插入
  因为 m a p p e d mapped mapped _ t y p e type type 的类型是 i n t int int，其默认构造出的结果是 0，即插入的是 p a i r < s t r , 0 > pair<str, 0> pair<str,0>
   i n s e r t insert insert 返回值的是 p a i r pair pair< i t e r a t o r iterator iterator, b o o l bool bool>

  如果水果( s t r str str)不在，插入成功
   i t e r a t o r iterator iterator 是新插入位置的迭代器
  最后再返回其 v a l u e value value 值，此时刚刚插入的 v a l u e value value 值是 0，再++，变成 1

  如果水果( s t r str str)在，插入失败
   i t e r a t o r iterator iterator是容器中原来 k e y key key 位置的迭代器
  最后再返回其 v a l u e value value 值，再对 v a l u e value value 进行 ++，完成计数

  

1.6.3 operator[] 的功能

  了解 o p e r a t o r [ ] operator[] operator[] 的底层后，不难看出 m a p map map 的 o p e r a t o r [ ] operator[] operator[] 有三个功能

插入查找修改

int main(){map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在->插⼊ {"insert", string()}dict["insert"];// 插⼊+修改dict["left"] = "左边";// 修改dict["left"] = "左边、剩余";// key存在->查找cout << dict["left"] << endl;return 0;}

  

1.7 map 的其余接口

   m a p map map 的其余接口与前面 s e t set set 的对应接口都是相似的，这里就不再过多赘述了

成员函数	功能
find	查找指定元素
erase	删除指定元素
count	获取容器中指定元素值的元素个数
swap	交换两个容器中的数据
clear	清空容器
empty	判断容器是否为空
size	获取容器中元素的个数

  

1.8 multimap 与 map 的差异

   m u l t i m a p multimap multimap 和 m a p map map 的使用基本完全类似，主要区别点在于 m u l t i m a p multimap multimap 支持关键值 key 冗余，那么 i n s e r t insert insert / f i n d find find / c o u n t count count / e r a s e erase erase 都围绕着支持关键值 k e y key key 冗余有所差异，这里跟 s e t set set 和 m u l t i s e t multiset multiset 完全⼀样，比如 f i n d find find 时，有多个 k e y key key，返回中序第⼀个。其次就是 multimap 不支持 operator[]，因为支持 k e y key key 冗余， o p e r a t o r [ ] operator[] operator[] 就只能支持插入了，不能支持修改，而且也不知道返回那个 k e y key key 的 v a l u e value value 值。

  这里提一下 e q u a l equal equal r a n g e range range 接口：
   e q u a l equal equal r a n g e range range是获取相等元素的范围。也就是说你输入一个 k e y key key，它会返回包含所有 k e y key key 的范围。这个接口 m a p map map 也有，只是 m a p map map 不允许冗余，因此在 m a p map map 中没什么用

int main(){    std::multimap<char, int> mymm;    mymm.insert(std::pair<char, int>('a', 10));    mymm.insert(std::pair<char, int>('b', 20));    mymm.insert(std::pair<char, int>('b', 30));    mymm.insert(std::pair<char, int>('b', 40));    mymm.insert(std::pair<char, int>('c', 50));    mymm.insert(std::pair<char, int>('c', 60));    mymm.insert(std::pair<char, int>('d', 60));    std::cout << "mymm contains:\n";    for (char ch = 'a'; ch <= 'd'; ch++)    {        std::pair <std::multimap<char, int>::iterator, std::multimap<char, int>::iterator> ret;        ret = mymm.equal_range(ch);        std::cout << ch << " =>";        for (std::multimap<char, int>::iterator it = ret.first; it != ret.second; ++it)            std::cout << ' ' << it->second;        std::cout << '\n';    }    return 0;}

  
  
  
  
  

---

  好啦，本期关于 m a p map map 与 m u l t i m a p multimap multimap 的知识就介绍到这里啦，希望本期博客能对你有所帮助。同时，如果有错误的地方请多多指正，让我们在 C++ 的学习路上一起进步！