0

假设我想编写一个双向迭代器，它迭代任何提供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; }

};

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

4

3 回答 3

3

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

operator--()您可以检查“begin”，而不是检查“rend” （由 表示的索引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; }

};
于 2020-02-05T13:41:22.117 回答
1

根据@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; }  
};
于 2020-02-05T17:41:07.637 回答
0

一种可能的解决方案是拥有一个基迭代器类，其中is_end和is_rend是虚拟抽象函数。

然后创建从基类继承的正向和反向迭代器类，并根据每个迭代器类型的需要实现is_end和is_rend功能。

于 2020-02-05T13:09:52.710 回答