C++ STL map容器迭代器用法详解

 
无论是前面学习的序列式容器,还是关联式容器,要想实现遍历操作,就必须要用到该类型容器的迭代器。当然,map 容器也不例外。

C++ STL 标准库为 map 容器配备的是双向迭代器(bidirectional iterator)。这意味着,map 容器迭代器只能进行 ++p、p++、--p、p--、*p 操作,并且迭代器之间只能使用 == 或者 != 运算符进行比较。

值得一提的是,相比序列式容器,map 容器提供了更多的成员方法(如表 1 所示),通过调用它们,我们可以轻松获取具有指定含义的迭代器。

表 1 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 容器键值对唯一,因此该范围最多包含一个键值对)。

表 1 中多数的成员方法,诸如 begin()、end() 等,在学习序列式容器时已经多次使用过,它们的功能如图 2 所示。

C++ STL map部分成员方法示意图
图 2 表 1 部分成员方法的功能示意图

注意,图中 Ei 表示的是 pair 类对象,即键值对。对于 map 容器来说,每个键值对的键的值都必须保证是唯一的。

下面程序以 begin()/end() 组合为例,演示了如何遍历 map 容器:
#include <iostream>
#include <map>      // pair
#include <string>       // string
using namespace std;

int main() {
    //创建并初始化 map 容器
    std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},{"C语言教程","http://c.biancheng.net/c/"} };

    //调用 begin()/end() 组合,遍历 map 容器
    for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}
程序执行结果为:

C语言教程 http://c.biancheng.net/c/
STL教程 http://c.biancheng.net/stl/

读者可自行尝试使用其他组合(如 cbegin()/cend()、 rbegin()/rend() 等)遍历 map 容器。


除此之外,map 类模板中还提供了 find() 成员方法,它能帮我们查找指定 key 值的键值对,如果成功找到,则返回一个指向该键值对的双向迭代器;反之,其功能和 end() 方法相同。

举个例子:
#include <iostream>
#include <map>      // pair
#include <string>       // string
using namespace std;

int main() {
    //创建并初始化 map 容器
    std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
                                             {"C语言教程","http://c.biancheng.net/c/"},
                                             {"Java教程","http://c.biancheng.net/java/"} };
    //查找键为 "Java教程" 的键值对
    auto iter = myMap.find("Java教程");
    //从 iter 开始,遍历 map 容器
    for (; iter != myMap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}
程序执行结果为:

Java教程 http://c.biancheng.net/java/
STL教程 http://c.biancheng.net/stl/


此程序中,创建并初始化的 myMap 容器,默认会根据各键值对中键的值,对各键值对做升序排序,其排序的结果为:

<"C语言教程","http://c.biancheng.net/c/">
<"Java教程","http://c.biancheng.net/java/">
<"STL教程","http://c.biancheng.net/stl/">

在此基础上,通过调用 find() 方法,我们可以得到一个指向键为 "Java教程" 的键值对的迭代器,由此当使用 for 循环从该迭代器出开始遍历时,就只会遍历到最后 2 个键值对。

同时,map 类模板中还提供有 lower_bound(key) 和 upper_bound(key) 成员方法,它们的功能是类似的,唯一的区别在于:
  • lower_bound(key) 返回的是指向第一个键不小于 key 的键值对的迭代器;
  • upper_bound(key) 返回的是指向第一个键大于 key 的键值对的迭代器;

下面程序演示了它们的功能:
#include <iostream>
#include <map>      // pair
#include <string>       // string
using namespace std;

int main() {
    //创建并初始化 map 容器
    std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
                                             {"C语言教程","http://c.biancheng.net/c/"},
                                             {"Java教程","http://c.biancheng.net/java/"} };
    //找到第一个键的值不小于 "Java教程" 的键值对
    auto iter = myMap.lower_bound("Java教程");
    cout << "lower:" << iter->first << " " << iter->second << endl;
   
    //找到第一个键的值大于 "Java教程" 的键值对
    iter = myMap.upper_bound("Java教程");
    cout <<"upper:" << iter->first << " " << iter->second << endl;
    return 0;
}
程序执行结果为:

lower:Java教程 http://c.biancheng.net/java/
upper:STL教程 http://c.biancheng.net/stl/

lower_bound(key) 和 upper_bound(key) 更多用于 multimap 容器,在 map 容器中很少用到。


equal_range(key) 成员方法可以看做是 lower_bound(key) 和 upper_bound(key) 的结合体,该方法会返回一个 pair 对象,其中的 2 个元素都是迭代器类型,其中 pair.first 实际上就是 lower_bound(key) 的返回值,而 pair.second 则等同于 upper_bound(key) 的返回值。

显然,equal_range(key) 成员方法表示的一个范围,位于此范围中的键值对,其键的值都为 key。举个例子:
#include <iostream>
#include <utility>  //pair
#include <map>      // map
#include <string>       // string
using namespace std;

int main() {
    //创建并初始化 map 容器
    std::map<string, string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
                                   {"C语言教程","http://c.biancheng.net/c/"},
                                   {"Java教程","http://c.biancheng.net/java/"} };
    //创建一个 pair 对象,来接收 equal_range() 的返回值
    pair <std::map<string, string>::iterator, std::map<string, string>::iterator> myPair = myMap.equal_range("C语言教程");
    //通过遍历,输出 myPair 指定范围内的键值对
    for (auto iter = myPair.first; iter != myPair.second; ++iter) {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}
程序执行结果为:

C语言教程 http://c.biancheng.net/c/

和 lower_bound(key)、upper_bound(key) 一样,该方法也更常用于 multimap 容器,因为 map 容器中各键值对的键的值都是唯一的,因此通过 map 容器调用此方法,其返回的范围内最多也只有 1 个键值对。