C++ 迭代器介绍

3 分钟阅读

C++ 迭代器介绍

迭代器概念

Iterator(迭代器)是一种”能够迭代某序列内所有元素”的对象，可通过改变自寻常pointer的一致性接口来完成工作。Iterator奉行一个纯抽象概念：任何东西，只要行为类似iterator，就是一种iterator。然而不同的的iterator具有不同的行进能力。

迭代器种类

Output迭代器

Output迭代器允许一步一步前行并搭配write动作。因此你可以一个一个元素地赋值，不能使用output迭代器对同一区间迭代两次。事实上，甚至不保证你可以将一个value复制两次而其迭代器不累进。我们的目标是将一个value以下列形式写入一个黑洞。

while(...) {
  *pos = ...;
  ++pos;
}

通常，迭代器可用来读，也可用来写; 几乎所有reading迭代器都有write的额外功能，这种情况下他们被称为mutable(可产生变化的)迭代器。一个典型的pure output迭代器例子是：”将元素写至标准输出设备”。如果采用两个output迭代器写至屏幕, 第二个字将跟在第一个字后面，而不是覆盖第一个字。另一个典型的例子是inserter, 那是一种用来将他插入容器。如果随后写入第二个value, 并不会覆盖第一个value, 而是安插进去。

Input迭代器

Input迭代器只能读取元素一次。如果你复制input迭代器, 并令原input迭代器和新产生的拷贝都向前读取, 可能会遍历到不同的值。 所有的迭代器都具备input迭代器的能力，而且往往更强。Pure input迭代器的典型例子就是”从标准输入设备读取数据”。同一个值不会被读取两次。一旦从input stream读入一个字(离开input缓冲区), 下次读取时就会返回另一个字。

对于input迭代器, 操作符==和!=只用来检查”某个迭代器是否等于一个past-the-end迭代器(指指向最末元素的下一个位置)”.这有其必要, 因为处理input迭代器的操作函数通常会有以下行为。

InputIterator pos, end;

while (pos != end) {
  ... // read-only access using *pos
  ++pos;
}

没有任何保证说，两个迭代器如果都不是past-the-end迭代器, 且指向不同位置，他们的比较结果会不相等(这个条件是和forward迭代器搭配引入的)。

也请注意, input迭代器的后置式递增操作符(++iter)不一定会返回什么东西。不过通常它会返回旧位置。你应该尽可能优先先选用前置式递增操作符(++iter)而非后置式递增操作符(iter++), 因为前者效能更好。因为后者会返回一个临时对象。

Forward(前向)迭代器

Forward迭代器是一种input迭代器且在前进读取时提供额外保证。

ForwardIterator pos1, pos2;

pos1 = pos2 = begin; /// both iterator refer to the same element
if(pos1 != end) {
  ++pos1; /// pos1 is one element ahead
  while(pos1 != end) {
    if(*pos1 == *pos2) {
      ... // precess adjacent duplicates
      ++pos1;
      ++pos2;
    }
  }
}

Forward迭代器由以下对象和类型提供：

Class
Unordered container 然而标准库也允许unordered容器的实现提供bidirectional迭代器。如果forward迭代器履行了output迭代器应有的条件, 那么它就是一个mutable forward迭代器, 即可用于读取，也可用于涂写。

Bidirectional(双向)迭代器

Bidirectional迭代器在forward迭代器的基础上增加回头迭代(iterate backward)能力。

Bidirectional 迭代器的新增操作 | 表达式 | 效果 | | —— | —————- | | –iter | 步退(返回新位置) | | iter– | 步退(返回旧位置) |

Bidirectional迭代器由以下的对象和类型提供：

Class list<>.
Associative(关联式) 关联式容器提供

如果bidirectional迭代器履行了output迭代器应有的条件, 那么他就是个mutable bidirectional迭代器, 即可用于读取, 也可用于涂写。

Random-Access(随机访问)迭代器

Random-access迭代器在bidirectional迭代器的基础上增加了随机访问能里。因此它必须提供iterator算数运算。也就是说，它能增减某个偏移量、计算距离(difference), 并运用诸如<和>等管理操作符(`relational operator`)进行比较。随机访问迭代器的新增操作: | 表达式 | 效果 | | -------------- | ------------------------------------ | | iter[n] | 访问索引位置为n的元素 | | iter+=n | 前进n个元素(如果n是负数, 则改为回退) | | iter-=n | 回退n个元素(如果n是负数, 则改为前进) | | iter+n | 返回iter之后的第n个元素 | | n+iter | 返回iter之后的第n个元素 | | iter-n | 返回iter之前的第n个元素 | | iter1-iter2 | 返回iter1和iter2之间的距离 | | iter1 < iter2 | 判断iter1是否在iter2之前 | | iter1 > iter2 | 判断iter1是否在iter2之后 | | iter1 <= iter2 | 判断iter1是否不在iter2之后 | | iter1 >= iter2 | 判断iter1是否不在iter2之前 |

Random-access迭代器由以下对象和类型提供:

可随机访问的容器(array、vector、deque)
String(string、wstring)
寻常的C-Style(pointer)

迭代器相关辅助函数

std::advance()

std::advance()可将迭代器的位置增加, 增加的幅度由实参决定, 也就是说它令迭代器一次前进(或后退)多个元素:

#include <iterator>
void advance(InputIterator& pos, Dist n)

令名称为pos的input迭代器前进(或后退)n个元素
对bidirectinal迭代器和random-access迭代器而言, n可为负值, 表示后退
Dist是个template类型。通常它必须是个整数类型, 因为会调用诸如<、++、--等操作, 还要和0做比较。
std::advance()并不检查迭代器是否超过序列的end()(因为迭代器通常不知道其所操作的容器, 因此并无检查)。所以, 调用std::advance()有可能导致不明确行为–因为”对序列尾端调用operator++“是一种未定义的行为。

对于random-access迭代器, 此函数只是简单地调用pos+=n, 因此具有常量复杂度。对于其他任何类型的迭代器, 则调用++pos(或--pos如果n为负值)n次。因此，对于其他任何类型地迭代器, 本函数具有线性复杂度。 如果你希望你的程序可以轻松地更换容器和迭代器种类, 你应该使用std::advance()而不是operator+= 另外, 请注意std::advance()不具有返回值, 而operator+=会返回新位置, 所以后者可作为更大表达式的一部分。

下面是一个std::advance()的实现。

/// 输入迭代器的情况
template <class _InIt, class _Diff>
inline void advance_impl(_InIt& _Where, _Diff _Off, std::input_iterator_tag) {
  /// 检查该偏移量不能为负值
  if (_Off < 0) {
    assert(false && "negative offset in advance");
  }
  /// 使用自增运算符来计算
  for (; 0 < _Off; --_Off) ++_Where;
}

/// 双向迭代器
template <class _BidIt, class _Diff>
inline void advance_impl(_BidIt& _Where, _Diff _Off,
                         std::bidirectional_iterator_tag) {
  /// 使用自增运算符来计算
  for (; 0 < _Off; --_Off) ++_Where;
  /// 如果偏移量为负值则使用自减运算符
  for (; _Off < 0; ++_Off) --_Where;
}

/// 随机访问迭代器
template <class _RanIt, class _Diff>
inline void advance_impl(_RanIt& _Where, _Diff _Off,
                         std::random_access_iterator_tag) {
  /// 使用operator += ，常量复杂度
  _Where += _Off;
}

template <class _InIt, class _Diff>
inline void advance(_InIt& _Where, _Diff _Off) {
  advance_impl(_Where, _Off,
               /// 在萃取迭代器的特性时去掉其const的属性来提高性能
               std::iterator_traits<_Iter>::iterator_category<
                   std::remove_const_t<_InIt>>());
}

std::next()和std::prev()

c++ 提供了两个新增的辅助函数, 允许你前进和后退移动迭代器的位置。

#include <iterator>
ForwardIterator next(ForwardIterator pos)
ForwardIterator next(ForwardIterator pos, Dist n)

导致forward迭代器pos前进或n个位置
如果处理的是bidirectional和random-access迭代器, n可为负值, 导致后退移动
Dist是类型std::iterator_traits<ForwardIterator>::difference_type
其内部将对一个临时对象调用std::advance(pos, n)
注意, std::next()并不检查是否会跨越序列的end()。因此调用者必须自行担保其结果有效。

#include <iterator>
BidirectionalIterator prev(BidirectionalIterator pos)
BidirectionalIterator prev(BidirectionalIterator pos, Dist n)

导致bidirectional迭代器pos后退一个或n个位置
n可为负值, 导致向前移动
Dist是类型std::iterator_traits<ForwardIterator>::difference_type
其内部将对一个临时对象调用std::advance(pos, -n)
注意, std::prev()并不检查是否会跨越序列的begin()。因此调用者必须自行担保其结果有效。

下面写一个简单的实现：

template <class _InIt>
inline _InIt next(
    _InIt _First,
    std::iterator_traits<_InIt>::iterator_category<_InIt> _Off = 1) {
  static_assert(
      std::is_base_of<
          std::input_iterator_tag,
          typename std::iterator_traits<_InIt>::iterator_category>::value,
      "next requires input iterator");

  advance(_First, _Off);
  return (_First);
}

template <class _BidIt>
inline _BidIt prev(
    _BidIt _First,
    std::iterator_traits<_BidIt>::iterator_category<_BidIt> _Off = 1) {
  static_assert(
      std::is_base_of<
          std::bidirectional_iterator_tag,
          typename std::iterator_traits<_BidIt>::iterator_category>::value,
      "prev requires bidirectional iterator");

  advance(_First, -_Off);
  return (_First);
}

std::distance()

std::distance()用来处理两个迭代器之间的距离:

Dist distance(InputIterator pos1, InputIterator pos2)

返回两个input迭代器pos1和pos2之间的距离。
两个迭代器必须指向同一个容器
如果不是random-access迭代器, 则从pos1开始前进必须能够到达pos2, 亦即pos2的位置必须与pos1相同或在其后。
返回类型Dist是类型std::iterator_traits<ForwardIterator>::difference_type

注意：处理两个non-random-access迭代器之间的距离时, 必须十分小心。第一个迭代器所指的元素绝不能在第二个迭代器所指元素之后方, 否则会导致不明确的行为。如果不知道哪个迭代器在前, 你必须先算出两个迭代器分别至容器起点的距离, 在根据这两个距离来判断。

一个简单的实现：

template <typename it>
typename std::iterator_traits<it>::difference_type distance(it from, it to) {
  if constexpr (typename std::iterator_traits<it>::iterator_category() ==
                std::random_access_iterator_tag) {
    /// 随机访问迭代器
    return to - from;
  } else if constexpr (typename std::iterator_traits<it>::iterator_category() ==
                       std::input_iterator_tag) {
    /// input 迭代器
    typename std::iterator_traits<it>::difference_type res = 0;
    for (; from != to; ++from) {
      ++res;
    }
    return res;
  } else {
    static_assert("unknow iterator type.");
  }
}

std::iter_swap()

这个简单的辅助函数用来交换两个迭代器所指的元素值

#include <algorithm>
void iter_swap(ForwardIterator1 pos1, ForwardIterator pos2)

交换迭代器pos1和pos2所指的值
迭代器的类型不必相同, 但其所指的两个值必须可以相互赋值

Twitter Facebook LinkedIn

李建聪

C++ 迭代器介绍

C++ 迭代器介绍

迭代器概念

迭代器种类

Output迭代器

Input迭代器

Forward(前向)迭代器

Bidirectional(双向)迭代器

Random-Access(随机访问)迭代器

迭代器相关辅助函数

std::advance()

std::next()和std::prev()

std::distance()

std::iter_swap()

分享

猜您还喜欢

C++线程知识简介

Issue 规范化建议

C++证明为什么operator==不能用memcmp实现

C++打印结构体的方法