demonstrate 的 blog

iterator 说起来简单，写起来却不是那么容易的事情。STL 的 iterator 给了我们很方便的使用经历，却没有给我们太多的扩展空间。这正是 boost.iterator 设计的初衷。

iterator 有几个和 STL 的 iterator 不同的地方。我们先看看有些啥 concepts。很重要的一点是 boost 区分了 access 和 traversal 两种正交的行为：

• access 包括 Readable（iterator_traits<some_iterator>::type、operator* 和 operator->）、Writable（operator* 返回的可以赋值）、Swappable（可以用 iter_swap 交换）、Lvalue（operator* 返回引用）。
• traversal 包括 Incrementable（是 Assignable、Copy Construtible；定义了 ++、iterator_traversal<some_iterator>::type 能够被转换成为 incrementable_traversal_tag）、Single-pass（是 Incrementable 和 Equaty Comparable）、ForwardTraversal（是 DefaultConstructible、Single-pass）、Bidirectional（是 Forward 且定义了 –）；RandomAccessTraversal（Bidirectional 且定义了 operator+=、operator-=、operator+ 和 operator-，各种比较与 operator[]）。

为了给各种复杂的 iterator 提供统一简洁的接口，boost.iterator 提供了 iterator facade 和 iterator adaptor。

• 利用 iterator_facade 有几个 template 的参数，第一个（由于使用了 CRTP）是 iterator 类自己，第二个是 value_type 即容器的 value_type，第三个是类型即前面提到的哪种 traversal 类型，第四个和第五个往往能自动推断出来，对应的是引用类型和 iterator 差的类型。然后根据选择的类型实现对应的方法（一般都是 private 里面对应的什么 increment 啊什么的），这些函数简化了具体到 iterator 的接口（因为不同的 iterator 可能需要实现很多方法），主要的方法有 dereference、increment、decrement 和 advance。实现 const interator 可以借用已经写好的 iterator，注意在 iterator_facade 第二个参数后面加上 const。如果是模版容器，最后一般通过一个 typedef 将 iterator 的名字简化。
• 某些情况下可能已经存在了类似 iterator 的东西，我们可以用 iterator_adaptor 将其行为弄成一个标准的 iterator，这往往更加简单。过程和上面类似。

除此以外，boost.iterator 还提供了一些非常有用的 iterator：

• counting_iterator 可以用来数数，比如初始化某些容器；
• filter_iterator 以及提供的 helper 函数 make_filter_iterator 用于产生 filtering 的 iterator；
• function_output_iterator 以及提供的 helper 函数 make_function_output_iterator 可以将某个 functor 反复作用在 dereferenced iterator 上。
• indirect_iterator 用于将一个 pointer 的 iterator 直接转换成为 pointer 指向的对象；
• permutation_iterator 以及 help 函数 make_permutation_iterator 用于通过某种给定的 permutation 次序访问原来容器里面的数据；
• reverse_iterator 与 helper 函数 make_reverse_iterator 用于反向遍历，可以看成 permutation iterator 的特例；
• shared_container_iterator 及其 helper 函数 make_shared_container_iterator 产生的 iterator 与 container 通过 shared_ptr 实现自动释放 container，一旦所有的 iterator 被释放掉。
• transform_iterator 及其 helper 函数 make_transform_iterator 将一个 functor 作用在另一个 dereferenced iterator 上获得的值作为新的 iterator 的 dereference 值；
• zip_iterator 及其 helper 函数 make_zip_iterator 将两个 iterator 绑定在一起产生一个新的 iterator。不知道这个 iterator 那个不能和 std::sort 一起用的 bug 被 fix 掉没有。

下面是一段简单的程序

#include <boost/iterator/permutation_iterator.hpp>
#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/io.hpp>
#include <iostream>
#include <iterator>
#include <algorithm>
namespace bnu = boost::numeric::ublas ;

const int N = 5 ;

typedef boost::permutation_iterator<bnu::vector<int>::iterator,
                                    bnu::vector<int>::iterator> perm_type ;

int
main( int argc, char* argv[] ) {
  bnu::vector<int> v( N ) ;
  bnu::vector<int> u( N ) ;
  for( int i = 0 ; i < N ; ++ i ) {
    v(i) = i;
    u(i) = N - i - 1 ;
  }

  std::cout << "v: " << v << std::endl ;
  std::cout << "u: " << u << std::endl ;

  perm_type begin = boost::make_permutation_iterator( v.begin(), u.begin() ) ;
  perm_type end   = boost::make_permutation_iterator( v.end(),   u.end() ) ;

  std::copy( begin, end, std::ostream_iterator<int>( std::cout, " ") ) ;
  std::cout << std::endl ;

  std::copy( begin, end, v.begin() ) ;
  std::cout << "v: " << v << std::endl ;

  return 0 ;
}

——————
And in process of time it came to pass, that Cain brought of the fruit of the ground an offering to the LORD.