【C++】—— map 与 multimap

【C++】—— map 与 multimap

• 1 map
  • 1.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 再探pair
    • 1.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<classKey,// map::key_typeclassT,// map::mapped_typeclassCompare= less<Key>,// map::key_compareclassAlloc= allocator<pair<const Key, T>>// map::allocator_type>classmap;

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<classT1,classT2>structpair;

它里面有两个成员： 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<classT1,classT2>structpair{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<classU,classV>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) ⽆参默认构造explicitmap(const key_compare& comp =key_compare(),const allocator_type& alloc =allocator_type());// range (2) 迭代器区间构造template<classInputIterator>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 的插入方式有多种

例如： 我们创建一个字典

intmain(){ 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","字符串"});return0;}

很明显，法四是最简洁的

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<classU,classV>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<constchar*,constchar*>("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<classT1,classT2>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 样例

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

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

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

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

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[] 有三个功能

插入查找修改

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

1.7 map 的其余接口

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

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 中没什么用

intmain(){ 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';}return0;}

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