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 正在接受审查。

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

std::algorithms friendly way to iterate over `std::vector<std::vector<something>>`

c++

algorithm

stl

vector