c++的STL（6）-- map和multimap

map和multimap概述

map和multimap中存储的是使用pair对象的键值对。
map和multimap底层也是使用红黑树的数据结构进行实现的。所以，map和multimap内部存储的键值对也是有序的。并且内部数据也是使用链表的形式进行关联。所以其的迭代器和指针，也只能进行++，--(前置和后置)，==,!=。
而且和set一样map的键不能重复。(值可以) multimap可以重复。
map容器的键是不支持修改的，map<const 键类型,值类型>
map支持我们使用[]和at()函数，方便我们通过键来操作其对应的值。

表 C++ map容器常用成员方法
成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
find(key)	在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(key)	返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(key)	返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(key)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前 map 容器中存有键值对的个数。
max_size()	返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
operator[]	map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。
at(key)	找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
insert()	向 map 容器中插入键值对。
erase()	删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。
swap()	交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。
clear()	清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。
emplace()	在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
emplace_hint()	在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
count(key)	在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。

map和multimap使用必须导入头文件#include<map>

1. map的默认构造

代码

int main(void) {/*map<string, int> m1;map<int, int>m2;map<Student,int>m3;map<Student,Student*>m4;map<int,int*>m5;*/system("pause");return 0;
}

2. map的有参构造

代码

	/*map<string, int> m1({ {"张三",18},{"李四",20} });map<string, int> m1{ {"张三",18},{"李四",20} };pair<string, int> p1("张三",20);pair<string, int> p2("李四",30);map<string, int> m2({p1,p2});map<string, int> m2{p1,p2};map<string, int> m3(m1.begin(), m1.end());map<string, int> m3{ m1.begin(), m1.end() };map<string,int> m3(m1);  // 调用拷贝构造函数// 借助make_pair()函数map<string, int> m1({ make_pair("张三", 18) });map<string, int> m1{ make_pair("张三", 18) };*/

3.map容器元素的个数

代码: 使用size()函数

int main(void) {map<string, int>m1{ {"数学",108},{"语文",80},{"英语",100} };cout << "m1的键值对个数:" << m1.size() << endl;  // 3system("pause");return 0;
}

代码: 使用count()函数

int main(void) {map<string, int>m1{ {"数学",108},{"语文",80},{"英语",100} };map<string,int>::size_type t1 = m1.count("数学");cout << t1 << endl;system("pause");return 0;
}

4.map的元素访问(有变动)

代码: 使用[]和at()

int main(void) {string s1(20, '-');map<string, int>m1{ {"数学",108},{"语文",80},{"英语",100} };// 使用[]访问cout << "键: 数学, 值: " << m1["数学"] << endl;cout << s1 << endl;// 使用[]修改m1["数学"] = 110;// 使用[]添加m1["政治"] = 90;for (map<string, int>::iterator it = m1.begin(); it != m1.end(); it++) {cout << "键:" << (*it).first << " 值: " << (*it).second << endl;}cout << s1 << endl;// 使用at()访问cout << "键: 数学, 值: " << m1.at("数学") << endl;cout << s1 << endl;// 使用at()修改m1.at("语文") = 110;for (map<string, int>::iterator it = m1.begin(); it != m1.end(); it++) {cout << "键:" << (*it).first << " 值: " << (*it).second << endl;}cout << s1 << endl;system("pause");return 0;
}

5.map的迭代器

表 map 容器迭代器相关成员方法
成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。

map的迭代器也值能进行++，--(前置和后置)的运算操作，==,!=的比较操作，以及不能使用迭代器修改键的值。

其它的操作和前面的容器是想用的。

6. map在指定位置插入元素

代码: 使用insert()函数

	/*map<string, int> m1;pair<string, int> p1("张三", 18);m1.insert(p1);m1.insert(pair<string, int>("李四", 20));m1.insert(m1.begin(), p1);m1.insert({ p1,pair<string,int>("王五",30) });// 使用make_pair构建并返回一个pair对象，然后添加m1.insert(make_pair("张三", 25));// 使用内置类型value_type对象(value_type表示存储在容器中的元素类型，此处为pair类型)m1.insert(map<string, int>::value_type("张三", 25));*/

使用make_pair()函数和value_type对象插入

make_pair(value1,value2); // 此函数用于构建一个pair对象，然后返回，将返回的pair对象插入map中。
value_type 是容器内部的一个类，其表示容器中存储数据的类型，map中存储的类型就是pair类型，所以此时value_type就表示pair，创建的对象也是pair对象。

insert()返回值

当我们直接插入pair对象，insert函数返回一个pair<iterator,bool>。迭代器指插入元素的位置(插入失败，指向键值与插入元素相同的元素位置)，bool表示插入是否成功 (如果map中存放的键值和插入数据的键值有相同则会插入失败)。
当我们在指定位置插入pair对象时，insert(iterator,pair); // 其返回一个迭代器，指向插入元素的位置(插入失败，指向键值与插入元素相同的元素位置)
当使用初始化列表进行插入的时候，insert()返回void。(因为初始化列表一次可以插入多个pair对象)

代码: 使用emplace()和emplace_hint()函数

map<string, int> m1;// emplace()函数
m1.emplace("张三",20);
m1.emplace("李四", 21);// emplace_hint()函数
m1.emplace_hint(m1.begin(), "张三", 20);

两函数的区别

emplace()和emplace_hint()的区别是，emplace_hint()函数的第一个参数传入一个迭代器，用来指向插入元素的位置，后面的参数形式和emplace()一样。 (也就是输emplace_hint()用于在指定位置插入数据)

在指定位置插入时应该注意

map在指定位置插入数据和set是一样的，因为其都是有序的，所以即使我们指定了插入的位置，我们插入的数据也不一定会在对应位置上，因为插入的时候底层会根据你插入的键值与原来数据进行比较，放到相应的位置上。所以，即使我们指定了插入位置，数据也不一定会放到哪个位置。

7. map删除元素

代码: erase()和clear()函数

map<string, int> m1{ {"张三",25},{"李四",26} };// 擦除对应的数据
m1.erase("张三");
m1.erase(m1.begin());
m1.erase(m1.begin(), m1.end());// 请空map中的元素
m1.clear();

erase()函数的返回值

erase(key); // 返回的是size_t(或者size_type)类型，用于表示删除的键值个数。(因为map中的键不能相同，所以使用这重载返回的值只能为1或者0，但是multimap就可以大于1了)

map<string,int>::size_type t = m1.erase("张三");

erase(iter);和erase(beg,end); // 返回的是删除键值对下一个键值对的迭代器。

map<string,int>::iterator it1 = m1.erase(m1.begin());
map<string,int>::iterator it2 = m1.erase(m1.begin(), m1.end());

erase()函数和循环结合删除元素时注意事项

注意: 在erase和循环结合使用的时候，应该注意删除时迭代器的指向。(在vector中详述)

8. map查找元素

代码: 使用find()函数

map<string, int> m1{ {"张三",25},{"李四",26} };map<string,int>::iterator it1 = m1.find("张三");if (it1 != m1.end()) {cout << (*it1).first << ":" << (*it1).second << endl;
}
else {cout << "没有找到!!!" << endl;
}

如何判断find()是否查找成功

find()如果没有找到对应元素，那么就会返回一个和end()函数返回值一样的迭代器，所以我们判断是否查找成功，就可以通过find()返回的迭代器是否等于end()返回的迭代器。

代码:使用[]和at()访问

在前面已经说过了

代码: 使用lower_bound(),upper_bound()和equal_range()函数

map<int, string> m1{ {25,"张三"},{26,"李四"} };map<int, string>::iterator it1 = m1.lower_bound(25);
map<int, string>::iterator it2 = m1.upper_bound(25);
pair<map<int, string>::iterator,map<int, string>::iterator> p1 = m1.equal_range(25);

如果没有我们要找的键值会怎么样

如果key不存在，那么两个迭代器就都指向按照规则key的下一个元素，(如果从小到大排列就指向第一个key的元素)。当然如果按照规则，set排在最后，则两个迭代器都指向最后一个元素的下一位。(比如: 从小到大排时，set比map中的元素都要大)
举个例子，lower_bound(key); 要找到是>=key的键值对(并且排序是从小到大排)，如果键值为key的键值对不存在，那么返回的两个迭代器，就会指向第一个键值>key的键值对。

9. map的排序规则

map和set是类似的，其内部都是有序的，同样我们也都可以指定数据的排序规则(使用函数对象)
在默认情况下map是使用内置的less函数对象，进行从小到大排序的。

map<int, string,greater<int>> m1{ {25,"张三"},{26,"李四"} };

上面我们使用另外一个内置的函数对象greater,其是让map从大到小排列。
注意: 函数对象我们只需要指定一个类型就行，用这个类型的数据作为排序的数据。

10. map的value_comp()函数

map<int, string, greater<int>>::value_compare v1 = m1.value_comp();map<int, string, greater<int>>::value_type t1 = make_pair(25,"张三");
map<int, string, greater<int>>::value_type t2 = make_pair(26,"李四");if (v1(t1, t2)) {cout << "t1在t2之前" << endl;
}
else {cout << "t2在t1之后" << endl;
}

11. map中的key_comp()函数

map<int, string,greater<int>> m1{ {25,"张三"},{26,"李四"} };greater<int> g1 = m1.key_comp();if (g1(1, 2)) {cout << "1在2之前" << endl;
}
else {cout << "1在2之后" << endl;
}

12. map的其它函数

swap(m1); //使调用此函数的map容器和m1的元素进行互换
empty(); // 判断map容器是否为空
max_size(); // 和vector类似

13. map和multimap的不同之处

multimap和map的函数大多数在使用的时候都是一样的，我们就不再说明了。

但是由于multimap可以存放不同的元素所以和map会有点区别。

区别:

multimap在调用erase(key),方法时期返回值可以大于1。
同理count(key)这个函数的返回值也可以大于1。
lower_bound(key)、upper_bound(key)、equal_range(key)其对应查找的数据范围也不再是一个，所以这些函数更加常用于multimap。

注意事项

由于map内部是有序的，所以我们不能随便修改其内部的值，因为如果修改了某一位置的值，很可能会导致其不再是有序排列的了。所以使用迭代器(即使迭代器不是const修饰的)或者其它方式都不能对map中的元素进行修改。如果要修改，那必须将这个元素删除，然后再添加一个新元素。
size_type和value_type和vector的用法一样。(或者其他的内嵌类型)
multimap是类似的。