使用迭代器实现算法

迭代器通常根据指向位置的移动，来遍历容器中的元素，但不需要迭代对应的数据类型。迭代器也会被用来实现算法，其可以通过++it指向下一个元素，并且通过*it解引用得到对应的值。

本节中，我们将用迭代器来实现斐波那契函数。斐波那契函数会有类似如下的迭代：F(n) = F(n - 1) + F(n - 2)。数列的初始值F(0) = 0和 F(1) = 1。这样下列序列就可以进行计算：

  • F(0) = 0
  • F(1) = 1
  • F(2) = F(1) + F(0) = 1
  • F(3) = F(2) + F(1) = 2
  • F(4) = F(3) + F(2) = 3
  • F(5) = F(4) + F(3) = 5
  • F(6) = F(5) + F(4) = 8
  • …

我们要实现一个函数，可以输出斐波那契第n个数的值。通常我们都会使用函数迭代，或者是循环来实现这个函数。这样的话，我们只能一个个的将相应的值算出来，然后才能计算出下一个值。这里我们有两个选择——递归调用斐波那契函数计算整个数列，这样很浪费计算时间，或者将最后两个斐波那契数作为临时变量，并用它们来计算下一个数。第二种方法我们需要重新实现斐波那契算法循环。这样我们就可以将斐波那契数列计算的代码和我们实际的代码放在一起：

  1. size_ta{0};
  2. size_tb{1};
  3. for(size_ti{0};i< N;++i){
  4.     constsize_told_b{b};
  5.     b+=a;
  6.     a=old_b;
  7.     // do something with b, which is the current fibonacci number
  8. }

使用迭代器实现斐波那契数列是一件很有意思的事情。如何将循环中的迭代，使用迭代器的前向自加操作来代替呢？其实很简单，让我们来看一下。

How to do it…

本节中，我们主要关注如何用一个迭代器实现生成斐波那契数列。

  1. 为了打印斐波那契数列在终端，我们需要包含标准输入输出流头文件。

    1. #include <iostream>

  2. 我们调用斐波那契迭代器——fibit。其会指向一个值i，其保存的值为斐波那契数列对应的位置，a和b保存斐波那契数列中最后两个值。实例化迭代器时，需要将斐波那契迭代器初始化为F(0)的值：

    1. class fibit
    2. {
    3.     size_t i {0};
    4.     size_t a {0};
    5.     size_t b {1};

  3. 下一步，定义标准构造函数和另一个构造函数用来初始化迭代器。

    1. public:
    2.     fibit() = default;
    3.     explicit fibit(size_t i_)
    4.         : i{i_}
    5.     {}

  4. 当我们对迭代器解引用时，迭代器将返回对应位置的数值。

    1.     size_t operator*() const { return b; }

  5. 当移动迭代器++时，其会移动到下一个斐波那契数上。这里的实现与基于循环的实现几乎是一样的。

    1.     fibit& operator++() {
    2.         const size_t old_b {b};
    3.         b += a;
    4.         a = old_b;
    5.         ++i;
    6.         return *this;
    7.     }

  6. 当使用循环时，增加后的迭代器将会和end迭代器进行比较，所以这里需要为迭代器实现不等于!=操作符。我们只比较当且迭代器所对应的步数，这比循环1000000次再结束迭代器简单许多，这样我们就不需要计算太多的斐波那契数：

    1.     bool operator!=(const fibit &o) const { return i != o.i; }
    2. };

  7. 为了能让斐波那契迭代器适应for循环的范围写法，我们需要实现一个范围类。我们称这个类为fib_range，其构造函数只需要一个参数，这个参数能够告诉我们我们想要遍历的范围：

    1. class fib_range
    2. {
    3.     size_t end_n;
    4. public:
    5.     fib_range(size_t end_n_)
    6.         : end_n{end_n_}
    7.     {}

  8. begin和end函数将会返回对应位置上的迭代器，也就是F(0)和F(end_n)对应的迭代器。

    1.     fibit begin() const { return fibit{}; }
    2.     fibit end() const { return fibit{end_n}; }
    3. };

  9. 好了，其他与迭代器相关的代码我们就不管了。因为我们辅助类就能很好的帮助我们将这些细节的东西隐藏掉！让我们打印10个斐波那契数字：

    1. int main()
    2. {
    3.     for (size_t i : fib_range(10)) {
    4.            std::cout << i << ", ";
    5.     }
    6.     std::cout << '\n';
    7. }

  10. 编译运行后，我们会在终端上看到如下的打印：

    1. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

There’s more…

为了兼容STL中的迭代器，这里实现的迭代器必须支持std::iterator_traits类。想要知道怎么做，要参考一下3.2节(让自己的迭代器与STL的迭代器兼容)，其对如何兼容进行了明确地说明。

Note：

试着从迭代器的角度思考，这样的代码在很多情况下就显得十分优雅。不用担心性能，编译器会根据模板对迭代器相关的代码进行优化。

为了保证例子的简洁性，我们并没有对其做任何事情，不过要是作为斐波那契迭代器的发布库的话，其可用性还是比较差的——fibit传入一个参数的构造函数，可以直接使用end迭代器替换，因为fibit并没有包含任何一个合法的斐波那契值，这里的库并不强制使用这种方式。

还有些方面需要进行修复：

  • 将fibit(size_t i_)声明为私有构造函数，并在fibit类中将fib_range类声明为一个友元类。这样用户就只能使用正确的方式进行迭代了。

  • 可以使用迭代器哨兵，避免用户引用end迭代器。可以参考一下3.6节(使用哨兵终止迭代)中内容，以获得更多信息。