C++ unordered_map迭代器的用法

 
C++ STL 标准库中,unordered_map 容器迭代器的类型为前向迭代器(又称正向迭代器)。这意味着,假设 p 是一个前向迭代器,则其只能进行 *p、p++、++p 操作,且 2 个前向迭代器之间只能用 == 和 != 运算符做比较。

在 unordered_map 容器模板中,提供了表 1 所示的成员方法,可用来获取指向指定位置的前向迭代器。

表 1 C++ unordered_map迭代器相关成员方法
成员方法 功能
begin() 返回指向容器中第一个键值对的正向迭代器。
end()  返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上增加了 const 属性,即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,即该方法返回的迭代器不能用于修改容器内存储的键值对。
find(key) 查找以 key 为键的键值对,如果找到,则返回一个指向该键值对的正向迭代器;反之,则返回一个指向容器中最后一个键值对之后位置的迭代器(如果 end() 方法返回的迭代器)。
equal_range(key) 返回一个 pair 对象,其包含 2 个迭代器,用于表明当前容器中键为 key 的键值对所在的范围。

值得一提的是,equal_range(key) 很少用于 unordered_map 容器,因为该容器中存储的都是键不相等的键值对,即便调用该成员方法,得到的 2 个迭代器所表示的范围中,最多只包含 1 个键值对。事实上,该成员方法更适用于 unordered_multimap 容器(该容器后续章节会做详细讲解)。


下面的程序演示了表 1 中部分成员方法的用法。
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
    //创建 umap 容器
    unordered_map<string, string> umap{
        {"Python教程","http://c.biancheng.net/python/"},
        {"Java教程","http://c.biancheng.net/java/"},
        {"Linux教程","http://c.biancheng.net/linux/"} };

    cout << "umap 存储的键值对包括:" << endl;
    //遍历输出 umap 容器中所有的键值对
    for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
        cout << "<" << iter->first << ", " << iter->second << ">" << endl;
    }
    //获取指向指定键值对的前向迭代器
    unordered_map<string, string>::iterator iter = umap.find("Java教程");
    cout <<"umap.find(\"Java教程\") = " << "<" << iter->first << ", " << iter->second << ">" << endl;
    return 0;
}
程序执行结果为:

umap 存储的键值对包括:
<Python教程, http://c.biancheng.net/python/>
<Linux教程, http://c.biancheng.net/linux/>
<Java教程, http://c.biancheng.net/java/>
umap.find("Java教程") = <Java教程, http://c.biancheng.net/java/>


需要注意的是,在操作 unordered_map 容器过程(尤其是向容器中添加新键值对)中,一旦当前容器的负载因子超过最大负载因子(默认值为 1.0),该容器就会适当增加桶的数量(通常是翻一倍),并自动执行 rehash() 成员方法,重新调整各个键值对的存储位置(此过程又称“重哈希”),此过程很可能导致之前创建的迭代器失效。

所谓迭代器失效,针对的是那些用于表示容器内某个范围的迭代器,由于重哈希会重新调整每个键值对的存储位置,所以容器重哈希之后,之前表示特定范围的迭代器很可能无法再正确表示该范围。但是,重哈希并不会影响那些指向单个键值对元素的迭代器。

举个例子:
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
    //创建 umap 容器
    unordered_map<int, int> umap;
    //向 umap 容器添加 50 个键值对
    for (int i = 1; i <= 50; i++) {
        umap.emplace(i, i);
    }
    //获取键为 49 的键值对所在的范围
    auto pair = umap.equal_range(49);
    //输出 pair 范围内的每个键值对的键的值
    for (auto iter = pair.first; iter != pair.second; ++iter) {
        cout << iter->first <<" ";
    }
    cout << endl;
    //手动调整最大负载因子数
    umap.max_load_factor(3.0);
    //手动调用 rehash() 函数重哈希
    umap.rehash(10);
    //重哈希之后,pair 的范围可能会发生变化
    for (auto iter = pair.first; iter != pair.second; ++iter) {
        cout << iter->first << " ";
    }
    return 0;
}
程序执行结果为:

49
49 17

观察输出结果不难发现,之前用于表示键为 49 的键值对所在范围的 2 个迭代器,重哈希之后表示的范围发生了改变。

经测试,用于遍历整个容器的 begin()/end() 和 cbegin()/cend() 迭代器对,重哈希只会影响遍历容器内键值对的顺序,整个遍历的操作仍然可以顺利完成。