Maine

纵有疾风起,人生不言弃

C++ STL迭代器( iterator )

迭代器是一种检查容器内元素并遍历元素的数据类型。要访问顺序容器和关联容器中的元素,需要通过“迭代器(iterator)”进行。C++更青睐使用迭代器操作元素而不是下标操作,因为标准库为每一种标准容器(如vector)都定义了一种迭代器类型,而只有少数容器(如vector)支持下标操作访问容器元素。迭代器可以指向容器中的某个元素,通过迭代器就可以读写它指向的元素。从这一点上看,迭代器和指针类似。

定义和分类

  1. 正向迭代器,定义方法如下:
容器类名::iterator  迭代器名;
  1. 常量正向迭代器,定义方法如下
容器类名::const_iterator  迭代器名;
  1. 反向迭代器,定义方法如下:
容器类名::reverse_iterator  迭代器名;
  1. 常量反向迭代器,定义方法如下:
容器类名::const_reverse_iterator  迭代器名;

迭代器的用法

迭代器都可以进行 ++ 操作。反向迭代器和正向迭代器在进行++操作的区别在于:

  • 对正向迭代器进行++操作时,迭代器会指向容器中的后一个元素;
  • 而对反向迭代器进行++操作时,迭代器会指向容器中的前一个元素。

每种容器都定义了一对名为beginend的函数,用于返回正向迭代器。begin 成员函数返回指向容器中第一个元素的迭代器,end 成员函数返回的不是指向最后一个元素的迭代器,而是指向最后一个元素后面的位置的迭代器,因此循环的终止条件是iter != v.end()。当然还有 rbeginrend 函数,返回反向迭代器。

同时 *迭代器名 表示迭代器指向的元素。使用非常量迭代器还能修改其指向的元素的值。

需要格外注意的是:如果迭代器指向了容器中最后一个元素的后面或第一个元素的前面,再通过该迭代器访问元素,就有可能导致程序崩溃,这和访问 NULL 或未初始化的指针指向的地方类似。

具体示例:

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, const char * argv[]) {

    vector<int> v;              // 定义一个 int 类型的可变长数组
    for (int i=0; i<4; ++i) {
        v.push_back(i);         // push_back 在 vector 容器尾部添加元素
    }

    // 用迭代器遍历容器
    vector<int>::iterator iter; // 定义一个正向迭代器
    for (iter = v.begin(); iter != v.end(); ++iter) {
        cout << *iter << " ";  // 使用 *iter 可以操作元素,是不是有点像指针
        *iter += 1;             // 每个元素加一
    }

    cout << endl;

    // 反向迭代器遍历
    vector<int>::reverse_iterator riter;    // 定义一个反向迭代器
    for (riter = v.rbegin(); riter != v.rend(); ++riter) {
        cout << *riter << " ";
    }
    cout << endl;

    return 0;
}

输出结果:

0 1 2 3 
4 3 2 1 

注意,容器适配器 stack、queue 和 priority_queue 没有迭代器。容器适配器有一些成员函数,可以用来对元素进行访问。

迭代器的功能分类

不同容器的迭代器,其功能有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序算法。

常用的迭代器按功能可分为输入、输出、正向、双向、随机访问五种,比较常用的是后三种。

  1. 正向迭代器。

正向迭代器支持以下操作:++pp++*p(假设 p 是一个正向迭代器)。此外,两个正向迭代器可以互相赋值,还可以用 ==!= 运算符进行比较。

  1. 双向迭代器

双向迭代器除了正向迭代器的所有功能以外还具有 -- 操作,可以朝相反方向移动。

  1. 随机访问迭代器

除了双向迭代器的所有功能以外,随机访问迭代器还具备一下操作:

  • p+=i:使 p 往后移动 i 个元素。
  • p-=i:使 p 往前移动 i 个元素。
  • p+i:返回 p 后面第 i 个元素的迭代器。
  • p-i:返回 p 前面第 i 个元素的迭代器。
  • p[i]:返回 p 后面第 i 个元素的引用。

除此之外,随机访问迭代器还具备<、>、<=、>= 操作,两个随机访问迭代器可以通过这些操作进行比较。

对于两个随机访问迭代器 p1、p2,p2-p1 返回 p2 所指向元素和 p1 所指向元素的序号之差(或者说 p2 和 p1 之间的元素个数减一)。

不同容器的迭代器类型:

容器 迭代器功能
vector 随机访问
deque 随机访问
list 双向
set / multiset 双向
map / multimap 双向
stack 不支持迭代器
queue 不支持迭代器
priority_queue 不支持迭代器

迭代器的遍历

  1. 随机访问迭代器,以 vector 举例:
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, const char * argv[]) {

    vector<int> v;              // 定义一个 int 类型的可变长数组
    for (int i=0; i<10; ++i) {
        v.push_back(i);         // push_back 在 vector 容器尾部添加元素
    }

    // 1. 使用下标遍历
    for (int i=0; i<v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << endl;

    // 2. 使用 != 条件遍历
    vector<int>::iterator iter;
    for (iter = v.begin(); iter != v.end(); ++iter) {
        cout << *iter << " ";
    }
    cout << endl;

    // 3. 使用 < 条件遍历
    for (iter = v.begin(); iter < v.end(); ++iter) {
        cout << *iter << " ";
    }
    cout << endl;

    // 4. 随机访问达到间隔输出
    iter = v.begin();
    while (iter < v.end()) {
        cout << *iter << " ";
        iter += 2;
    }
    cout << endl;

    return 0;
}

程序输出:

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
0 2 4 6 8
  1. 双向迭代器遍历,以 list 为例:
#include <iostream>
#include <list>
using namespace std;

int main(int argc, const char * argv[]) {
    list<int> my_list;              // 定义一个 int 类型的 List
    for (int i=0; i<10; ++i) {
        my_list.push_back(i);       // 往 list 里面添加元素
    }

    // 正确的遍历方法
    list<int>::iterator iter;
    for (iter = my_list.begin(); iter != my_list.end(); ++iter) {
        cout << *iter << " ";
    }
    cout << endl;

    // 错误的遍历,双向迭代器不支持 < 操作
    for (iter = my_list.begin(); iter < my_list.end(); ++iter) {
        cout << *iter << " ";
    }
    cout << endl;

    // 下面的遍历也是错误的,双向迭代器不支持下标访问
    for (int i=0; i<my_list.size(); ++i) {
        cout << my_list[i];
    }
    cout << endl;

    return 0;
}

迭代器算法

STL 中有用于操作迭代器的三个函数模板,分别是:

  • advance(p, n):使迭代器 p 向前或向后移动 n 个元素。
  • distance(p, q):计算两个迭代器之间的距离,即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面,则这个函数会陷入死循环。
  • iter_swap(p, q):用于交换两个迭代器 p、q 指向的值。

要使用上面三个函数,需要包含 algorithm 头文件。

示例:

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    int a[4] = {1, 2, 3, 4};
    list<int> my_list(a, a+4);  // 使用数组初始化一个 list
    list<int>::iterator iter = my_list.begin();

    advance(iter, 2);   // 向后移动两个元素 == 3
    cout << *iter << endl;

    advance(iter, -1);  // 向前移动一个元素 == 2
    cout << *iter << endl;

    list<int>::iterator iter_end = my_list.end();
    iter_end--;  // 注意 -- 操作之后才指向最后一个元素 == 4

    cout << "distance(2, 4): " << distance(iter, iter_end) << endl;

    cout << "iter: " << *iter << ", iter_end: " << *iter_end << endl;
    iter_swap(iter, iter_end);  // 交换两个迭代器的值
    cout << "iter: " << *iter << ", iter_end: " << *iter_end << endl;

    return 0;
}

输出结果:

3
2
distance(2, 4): 2
iter: 2, iter_end: 4
iter: 4, iter_end: 2
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注