关于c++17:浅谈如何实现自定义的-iterator

在 C++17 之前，实现自定义的迭代器被举荐采纳从 std::iterator 派生的形式。

Std::iterator 具备这样的定义：

template<
    class Category,
    class T,
    class Distance = std::ptrdiff_t,
    class Pointer = T*,
    class Reference = T&
> struct iterator;

其中，T 是你的容器类类型，无需多提。而 Category 是必须首先指定的所谓的 迭代器标签，参考这里。Category 次要能够是：

input_iterator_tag：输出迭代器
output_iterator_tag：输入迭代器
forward_iterator_tag：前向迭代器
bidirectional_iterator_tag：双向迭代器
random_access_iterator_tag：随机拜访迭代器
contiguous_iterator_tag：间断迭代器

这些标签看起来仿佛相当莫名其妙，好像我晓得它们的用意，但实际上却又难以明确，难以筛选。

上面粗略地对它们及其关联实体进行个性上的介绍，以帮忙你了解。

这些 tags 实际上绑定关联着一些同名实体类如 input_iterator 等等，通过模板特化技术别离实现专有的 distance() 和 advance()，以达到特定的迭代优化成果。

`input_iterator_tag`

input_iterator_tag 能够包装函数的输入——以用作它人的输出流。所以它是仅可递增的（只能 +1），你不能对它 +n，只能通过循环 n 次递增来模仿相应的成果。input_iterator 无奈递加（-1），因为输出流没有这样的个性。它的迭代器值（*it）是只读的，你不能对其置值。

但 output_iterator_tag，forward_iterator_tag 的迭代器值是可读写的。可读写的迭代器值是指：

std::list<int> l{1,2,3};
auto it = l.begin();
++it;
(*it) = 5; // <- set value back into the container pointed by iterator

input_iterator 将容器出现为一个输出流，你能够通过 input_iterator 接管输出数据流。

`output_iterator_tag`

output_iterator_tag 很少被用户间接应用，它通常和 back_insert_iterator/ front_insert_iterator/ insert_iterator 以及 ostream_iterator 等配合应用。

output_iterator 没有 ++/– 能力。你能够向 output_iterator 指向的容器中写入 / 置入新值，仅此而已。

如果你有输入流款式的出现需要，能够抉择它。

`forward_iterator_tag`

forward_iterator_tag 示意前向迭代器，所以只能增量，不能回退，它继承 input_iterator_tag 的所有根本能力，但又有所加强，例如容许设置值。

从能力上说，input_iterator 反对读取 / 设置值，也反对递增行走，不反对递加行走（须要模仿，低效），+n 须要用循环模仿故而低效，但如果你的容器只有这样的外露的需要，那么 forward_iterator_tag 就是最佳抉择。

从实践上来说，反对 forward_iterator_tag 的迭代器必须至多实现 begin/end。

`bidirectional_iterator_tag`

bidirectional_iterator_tag 的关联实体 bidirectional_iterator 是双向可行走的，既能够 it++ 也能够 it--，例如 std::list。如同 forward_iterator_tag 一样，bidirectional_iterator_tag 不能间接 +n（和 -n），所以 +n 须要一个特化的 advance 函数来循环 n 次，每次 +1（即通过循环 n 次递增或递加来模仿）。

从实践上来说，反对 bidirectional_iterator_tag 的迭代器必须同时实现 begin/end 以及 rbegin/rend。

`random_access_iterator_tag`

random_access_iterator_tag 示意的随机拜访迭代器，random_access_iterator 反对读取 / 设置值，反对递增递加，反对 +n/-n。

因为 random_access_iterator 反对高效的 +n/-n，这也意味着它容许高效的间接定位，这种迭代器的所属容器，通常也顺便反对 operator [] 下标存取，如同 std::vector 那样。

`contiguous_iterator_tag`

contiguous_iterator_tag 在 C++17 中开始引入，然而编译器们的反对力度有问题，所以目前咱们不能对其进行具体介绍，对于实作来说不用思考它的存在。

一个定制迭代器须要抉择一个迭代器标签，也就是抉择迭代器的反对能力汇合。上面是一个示例：

namespace customized_iterators {
  template<long FROM, long TO>
  class Range {
    public:
    // member typedefs provided through inheriting from std::iterator
    class iterator : public std::iterator<std::forward_iterator_tag, // iterator_category
    long,                      // value_type
    long,                      // difference_type
    const long *,              // pointer
    const long &               // reference
      > {
      long num = FROM;

      public:
      iterator(long _num = 0)
        : num(_num) {}
      iterator &operator++() {
        num = TO >= FROM ? num + 1 : num - 1;
        return *this;
      }
      iterator operator++(int) {
        iterator ret_val = *this;
        ++(*this);
        return ret_val;
      }
      bool operator==(iterator other) const {return num == other.num;}
      bool operator!=(iterator other) const {return !(*this == other); }
      long operator*() { return num;}
    };
    iterator begin() { return FROM;}
    iterator end() { return TO >= FROM ? TO + 1 : TO - 1;}
  };

  void test_range() {
    Range<5, 13> r;
    for (auto v : r) std::cout << v << ',';
    std::cout << '\n';
  }

}

这个示例的原型来自于 cppreference 上 std::iterator 及其原作者，略有批改。

专门独立一个大节，因为发现垃圾教程太多了。

自增自减的运算符重载分为前缀后缀两种模式，前缀形式 返回援用 ，后缀形式 返回新正本：

struct X {
  // 前缀自增
  X& operator++() {
    // 实际上的自增在此进行
    return *this; // 以援用返回新值
  }

  // 后缀自增
  X operator++(int) {
    X old = *this; // 复制旧值
    operator++();  // 前缀自增
    return old;    // 返回旧值
  }

  // 前缀自减
  X& operator--() {
    // 实际上的自减在此进行
    return *this; // 以援用返回新值
  }

  // 后缀自减
  X operator--(int) {
    X old = *this; // 复制旧值
    operator--();  // 前缀自减
    return old;    // 返回旧值
  }
};

或者去查看 cppreference 的文档以及文档，别去看那些教程了，找不出两个正确的。

正确的编码是实现一个前缀重载，而后基于它实现后缀重载：

struct incr {int val{};
  incr &operator++() {
    val++;
    return *this;
  }
  incr operator++(int d) {
    incr ret_val = *this;
    ++(*this);
    return ret_val;
  }
};

如果有必要，你可能须要实现 operator= 或者 X(X const& o) 拷贝构造函数。但对于 简略平庸 struct 来说能够省略（如果你不能确定主动内存拷贝是否被提供，思考查看汇编代码，或者罗唆显式实现 operator= 或者 X(X const& o) 拷贝构造函数）

但从 C++17 起 std::iterator 被弃用了。

如果你真的很关怀流言飞语，能够去这里看看无关的探讨。

在少数状况下，你依然能够应用 std::iterator 来简化代码编写，但这一个性以及晚期的迭代器标签、类别等等概念曾经过期。

所以在从 C++17 开始的新时代，自定义迭代器原则上临时只有手写。

namespace customized_iterators {
  namespace manually {
    template<long FROM, long TO>
    class Range {
      public:
      class iterator {
        long num = FROM;

        public:
        iterator(long _num = 0)
          : num(_num) {}
        iterator &operator++() {
          num = TO >= FROM ? num + 1 : num - 1;
          return *this;
        }
        iterator operator++(int) {
          iterator ret_val = *this;
          ++(*this);
          return ret_val;
        }
        bool operator==(iterator other) const {return num == other.num;}
        bool operator!=(iterator other) const {return !(*this == other); }
        long operator*() { return num;}
        // iterator traits
        using difference_type = long;
        using value_type = long;
        using pointer = const long *;
        using reference = const long &;
        using iterator_category = std::forward_iterator_tag;
      };
      iterator begin() { return FROM;}
      iterator end() { return TO >= FROM ? TO + 1 : TO - 1;}
    };
  } // namespace manually

  void test_range() {
    manually::Range<5, 13> r;
    for (auto v : r) std::cout << v << ',';
    std::cout << '\n';
  }

}

示例中的 iterator traits 局部不是必须的，你齐全能够不用反对它们。

齐全手写迭代器的注意事项包含：

begin() 和 end()
迭代器嵌入类（不用被限定为嵌入），至多实现：
1. 递增运算符重载，以便行走
2. 递加运算符重载，如果是双向行走（bidirectional_iterator_tag）或随机行走（random_access_iterator_tag）
3. operator* 运算法重载，以便迭代器求值
4. operator!= 运算符重载，以便计算迭代范畴；必要时也能够显式重载 operator==（默认时编译器主动从 != 运算符上生成一个配套替代品）

如果你编码对迭代范畴进行了反对，那么就能够应用 for 范畴循环：

your_collection coll;
for(auto &v: coll) {std::cout << v << '\n';}

对于 for 范畴循环的展开式，能够查看这里。

在 C++20 之后，迭代器产生了微小的变动。但因为它的工程实作还早的很，所以本文中暂且不予探讨。

为了代码标准和安全性，getter 通常一次提供两个，可写的和不可写的：

struct incr {int &val(){return _val;}
  int const &val() const { return _val;}
  private:
  int _val{};}

同样的情理，迭代器的 begin() 和 end() 也至多要提供 const 和非 const 的两种版本。一般来说你能够通过独立实现来帮忙提供多套版本：

struct XXX {
  
  // ... struct leveled_iter_data {//    static leveled_iter_data begin(NodePtr root_) {...}
  //.   static leveled_iter_data end(NodePtr root_) {...}
  // }
  
  using iterator = leveled_iter_data;
  using const_iterator = const iterator;
  iterator begin() { return iterator::begin(this); }
  const_iterator begin() const { return const_iterator::begin(this); }
  iterator end() { return iterator::end(this); }
  const_iterator end() const { return const_iterator::end(this); }

}

这是不费脑子的一种形式，读写安全性被束缚在 XXX 之内：owner 当然可能明确哪些应该可被裸露，哪些须要临时束缚裸露进去的能力。

除了 iterator 和 const_iterator 之外，rbegin/rend, cbegin/cend 等也能够思考被实现。

迭代器的应用肯定要留神 随用随取 的准则。

void test_iter_invalidate() {std::vector<int> vi{3, 7};
  auto it = vi.begin();
  it = vi.insert(it, 11);
  vi.insert(it, 5000, 23);
  vi.insert(it, 1, 31);                // crach here!
  std::cout << (*it) << '\n';
  return;
}

在少数 OS 环境中，vi.insert(it, 5000, 23); 语句有极大概率导致 vector 不得不重新分配外部的数组空间，因而该语句执行之后，it 所持有的外部指针就曾经无意义了（it 仍指向旧的缓冲区的某个地位），所以下一行语句持续应用 it 将会导致谬误的指向与写入。因为过期的缓冲区有很大的可能曾经被调度处于缺页状态，所以这个谬误往往会导致 SIGSEGV 致命异样。如果产生了 SIGSEGV 信号，你可能是很侥幸的，反而若是过期的缓冲区尚且无效，那么这一语句可能被执行且不报任何谬误，那才是要命。

stdlib 的容器采纳一种叫做 erase and remove 的习用法来事实上删除一个元素。以 std::list 为例，remove_if() 可能从 list 中找到符合条件的元素，并将他们汇集（收集）起来挪动到 list 的开端，而后返回这组元素中的第一个元素的地位 iter，然而这些元素并未被从 list 中删除，如果你须要去掉他们的话，你须要以 list.erase(iter, list.end()) 来明确地移除它们。

所以删除元素是这样的：

bool IsOdd(int i) {return i & 1;}

std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
v.erase(std::remove_if(v.begin(), v.end(), IsOdd), v.end());

std::list<int> l = {1,100,2,3,10,1,11,-1,12};
l.erase(l.remove_if(IsOdd), l.end());

因为 std::vector 不能像 std::list 那样汇集元素到链表开端，所以它没有 remove_if() 成员函数，故而在它下面做 search & erase 须要 std::remove_if 的参加。而 std::list 能够间接应用成员函数 remove_if 来实现，代码也显得略微简洁一些。

自 C++20 起，erase and remove_if 能够被简化为 std::erase_if() 或 erase_if() 成员函数，例如 std::erase, std::erase_if (std::vector)。

这次的 About customizing your own STL-like iterator 奉献了一些集体了解和最佳实际的准则，然而还有点点意犹未尽。

下回思考是不是介绍一个 tree_t 及其迭代器实现，或者可能更有参考价值。

基于范畴的 for 循环 (C++11 起) – cppreference.com
std::iterator – cppreference.com
std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, std::random_access_iterator_tag, std::contiguous_iterator_tag – cppreference.com
Increment/decrement operators – cppreference.com
operator overloading – cppreference.com
Traversing Trees with Iterators
c++ – How to implement an STL-style iterator and avoid common pitfalls? – Stack Overflow
c++ – Writing your own STL Container – Stack Overflow
STL & Generic Programming: Writing Your Own Iterators – Dr Dobb’s

c++ – How to correctly implement custom iterators and const_iterators? – Stack Overflow

关于c++17:浅谈如何实现自定义的-iterator

实现你本人的迭代器

应用 std::iterator

std::iterator 的根本定义

迭代器标签

`input_iterator_tag`

`output_iterator_tag`

`forward_iterator_tag`

`bidirectional_iterator_tag`

`random_access_iterator_tag`

`contiguous_iterator_tag`

自定义迭代器的实现

自增自减运算符重载

C++17 起

齐全手写迭代器

须要关照到的事件

C++20 之后

其它相干

除了 iterator 还有 const_iterator

注意事项：迭代器的应用

迭代器的搜寻并删除

后记

Refs

Just My Socks（注册教程内含优惠码）

关于c++17:浅谈如何实现自定义的-iterator

实现你本人的迭代器

应用 std::iterator

std::iterator 的根本定义

迭代器标签

input_iterator_tag

output_iterator_tag

forward_iterator_tag

bidirectional_iterator_tag

random_access_iterator_tag

contiguous_iterator_tag

自定义迭代器的实现

自增自减运算符重载

C++17 起

齐全手写迭代器

须要关照到的事件

C++20 之后

其它相干

除了 iterator 还有 const_iterator

注意事项：迭代器的应用

迭代器的搜寻并删除

后记

Refs

Just My Socks（注册教程 内含优惠码）

`input_iterator_tag`

`output_iterator_tag`

`forward_iterator_tag`

`bidirectional_iterator_tag`

`random_access_iterator_tag`

`contiguous_iterator_tag`

Just My Socks（注册教程内含优惠码）