反转依赖于 end() 的迭代器

Question

假设我想编写一个双向迭代器，它迭代提供 begin()/end()/rbegin()/rend() 的任何容器的所有非零值.我将不得不重写 operator++() 以跳过它遇到的所有零。为了确保它仍然有效，它必须每次都检查容器的 end() 和 rend()。以下几行内容：

template<class Container, class Iter> 
struct NonZeroIter: public Iter
{
  Container& c;

  using Parent = Iter;
  using Parent::Parent;
  using iterator_category = std::bidirectional_iterator_tag;

  bool is_valid() const { return *(*this) != 0; }
  bool is_end()   const { return *this == c.end(); }
  bool is_rend()  const { return *this == c.rend(); }

  NonZeroIter(Container& _c, const Iter& _it):
    Parent(_it),
    c(_c)
  { if(!is_end() && !is_valid()) ++(*this); }

  NonZeroIter& operator++()
  {
    if(!is_end()){
      do{
        Parent::operator++();
      } while(!is_end() && !is_valid());
    }
    return *this;
  }

  NonZeroIter& operator--()
  {
    if(!is_rend()){
      do{
        Parent::operator--();
      } while(!is_rend() && !is_valid());
    }
    return *this;
  }

  NonZeroIter& operator++(int) { NonZeroIter tmp(*this); ++(*this); return tmp; }
  NonZeroIter& operator--(int) { NonZeroIter tmp(*this); --(*this); return tmp; }

};

现在，我想使用 std::reverse_iterator 创建 NonZeroIter 的反向迭代器，但要做到这一点，我必须在 NonZeroIter 检查时检查 rend() end() 反之亦然。有没有一种很好的方法（如果可能的话避免开销）或者我是否必须编写自己的相应反向迭代器 class?

Answer 1

一种可能的解决方案是使用基本迭代器 class，其中 is_end 和 is_rend 是虚拟抽象函数。

然后创建正向和反向迭代器classes继承自基础class，并根据每个迭代器类型的需要实现is_end和is_rend函数。

Answer 2

而不是 NonZeroIter 显式检查 end() 和 rend()，构造函数应该检查迭代方向并选择开始（begin() 或 rbegin() ) 和结束（end() 或 rend()）。这些可以保存为局部变量并进行检查。

您可以在 operator--() 中检查 "rend"，而不是检查 "begin"（begin() 表示的索引与 rend() - 1 相同）。

标准容器的所有迭代器都基于std::reverse_iterator，因此您可以使用该知识找到_it的方向。

像这样：

template<typename T>
struct is_reverse_iterator : std::false_type {};

template<typename T>
struct is_reverse_iterator<std::reverse_iterator<T>> : std::true_type {};

template<class Container, class Iter> 
struct NonZeroIter: public Iter
{
  using Parent = Iter;
  using Parent::Parent;
  using iterator_category = std::bidirectional_iterator_tag;
private:      
  Parent begin, end;

  bool is_valid() const { return *(*this) != 0; }
  bool is_end()   const { return *this == end; }
  bool is_begin()  const { return *this == begin; }

public:
  NonZeroIter(Container& c, const Iter& _it):
    Parent(_it),
    begin(is_reverse_iterator<Parent> ? c.rbegin() : c.begin()),
    end(is_reverse_iterator<Parent> ? c.rend() : c.end()),
  { if (!is_end() && !is_valid()) ++(*this); }

  NonZeroIter& operator++()
  {
    if (!is_end()){
      do{
        Parent::operator++();
      } while(!is_end() && !is_valid());
    }
    return *this;
  }

  NonZeroIter& operator--()
  {
    // Smallest possible value is begin, but you could also make that begin - 1
    if (!is_begin()){
      do{
        Parent::operator--();
      } while(!is_begin() && !is_valid());
    }
    return *this;
  }

  NonZeroIter& operator++(int) { NonZeroIter tmp(*this); ++(*this); return tmp; }
  NonZeroIter& operator--(int) { NonZeroIter tmp(*this); --(*this); return tmp; }

};

Answer 3

根据@vll 的回答，我得到了以下代码：

// these structs compile-time translate begin,end to rbegin,rend for reverse iters
template<class Container, class Iter>
struct BeginEndIters
{
  using iterator     = Iter;
  static iterator begin(Container& c) { return c.begin(); }
  static iterator end(Container& c) { return c.end(); }
};
template<class Container, class Iter>
struct BeginEndIters<Container, std::reverse_iterator<Iter>>
{
  using iterator     = std::reverse_iterator<Iter>;
  static iterator begin(Container& c) { return c.rbegin(); }
  static iterator end(Container& c) { return c.rend(); }
};

template<class Container, class Iter>
struct NonZeroIter: public Iter
{
  Container& c;

  // this is the main change
  using BeginEnd = BeginEndIters<Container, Iter>;
  // ^^^^^^^^^^^

  using Parent = Iter;
  using Parent::Parent;
  using iterator_category = std::bidirectional_iterator_tag;

  bool is_valid() const { return *(*this) != 0; }
  bool is_end()   const { return *this == BeginEnd::end(c); }
  bool is_past_begin()  const { return *this == std::prev(BeginEnd::begin(c)); }

  NonZeroIter(Container& _c, const Iter& _it):
    Parent(_it),
    c(_c)
  { if(!is_end() && !is_valid()) ++(*this); }

  NonZeroIter& operator++()
  {
    if(!is_end()){
      do{
        Parent::operator++();
      } while(!is_end() && !is_valid());
    }
    return *this;
  }

  NonZeroIter& operator--()
  { 
    if(!is_past_begin()){
      do{
        Parent::operator--();
      } while(!is_past_begin() && !is_valid());
    }
    return *this;
  }

  NonZeroIter& operator++(int) { NonZeroIter tmp(*this); ++(*this); return tmp; }
  NonZeroIter& operator--(int) { NonZeroIter tmp(*this); --(*this); return tmp; }  
};

反转依赖于 end() 的迭代器

reversing an iterator that depends on end()

c++

iterator

reverse-iterator