我要评论1.1 map 和 multimap 参考文档
https://legacy.cplusplus.com/reference/map/
1.2 map 类的介绍
map 的声明如下：
key 就是 map 底层 关键字 的类型，t 是 map 底层 value 的类型， map 默认要求 key 支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第⼆个模版参数，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 类型介绍
在讲解 map 的使用前，我们先来认识一下 pair 类型，因为 map 就是用 pair 来存储 key 和 value
pair 是一个类模板，它将一对键值对耦合在一起，它有两个模板参数
template <class t1, class t2> struct pair;
它里面有两个成员：first 和 second；first 是 t1 类型，second 是 t2 类型
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)
{}
};
在 map 中，我们插入数据都是插入pair，t1 是const key， t2 是 t（value）
pair<const key, t>
也即key 为 first，value 为 second。
1.4 map的构造
map 的构造我们关注以下几个接口即可。
map 支持正向和反向迭代遍历，遍历默认按 key 的升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；⽀持迭代器就意味着支持范围 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 的插入方法
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;
}
通过迭代器遍历，我们也能清楚为什么 map 的返回值是 pair，而不是把 key 和 value 分开。
因为 c++ 只支持返回一个值。如果将 key 和 value 分开，我是返回 key 还是 value 呢？都不合适吧。
如何才能同时返回 key 和 value 呢？我将他们用一个结构体封装起来，我们返回一个结构体不就可以了吗
如果我们插入：
pair<string, string> kv1("left", "叶子");
left 的键值对会被修改吗？
不会。插入的时候只会去看 key 相不相等，如果相等插入失败，与value无关
1.5.3 再探pair
有细心的小伙伴可能会发现： insert 插入的类型是 value_type，而 value_ type 是 pair<const key, t(value)>。
但是上面例子我们插入的都是 pair<string, string> 类型。模板参数不同他们就是不同的类型，就像vector<int> 和vector<char> 虽然他们都是同一个模板，但是他们模板参数不同，他们就不是同一个类型。
那为什么 pair<string, string> 和 pair<const string, string> 是两个完全不同的类型，我们还能插入成功呢？
玄机就出现在 pair 的构造函数上
更准确的说问题出现在pair的拷贝构造上。
pair 的拷贝构造不是写死的，而是写成了一个模板。前面我们说过：类模板中的函数可以继续是函数模板。
一起来理解一下：
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)
{}
当前这个函数模版的两个模版参数实例化出的都是 string 类型，可是整个类模板实例化出的两个模板参数是 const string 和 string 类型。
即pr.first 是string 类型，this->first 是 const string，用string 去构造const 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
make_pair 是一个函数模板，可以用来生成 pair。函数模板有一个特点：可以自己推演模板参数
我们将key 和 value 传给 make_ pair，它可以自动推导他们的类型，并返回对应的 pair 对象
make_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));
pairpair 这里 make_pair 推演出来的类型一个是 pair<const char*,const char*> > 和 pair<string, string>，为什么能成功插入？是因为上面所讲的 pair 的构造函数模板
1.6 operator[]
operator[] 的声明如下
mapped_type& operator[] (const key_type& k);
在讲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]++;就可以完成在和不在两种逻辑的判断呢？
我们先来看operator[] 底层的代码实现
mapped_type& operator[] (const key_type& k)
{
return (*((this->insert(make_pair(k,mapped_type()))).first)).second；
}
其中 key_type 就是key 的类型， mapped_type 就是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())
首先是调用insert函数 插入一对键值对。key 就是我们的k，value 调用value 类型的默认构造函数
这里我们要重新认识一下insert函数，其声明如下：
pair<iterator, bool> insert (const value_type& val);
可以看到， insert 的返回值是一个 pair，而不是我们认为的 bool。 pair 的first 是一个迭代器，second 是 bool。
如果插入成功，返回的 pair 中的first 就是新插入的值的迭代器，second 为 true
如果插入失败，表明容器中已经有相同的key 了，此时返回的pair 中的first 就是容器中已经存在的 key 的迭代器，second 为 false
二、*(tmp1).first;
再接着，就是取出insert 返回值pair 中的first 成员，这里即容器的迭代器。容器的迭代器也是一个pair。
需要注意的是，insert 返回的pair 和迭代器的pair 不是同一个类型：insert 返回的是pair<iterator, bool>，而迭代器类型是 pair<key, value>
三、return tmp2.second;
最后就是返回迭代器中的 value 值的引用
了解了 operator[] 后，我们就可以看看为什么一句countmap[str]++;代码就能完成整个逻辑的判断啦
首先是先调用insert 进行插入
因为mapped _type 的类型是int，其默认构造出的结果是 0，即插入的是pair<str,0>
insert 返回值的是pair<iterator,bool>
如果水果(str)不在，插入成功
iterator 是新插入位置的迭代器
最后再返回其 value 值，此时刚刚插入的value 值是 0，再++，变成 1
如果水果(str)在，插入失败
iterator是容器中原来key 位置的迭代器
最后再返回其value 值，再对value 进行 ++，完成计数
1.6.3 operator[] 的功能
了解operator[] 的底层后，不难看出map 的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 的其余接口
map 的其余接口与前面set 的对应接口都是相似的，这里就不再过多赘述了
| 成员函数 | 功能 |
|---|---|
| find | 查找指定元素 |
| erase | 删除指定元素 |
| count | 获取容器中指定元素值的元素个数 |
| swap | 交换两个容器中的数据 |
| clear | 清空容器 |
| empty | 判断容器是否为空 |
| size | 获取容器中元素的个数 |
1.8 multimap 与 map 的差异
multimap 和 map 的使用基本完全类似，主要区别点在于 multimap 支持关键值 key 冗余，那么 insert / find / count / erase 都围绕着支持关键值 key 冗余有所差异，这里跟 set 和 multiset 完全⼀样，比如find 时，有多个 key，返回中序第⼀个。其次就是 multimap 不支持 operator[]，因为支持 key 冗余， operator[] 就只能支持插入了，不能支持修改，而且也不知道返回那个 key 的 value 值。
这里提一下 equal range range 接口：
equal range 是获取相等元素的范围。也就是说你输入一个 key，它会返回包含所有 key 的范围。这个接口 map 也有，只是 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;
}
总结
好啦，本期关于 map 与 multimap 的知识就介绍到这里啦，希望本期博客能对你有所帮助。同时，如果有错误的地方请多多指正，让我们在 c++ 的学习路上一起进步！
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论