c++ - std::algorithms 迭代 `std::vector<std::vector<something>>` 的友好方式

Question

我当前项目中的一个常见模式是这样的:

for(auto& row: matrix)
{
    for(auto& col: row)
    {
        //insert simple operation here:
        //return when condition is true
        //increase counter when condition is true
        //etc
    }
}

如您所见，条件将完全适合某些 std::algorithm，但我真的不知道如何迭代此结构。因此，大多数简单的事情，比如计算条件为真的元素，都有几行而不是一行。

能否请您建议我一种定义类似矩阵的数据结构的方法，使其更易于与 std::algorithms 一起使用？

Answer 1

boost有办法将多个范围合并为一个范围。

如果您不能使用 boost ，你可以这样写:

template<class Iterator>
struct Range {
  Iterator b_, e_;
  Range( Iterator b, Iterator e ):b_(b), e_(e) {}
  Iterator begin() const { return b_; }
  Iterator end() const { return e_; }
  bool empty() const { return begin() == end(); }
  template<class C>
  static auto adl_begin(C&& c) {
    using std::begin;
    return begin( std::forward<C>(c) );
  }
  template<class C>
  static auto adl_end(C&& c) {
    using std::end;
    return end( std::forward<C>(c) );
  }
  template<class C>
  explicit Range(C&& c):
    Range(adl_begin(std::forward<C>(c)), adl_end(std::forward<C>(c)))
  {}
  Range():b_(), e_() {}; // Range of pointers should be null null just in case
  Range( Range const& ) = default;
  Range( Range && ) = default;
  ~Range() = default;
  Range& operator=(Range const&)=default;
  Range& operator=(Range &&)=default;

  friend bool operator==( Range const& lhs, Range const& rhs ) {
    return lhs.b_ == rhs.b_ && lhs.e_ == rhs.e_;
  }
  friend bool operator!=( Range const& lhs, Range const& rhs ) {
    return !( lhs == rhs );
  }
};

上面是一个非常简单的 Range使您可以将成对的迭代器存储在一个包中的模板，该包可以被迭代并被视为一个单元。 boost也有其中之一，可能写得更好。

接下来，一个遍历两个嵌套范围的迭代器:

template<class Outer, class Inner>
struct bi_iterator:std::iterator<
  std::forward_iterator_tag,
  typename std::iterator_traits<Inner>::value_type
  // in theory add more, but I won't bother
> {
  using value_type = typename std::iterator_traits<Inner>::value_type;
  Range<Outer> outer;
  Range<Inner> inner;
  explicit bi_iterator( Range<Outer> out ):outer(out), inner(advance())
  {}
  friend bool operator==( bi_iterator const& lhs, bi_iterator const& rhs ) {
    if (lhs.outer != rhs.outer) return false;
    if (lhs.outer.empty()) return true;
    return lhs.inner == rhs.inner;
  }
  friend bool operator!=( bi_iterator const& lhs, bi_iterator const& rhs ) {
    return !(lhs==rhs);
  }
private:
  Range<Inner> advance() {
    if (outer.empty()) return;
    inner = Range<Inner>( *outer.begin() );
    rectify();
    return inner;
  }
  void rectify() {
    if (!inner.empty()) return;
    if (outer.empty()) return;
    outer = {std::next(outer.begin()), outer.end()};
    inner = advance();
  }
public:
  value_type& operator*() { return *inner.begin(); }
  bi_iterator operator++(int) {
    bi_iterator retval = *this;
    ++(*this);
    return retval;
  }
  bi_iterator& operator++() {
    inner = { std::next(inner.begin()), inner.end() };
    rectify();
    return *this;
  };
};
template<class Outer, class Inner>
Range<bi_iterator<Outer,Inner>> bi_range_helper( Range<Outer> out ) {
  return { bi_iterator<Outer,Inner>(out), bi_iterator<Outer,Inner>({out.end(), out.end()}) };
}
template<class Container>
auto bi_range( Container&& c ) {
  using std::begin; using std::end;
  auto b = begin(c);
  auto e = end(c);
  using Outer = decltype(b);
  using Inner = typename std::decay<decltype(begin(*b))>::type;
  return bi_range_helper<Outer,Inner>( {b,e} );
}

然后:

auto bi = bi_range( matrix );
for( auto&& element: bi ) { /* stuff */ }

应该遍历 matrix 的第二个维度, 和

using std::begin; using std::end;
auto b = begin(bi);
auto e = end(bi);

应该是一些<algorithms>兼容的前向迭代器到矩阵的二维元素中。

请注意，上面可能存在一些错误，我是在没有任何测试甚至编译的情况下编写的。

(另外:始终在 ADL 兼容上下文中使用 std::begin 和 std::end，因此使用 using std::begin 子句)。

如果你让上面的工作正常，一个有趣的项目:make nary_iterator构建递归 bi_iterator链接任意深度的类型。对于高级问题，不用链接就可以解决 bi_iterator .

请注意我的 bi_iterator在很多方面都会不如增强版(我忘了它叫什么)，因为我刚刚把它拿出来了，boost接受审查。