【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 类的介绍

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

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;

1.3 pair 类型介绍

在讲解 $ma p$ 的使用前，我们先来认识一下 $p ai r$ 类型，因为 $ma p$ 就是用 $p ai r$ 来存储 $k ey$ 和 $v a l u e$

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

template <class T1, class T2> struct pair;

它里面有两个成员： $f i rs t$ 和 $seco n d$ ； $f i rs t$ 是 $T 1$ 类型， $seco n d$ 是 $T 2$ 类型

$p ai r$ 的底层大致如下：

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){}
};

在 $ma p$ 中，我们插入数据都是插入 $p ai r$ ， $T 1$ 是 $co n s t$ $Key$ ， $T 2$ 是 $T$ （ $v a l u e$ ）

pair<const Key, T>

也即 $Key$ 为 $f i rs t$ ， $v a l u e$ 为 $seco n d$ 。

1.4 map的构造

$ma p$ 的构造我们关注以下几个接口即可。
$ma p$ 支持正向和反向迭代遍历，遍历默认按 $k ey$ 的升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；⽀持迭代器就意味着支持范围 $f or$ ，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 的插入方法

$ma p$ 的插入方式有多种

例如： 我们创建一个字典

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;
}

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

如果我们插入：

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

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

1.5.3 再探pair

有细心的小伙伴可能会发现： $in ser t$ 插入的类型是 $v a l u e$ _ $t y p e$ ，而 $v a l u e$ _ $t y p e$ 是 pair<const key, T(value)>。

但是上面例子我们插入的都是 pair<string, string> 类型。模板参数不同他们就是不同的类型，就像 $v ec t or$ < $in t$ > 和 $v ec t or$ < $c ha r$ > 虽然他们都是同一个模板，但是他们模板参数不同，他们就不是同一个类型。那为什么 pair<string, string> 和 pair<const string, string> 是两个完全不同的类型，我们还能插入成功呢？

玄机就出现在 $p ai r$ 的构造函数上

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

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

一起来理解一下：
$in ser t$ 需要传递的是 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 in g$ 类型，可是整个类模板实例化出的两个模板参数是 $co n s t$ $s t r in g$ 和 $s t r in g$ 类型。
即 $p r$ . $f i rs t$ 是 $s t r in g$ 类型， $t hi s$ -> $f i rs t$ 是 $co n s t$ $s t r in g$ ，用 $s t r in g$ 去构造 $co n s t$ $s t r in g$ 类型。

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

我们还能这样给 $p ai r$ 类型插入

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

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

1.5.4 make_pair

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

$mak e$ _ $p ai r$ 的底层如下：

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));

$mak e$ _ $p ai r$ 这里 $mak e$ _ $p ai r$ 推演出来的类型一个是 $p ai r < co n s t$ $c ha r *, co n s t$ $c ha r * >$ 和 $p ai r < s t r in g, s t r in g >$ ，为什么能成功插入？是因为上面所讲的 $p ai r$ 的构造函数模板

1.6 operator[]

$o p er a t or []$ 的声明如下

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

在讲 $o p er a t or []$ 之前，我们先来看一个样例：

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 er a t or []$ 底层的代码实现

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

其中 $k ey$ _ $t y p e$ 就是 $k ey$ 的类型， $ma pp e d$ _ $t y p e$ 就是 $v a l u e$ 的类型

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

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())
首先是调用 $in ser t$ 函数插入一对键值对。 $k ey$ 就是我们的 $k$ ， $v a l u e$ 调用 $v a l u e$ 类型的默认构造函数

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

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

可以看到， $in ser t$ 的返回值是一个 pair，而不是我们认为的 $b oo l$ 。 $p ai r$ 的 $f i rs t$ 是一个迭代器， $seco n d$ 是 $b oo l$ 。
如果插入成功，返回的 $p ai r$ 中的 $f i rs t$ 就是新插入的值的迭代器， $seco n d$ 为 true
如果插入失败，表明容器中已经有相同的 $k ey$ 了，此时返回的 $p ai r$ 中的 $f i rs t$ 就是容器中已经存在的 key 的迭代器， $seco n d$ 为 $f a l se$

二、*(tmp1).first;
再接着，就是取出 $in ser t$ 返回值 $p ai r$ 中的 $f i rs t$ 成员，这里即容器的迭代器。容器的迭代器也是一个 $p ai r$ 。
需要注意的是， $in ser t$ 返回的 $p ai r$ 和迭代器的 $p ai r$ 不是同一个类型： $in ser t$ 返回的是pair<iterator, bool>，而迭代器类型是 pair<key, value>

三、return tmp2.second;
最后就是返回迭代器中的 value 值的引用

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

首先是先调用 $in ser t$ 进行插入
因为 $ma pp e d$ _ $t y p e$ 的类型是 $in t$ ，其默认构造出的结果是 0，即插入的是 $p ai r < s t r, 0 >$
$in ser t$ 返回值的是 $p ai r$ < $i t er a t or$ , $b oo l$ >

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

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

1.6.3 operator[] 的功能

了解 $o p er a t or []$ 的底层后，不难看出 $ma p$ 的 $o p er a t or []$ 有三个功能

插入
查找
修改

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 的其余接口

$ma p$ 的其余接口与前面 $se t$ 的对应接口都是相似的，这里就不再过多赘述了

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

1.8 multimap 与 map 的差异

$m u lt ima p$ 和 $ma p$ 的使用基本完全类似，主要区别点在于 $m u lt ima p$ 支持关键值 key 冗余，那么 $in ser t$ / $f in d$ / $co u n t$ / $er a se$ 都围绕着支持关键值 $k ey$ 冗余有所差异，这里跟 $se t$ 和 $m u lt i se t$ 完全⼀样，比如 $f in d$ 时，有多个 $k ey$ ，返回中序第⼀个。其次就是 multimap 不支持 operator[]，因为支持 $k ey$ 冗余， $o p er a t or []$ 就只能支持插入了，不能支持修改，而且也不知道返回那个 $k ey$ 的 $v a l u e$ 值。

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

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;
}