map的原理（一文读懂map和multimap的差异原理）
map的原理（一文读懂map和multimap的差异原理）map的测试代码输出日志map的红黑树效果图(0 "zero")、(1 "one")、(5 "five")、(3 "three1")、(4 "four1")、(3 "three2")、(4 "four2")、(3 "three3")、(4 "four3")2.查看map和multimap最终插入和查询效果：①map的红黑树效果图和测试代码输出日志
概述map和multimap的共同点：
- map/multimap都是存储键值对的结构，可以改变value但是禁止改变key。
- map/multimap都是基于红黑树，故都是有序的，排序的依据是key，默认排序规则都是升序。
- map/multimap提供遍历操作及迭代器，按照正常规则（ iter）遍历，便能获得排序状态。
- map和multimap都定义于头文件 <map> 中。
map和multimap的差异点：
- map的key是不能重复的，可以使用at()或[]操作符进行查找或修改数据；
- multimap的key是可以重复的，未提供 at() 成员方法，也没有重载 [] 运算符；
我们先写两个测试函数(为了提高大家的阅读体验，测试代码放在文章最后进行展示)，看一下map和multimap在插入和查找方面的不同的点和相同点。
1.map和multimap先依次插入如下同样数据：
(0 "zero")、(1 "one")、(5 "five")、(3 "three1")、(4 "four1")、(3 "three2")、(4 "four2")、(3 "three3")、(4 "four3")
2.查看map和multimap最终插入和查询效果：
①map的红黑树效果图和测试代码输出日志
map的红黑树效果图
map的测试代码输出日志
②multimap的红黑树效果图和测试代码输出日志
multimap的红黑树效果图和测试代码输出日志
3.分析map和multimap的差异原理：
①map插入操作使用的是rb tree的insert_unique()函数，key不可重复，insert的返回值类型是pair<iterator bool>，第二个参数bool表示插入是否成功。
<STL源码剖析>片段
<STL源码剖析>片段
②multimap插入操作使用的是rb tree的insert_equal()函数，key可以重复，insert的返回值类型是iterator。
<STL源码剖析>片段
③map和multimap元素的查找原理是一样的。
multimap的查找方法主要有如下几种(map虽然常用find函数，但也支持其他几种查找方法):
|
find(key) |
在 multimap 容器中查找首个键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。 |
|
lower_bound(key) |
返回一个指向当前 multimap 容器中第一个大于或等于 key 的键值对的双向迭代器。 |
|
upper_bound(key) |
返回一个指向当前 multimap 容器中第一个大于 key 的键值对的迭代器。 |
|
equal_range(key) |
该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。 |
find的查找原理：
<STL源码剖析>片段
equal_range/(lower_bound upper_bound)的查找原理：
大家可以结合上述表格内容和“②multimap的红黑树效果图”内容对比查看，此处就不再文字描述了。
示例代码#include<iostream>
#include<map>
using namespace std;
void fun_multimap_test()
{
//构造数据
multimap<int string> m_map = { {0 "zero"} {1 "one"} };
m_map.insert(pair<int string>(5 "five"));
m_map.insert(make_pair(3 "three1"));
m_map.insert(pair<int string>(4 "four1"));
m_map.insert(make_pair(3 "three2"));
m_map.insert(pair<int string>(4 "four2"));
m_map.insert(make_pair(3 "three3"));
m_map.insert(pair<int string>(4 "four3"));
//打印数据
cout << endl;
cout << " multimap 最大允许存储数据个数:" << m_map.max_size() << endl;
cout << " 实际元素个数:" << m_map.size() << " 打印排序后的数据:" << endl;
multimap<int string>::iterator iter_print = m_map.begin();
for (; iter_print != m_map.end(); iter_print)
{
cout << " 迭代器地址:" << &*iter_print << " 键：" << (*iter_print).first << " 值：" << (*iter_print).second << endl;
}
//查找数据
size_t m_count = m_map.count(3);
cout << endl << " key=3的元素个数:" << m_count << endl;
//使用equal_range()获取指向键值匹配元素下界和上界的迭代器
cout << endl;
pair<multimap<int string>::iterator multimap<int string>::iterator> result = m_map.equal_range(3);
cout << " equal_range first 迭代器地址:" << &*(result.first) << endl;
cout << " equal_range second 迭代器地址:" << &*(result.second) << endl;
for (multimap<int string >::iterator it = result.first; it != result.second; it)
{
cout << " 查到数据的迭代器地址:" << &*it << " 键：" << it->first << " 值：" << it->second << endl;
}
//小测试
cout << endl << " 打印equal_range(3)返回迭代器再前和再后一个元素的信息：" << endl;
auto iter_1 = --(result.first);
cout << " equal_range --first 迭代器地址:" << &*iter_1 << " 键：" << iter_1->first << " 值：" << iter_1->second << endl;
auto iter_2 = (result.second);
cout << " equal_range second 迭代器地址:" << &*iter_2 << " 键：" << iter_2->first << " 值：" << iter_2->second << endl;
//使用lower_bound()和upper_bound()获取指向键值匹配元素下界和上界的迭代器
cout << endl;
auto iter_lower = m_map.lower_bound(3);
auto iter_upper = m_map.upper_bound(3);
cout << " lower_bound 迭代器地址:" << &*(iter_lower) << " 键：" << iter_lower->first << " 值：" << iter_lower->second << endl;
cout << " upper_bound 迭代器地址:" << &*(iter_upper) << " 键：" << iter_upper->first << " 值：" << iter_upper->second << endl;
for (multimap<int string >::iterator it = iter_lower; it != iter_upper; it)
{
cout << " 查到数据的迭代器地址:" << &*it << " 键：" << it->first << " 值：" << it->second << endl;
}
//使用find()和count()获取指向键值匹配的迭代器
cout << endl << " 打印find(3)结合count()信息：" << endl;
auto itr = m_map.find(3);
for (size_t i = 0; i < m_count; i itr)
{
cout << " 查到数据的迭代器地址:" << &*itr << " 键：" << itr->first << " 值：" << itr->second << endl;
}
}
void fun_map_test()
{
//构造数据
map<int string> normal_map = { {0 "zero"} {1 "one"} };
normal_map[5] = "five";
normal_map.insert(make_pair(3 "three1"));
normal_map.insert(pair<int string>(4 "four1"));
normal_map.insert(make_pair(3 "three2"));
normal_map.insert(pair<int string>(4 "four2"));
normal_map.insert(make_pair(3 "three3"));
normal_map.insert(pair<int string>(4 "four3"));
//打印数据
cout << endl;
cout << " map 最大允许存储数据个数:" << normal_map.max_size() << endl;
cout << " 实际元素个数:" << normal_map.size() << " 打印排序后的数据:" << endl;
map<int string>::iterator iter_print = normal_map.begin();
for (; iter_print != normal_map.end(); iter_print)
{
cout << " 迭代器地址:" << &*iter_print << " 键：" << (*iter_print).first << " 值：" << (*iter_print).second << endl;
}
//查找数据
size_t m_count = normal_map.count(3);
cout << endl << " key=3的元素个数:" << m_count << endl;
//使用equal_range()获取指向键值匹配元素下界和上界的迭代器
cout << endl;
pair<map<int string>::iterator map<int string>::iterator> result = normal_map.equal_range(3);
cout << " equal_range first 迭代器地址:" << &*(result.first) << endl;
cout << " equal_range second 迭代器地址:" << &*(result.second) << endl;
for (map<int string >::iterator it = result.first; it != result.second; it)
{
cout << " 查到数据的迭代器地址:" << &*it << " 键：" << it->first << " 值：" << it->second << endl;
}
//小测试
cout << endl << " 打印equal_range(3)返回迭代器再前和再后一个元素的信息：" << endl;
auto iter_1 = --(result.first);
cout << " equal_range --first 迭代器地址:" << &*iter_1 << " 键：" << iter_1->first << " 值：" << iter_1->second << endl;
auto iter_2 = (result.second);
cout << " equal_range second 迭代器地址:" << &*iter_2 << " 键：" << iter_2->first << " 值：" << iter_2->second << endl;
//使用lower_bound()和upper_bound()获取指向键值匹配元素下界和上界的迭代器
cout << endl;
auto iter_lower = normal_map.lower_bound(3);
auto iter_upper = normal_map.upper_bound(3);
cout << " lower_bound 迭代器地址:" << &*(iter_lower) << " 键：" << iter_lower->first << " 值：" << iter_lower->second << endl;
cout << " upper_bound 迭代器地址:" << &*(iter_upper) << " 键：" << iter_upper->first << " 值：" << iter_upper->second << endl;
for (map<int string >::iterator it = iter_lower; it != iter_upper; it)
{
cout << " 查到数据的迭代器地址:" << &*it << " 键：" << it->first << " 值：" << it->second << endl;
}
//使用find()和count()获取指向键值匹配的迭代器
cout << endl << " 打印find(3)结合count()信息：" << endl;
auto itr = normal_map.find(3);
for (size_t i = 0; i < m_count; i itr)
{
cout << " 查到数据的迭代器地址:" << &*itr << " 键：" << itr->first << " 值：" << itr->second << endl;
}
}
int main()
{
fun_multimap_test();
fun_map_test();
return 0;
}
原创不易，欢迎点赞、收藏、关注！
