c++拓展-8:关联式容器STL map

map容器

简要说明及其定义

map容器是关联式容器的一种，存储的全都是pair对象，即用pair类模板创建的键值对，其中各个键值对的键和值可以是任何数据类型，包括基本数据类型或结构体或自定义的类，通常来说，map容器中各个键值对都选用string字符串作为键的类型

map容器会根据键的大小将元素按既定顺序排列，默认使用less< T >排序规则，会根据键的大小对所有键值作升序排序，但也可以手动指定或自定义这种排序规则

对于map容器中的键值对来说，键的值不可以重复也不能修改，即每个键都是独一无二的对应一个元素，且类型使用const修饰

map容器定义在头文件< map >中，其容器模板有键类型、值类型、排序规则、分配器对象的类型，以上4个参数，其中后两者都有默认值，最后一个参数几乎不会用到

其中，已有可供修改的排序规则包括：greater< T>【降序】、less< T >【升序】

map容器常见创建方法：

map<string,int> map1;
//创建空的map容器
map<string,string> map2{{"key1","value1"},{"key2","value2"}};
//创建map容器并初始化存入两个键值对
map<string,int> map3(map1);
//复制创建map3
map<string,int> map4()	//将临时map对象传递给需要初始化的map容器
{
	map<string,int> map5(map2);
	return  map4;
}
map<string,int> map6(++map2.begin(),map2.end());
//取已建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 属性，不能用于修改容器内存储的键值对
find(key)	在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回最后一个元素+1位置的迭代器。另外，如果 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 容器配备的是双向迭代器（bidirectional iterator），也就是map 容器迭代器只能进行 ++p、p++、–p、p–、*p 操作，并且迭代器之间只能使用 == 或者 != 运算符进行比较

成员方法	功能
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 容器键值对唯一，因此该范围最多包含一个键值对）

其中lower_bound(key)和upper_bound(key)更加多用于multimap容器，在map容器中很少用到

equal_range(key)可以看做是lower_bound(key)和upper_bound(key)的结合，返回一个pair对象，两个元素都是迭代器类型，其中pair.first是lower_bound(key)的返回值，pair.second是upper_bound(key)的返回值，其本身表示键值对中键的值都为key的一个范围

由于map容器中键值对的键都是唯一的，所以调用equal_range(key)函数时，其范围内也最多只有一个键值对

按键索值

map类模板对[]运算符进行了重载，可以借助类似数组下标的方式直接访问数组中元素，通过指定的键可以得到其对应的值

map<int,string> map1{1,"first"},{2,"second"},{3,"third"};
string value=map1[2];
//此时value的值等于second

当无法在已有map容器的元素中找到对应键时，会向map容器中添加一个符合要求的新键值对，其对应值默认为0

map容器也提供at()成员函数，通过输入键查找对应的值，但如果查找失败不会创建新键值对，而是抛出out_of_range异常

同样，使用find()函数也可以间接的实现这个功能，但返回的是一个迭代器，指向查找到的键值对，查找失败时返回最后一个键值对之后的位置

插入数据

同上，[]运算符在没有查找到对应键时会添加键值对，配合map容器本身的排序功能便可以实现插入

除此之外，insert()成员函数专门用于向map中插入键值对数据

注：这里所谓的“插入”，指的是 insert() 方法可以将新的键值对插入到 map 容器中的指定位置，但这与 map 容器会自动对存储的键值对进行排序并不冲突。当使用 insert() 方法向 map 容器的指定位置插入新键值对时，其底层会先将新键值对插入到容器的指定位置，如果其破坏了 map 容器的有序性，该容器会对新键值对的位置进行调整

insert()既可以不指定插入位置，直接将键值对添加到map容器中，又可以向map容器的指定位置插入键值对

//不指定位置
pair<iterator,bool> insert(const value_type&val);
//引用传递一个键值对

template<class p>
pair<iterator,bool> insert(p&&val);
//以右值引用的方式传递键值对

//指定位置
iterator insert(const_interator position,const value_type&val);
//引用传递一个键值对

template<class p>
  iterator insert(const_iterator position,p&&val);
//以右值引用的方式传递键值对

//插入其他map容器中指定区域的所有键值对
template <class InputIterator>
  void insert (InputIterator first, InputIterator last);
//其中first和last都是迭代器，<first,last>可以表示某map容器中的指定区域

//一次性插入多个键值对
void insert ({val1, val2, ...});

其中，不指定位置时，val是键值对类型的变量，该方法会返回一个pair对象，pair.first代表迭代器，pair.second为bool型变量：

• 如果成功插入val，返回的pair对象中的迭代器指向val，bool为true
• 如果插入失败，返回的pair对象中的迭代器指向和val的键相同的键值对p，bool为false

指定位置时，val依旧是键值对类型变量，而insert()的返回值将会是迭代器而不再是pair对象：

• 如果插入成功，insert()返回一个指向map容器中已插入键值对的迭代器
• 如果插入失败，insert()返回一个map容器中指向和val的键相同的键值对

以上除指定位置的差别外，语法格式区别在于传参方式不同，局部和全局变量都采用普通引用传参，对于临时的键值对变量则以右值引用方式传参

而即使指定位置，insert()插入之后map容器依旧会对自己进行排序，决定插入位置的不是insert()传入的迭代器，而是新键值对中的键的值

除了 insert() ，map 类模板还提供 emplace() 和 emplace_hint() ，它们也可以完成向 map 容器中插入键值对的操作，且效率还比 insert() 高

其中，emplace() 方法的语法格式如下：

template <class... Args>
 pair<iterator,bool> emplace (Args&&... args);

参数 (Args&&… args) 指的是，这里只需要将创建新键值对所需的数据作为参数直接传入即可，此方法可以自行利用这些数据构建出指定的键值对。另外，该方法的返回值也是一个 pair 对象，其中 pair.first 为一个迭代器，pair.second 为一个 bool 类型变量：

• 当该方法将键值对成功插入到 map 容器中时，其返回的迭代器指向该新插入的键值对，同时 bool 变量的值为 true；
• 当插入失败时，则表明 map 容器中存在具有相同键的键值对，此时返回的迭代器指向此具有相同键的键值对，同时 bool 变量的值为 false。

emplace_hint() 方法的功能和 emplace() 类似，其语法格式如下：

template <class... Args>
 iterator emplace_hint (const_iterator position, Args&&... args);

显然和 emplace() 语法格式相比，有以下 2 点不同：

1. 该方法不仅要传入创建键值对所需要的数据，还需要传入一个迭代器作为第一个参数，指明要插入的位置（新键值对键会插入到该迭代器指向的键值对的前面）；
2. 该方法的返回值是一个迭代器，而不再是 pair 对象。当成功插入新键值对时，返回的迭代器指向新插入的键值对；反之，如果插入失败，则表明 map 容器中存有相同键的键值对，返回的迭代器就指向这个键值对。

和 insert() 方法一样，虽然 emplace_hint() 方法指定了插入键值对的位置，但 map 容器为了保持存储键值对的有序状态，可能会移动其位置

删除数据

map容器删除数据的函数只有如下两个：

• erase() ：删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对
• clear() ：清空 map 容器中所有的键值对，使 map 容器的 size() 为 0

用法可参照前面的其他容器的用法，此处不详细说明

总结

• 定义方式
• map的迭代器
• 访问元素
• 添删元素

• map<键类型,值类型,排序方式(可省)，分配器对象类型(不常用)> 容器名；

  ——创建空的map容器

• map<键类型,值类型,排序方式(可省)，分配器对象类型(不常用)> 容器名{以{“键”,”值”}的格式列举键值对}；

  ——创建map容器并初始化存入键值对

• map<键类型,值类型,排序方式(可省)，分配器对象类型(不常用)> 容器名(另一个容器名)；

  ——复制创建map容器

• map<键类型,值类型,排序方式(可省)，分配器对象类型(不常用)> 容器名(函数参数表){函数体部分，需要返回一个map对象}

  ——将函数中的临时map对象传递给需要初始化的map容器

• map<键类型,值类型,排序方式(可省)，分配器对象类型(不常用)> 容器名(另一容器的初始位置,另一容器的末位置)；

  ——取已建map容器中指定区域内的键值对，创建并初始化新的map容器

• begin（）/end（）：返回“开头/结尾+1”处的元素的正向迭代器
• 前加r：返回“开头-1/结尾”的反向迭代器——rbegin（）/rend（）
• 前加c：返回const类型的元素迭代器——cbegin()/cend(),crbegin()/crend()
• 只能进行 ++p、p++、–p、p–、*p 操作
• 只能使用 == 或者 != 运算符进行比较
• lower_bound(key)——返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器
• upper_bound(key) ——返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器
• equal_range(key)——返回键值对可以看做是<lower_bound(key),upper_bound(key) >

• 以[]运算符访问已知键对应的值，如果查找失败则插入为新元素，值默认为0
• 使用at()函数访问，查找失败返回out_of_range错误
• 使用find()函数，返回一个迭代器指向查找到的键值对，查找失败时返回最后一个键值对之后的位置

插入元素：

• 不指定位置：

  pair<iterator,bool> insert(const value_type&val);
  ——引用传递一个键值对

  template< class p >
  pair<iterator,bool> insert(p&&val);
  ——以右值引用的方式传递键值对

• 指定位置

  iterator insert(const_interator position,const value_type&val);
  ——引用传递一个键值对

  template< class p >
  iterator insert(const_iterator position,p&&val);
  ——以右值引用的方式传递键值对

• 插入其他map容器中指定区域的所有键值对
  template < class InputIterator >
  void insert (InputIterator first, InputIterator last);
  ——其中first和last都是迭代器，<first,last>可以表示某map容器中的指定区域

• ——一次性插入多个键值对
  void insert ({val1, val2, …});

删除元素：

• erase() ：删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对
• clear() ：清空 map 容器中所有的键值对，使 map 容器的 size() 为 0

代码实例

#include <iostream>
#include <map>  //map
#include <string> //string
using namespace std;
int main()
{
    //创建一个空 map 容器
    std::map<string, string> mymap;
   
    //创建一个真实存在的键值对变量
    std::pair<string, string> STL = { "2","2-2" };
   
    //创建一个接收 insert() 方法返回值的 pair 对象
    std::pair<std::map<string, string>::iterator, bool> ret;
   
    //插入 STL，由于 STL 并不是临时变量，因此会以第一种方式传参
    ret = mymap.insert(STL);
    cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
    //以右值引用的方式传递临时的键值对变量
    ret = mymap.insert({ "1","1-2" });
    cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
    //插入失败样例
    ret = mymap.insert({ "2","2-3" });
    cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
    return 0;
}

输出结果为：

ret.iter = <{2,2-2}, 1>
ret.iter = <{1,1-2}, 1>
ret.iter = <{2,2-2}, 0>

#include <iostream>
#include <map>  //map
#include <string> //string
using namespace std;
int main()
{
    //创建一个空 map 容器
    std::map<string, string> mymap;
   
    //创建一个真实存在的键值对变量
    std::pair<string, string> STL = { "2","2-2" };
    //指定要插入的位置
    std::map<string, string>::iterator it = mymap.begin();
    //向 it 位置以普通引用的方式插入 STL
    auto iter1 = mymap.insert(it, STL);
    cout << iter1->first << " " << iter1->second << endl;
    //向 it 位置以右值引用的方式插入临时键值对
    auto iter2 = mymap.insert(it, std::pair<string, string>("1", "1-2"));
    cout << iter2->first << " " << iter2->second << endl;
    //插入失败样例
    auto iter3 = mymap.insert(it, std::pair<string, string>("2", "2-3"));
    cout << iter3->first << " " << iter3->second << endl;
    return 0;
}

输出结果为：

2 2-2
1 1-2
2 2-2

#include <iostream>
#include <map>  //map
#include <string> //string
using namespace std;
int main()
{
    //创建并初始化 map 容器
    std::map<std::string, std::string>mymap{ {"2","2-2"},
                                                {"1","1-2"},
                                                {"3","3-2"} };
    //创建一个空 map 容器
    std::map<std::string, std::string>copymap;
    //指定插入区域
    std::map<string, string>::iterator first = ++mymap.begin();
    std::map<string, string>::iterator last = mymap.end();
    //将<first,last>区域内的键值对插入到 copymap 中
    copymap.insert(first, last);
    //遍历输出 copymap 容器中的键值对
    for (auto iter = copymap.begin(); iter != copymap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}

输出结果为：

3 3-2
2 2-2