更快的范围循环（C++11）

Question

我有一些代码需要迭代一个（多元）数值范围：

#include <array>
#include <limits>
#include <iostream>
#include <iterator>

template <int N>
class NumericRange : public std::iterator<double, std::input_iterator_tag>
{
public:
  NumericRange() {
    _lower.fill(std::numeric_limits<double>::quiet_NaN());
    _upper.fill(std::numeric_limits<double>::quiet_NaN());
    _delta.fill(std::numeric_limits<double>::quiet_NaN());
  }
  NumericRange(const std::array<double, N> & lower, const std::array<double, N> & upper, const std::array<double, N> & delta):
    _lower(lower), _upper(upper), _delta(delta) {
    _state.fill(std::numeric_limits<double>::quiet_NaN());
  }

  const std::array<double, N> & get_state() const {
    return _state;
  }

  NumericRange<N> begin() const {
    NumericRange<N> result = *this;
    result.start();
    return result;
  }

  NumericRange<N> end() const {
    NumericRange<N> result = *this;
    result._state = _upper;
    return result;
  }

  bool operator !=(const NumericRange<N> & rhs) const {
    return in_range();
    //    return ! (*this == rhs);
  }

  bool operator ==(const NumericRange<N> & rhs) const {
    return _state == rhs._state && _lower == rhs._lower && _upper == rhs._upper && _delta == rhs._delta;
  }

  const NumericRange<N> & operator ++() {
    advance();
    if ( ! in_range() )
      _state = _upper;
    return *this;
  }

  const std::array<double, N> & operator *() const {
    return _state;
  }

  void start() {
    _state = _lower;
  }

  bool in_range(int index_to_advance = N-1) const {
    return ( _state[ index_to_advance ] - _upper[ index_to_advance ] ) < _delta[ index_to_advance ];
  }

  void advance(int index_to_advance = 0) {
    _state[ index_to_advance ] += _delta[ index_to_advance ];
    if ( ! in_range(index_to_advance) ) {
      if (index_to_advance < N-1) {
    // restart index_to_advance
    _state[index_to_advance] = _lower[index_to_advance];

    // carry
    ++index_to_advance;
    advance(index_to_advance);
      }
    }
  }
private:
  std::array<double, N> _lower, _upper, _delta, _state;
};

int main() {
   std::array<double, 7> lower{{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0}};
   std::array<double, 7> upper{{1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0}};
   std::array<double, 7> delta{{0.03, 0.06, 0.03, 0.06, 0.03, 0.06, 0.03}};

  NumericRange<7> nr(lower, upper, delta);
  int c = 0;    
  for (nr.start(); nr.in_range(); nr.advance()) {
    ++c;
  }
  std::cout << "took " << c << " steps" << std::endl;    
  return 0;
}

使用 g++ -std=c++11 -O3 进行编译（或者使用 gcc < 4.7 时的 -std=c++0x）在我的电脑上大约需要13.8秒的时间。

如果我将 main 函数改为使用范围 for 循环：

  for (const std::array<double, 7> & arr : nr) {
    ++c;
  }

运行时间增加到了29.8秒。巧合的是，当我使用std::vector<double>代替std::array<double，N>时，原始代码的运行时间也几乎相同，这让我相信编译器无法展开范围for循环生成的代码。

有没有一种方法可以保持原始速度并仍然使用范围for循环？

---

我尝试过的：

我可以通过更改NumericRange中的两个成员函数来使用范围for循环获取所需的速度：

bool operator !=(const NumericRange<N> & rhs) const {
  return in_range();
  //    return ! (*this == rhs);
}

const NumericRange<N> & operator ++() {
  advance();
  //    if ( ! in_range() )
  //      _state = _upper;
  return *this;
}

然而，这段代码设计得不太好，因为!=运算符的行为不像预期那样。通常情况下，我使用<来终止循环，而不是使用==。我想过找到第一个超出范围的值，但是基于分析的方法可能由于数值误差而不能得到精确答案。

如何让!= 运算符的行为类似于<，而不会给其他人看到我的代码造成误解？我可以将begin()和end()函数设置为私有，但它们需要对基于范围的for循环公开。

非常感谢您的帮助。

- user

---

你的 begin 和 end 实现非常昂贵。 - ildjarn

@ildjarn：这应该不是问题，因为它们只被调用一次。 - Matthieu M.

@KarolyHorvath 那肯定可能是这种情况。我真的想成为一个更好的程序员，但像你这样批评却不提供任何帮助的评论让我感到沮丧。您认为您能否通过解释改进我的代码和设计的方法来提供帮助？ - user

也许这是一个愚蠢的建议，但是你的 end 在每次循环迭代时都会被调用，这会影响性能。 - Asha

@Asha：不，range-for语法保证它只会被调用一次。只是operator++和operator==太耗费资源了。 - Matthieu M.

Answer 1

就我而言，问题在于您没有适当地使用范围 for 结构。

---

让我们退一步：

void foo(std::vector<int> const& v) {
    for (int i: v) {
    }
}

请注意，range-for循环遍历向量以提取整数。

---

由于某些原因，您选择不使用迭代器从begin到end进行桥接，而是重复使用正在迭代的内容的副本，即使它只有非常微小的变化，并且您正在进行大量的额外工作（在副本和检查中）... 注意：std::iterator<double，...>表示operator*应返回double&。 如果您想使用新的习惯用法，则必须符合其期望。

期望是您使用迭代器进行迭代，而不是一遍又一遍地复制原始对象（稍加修改）。这是C++习惯用法。

这意味着您需要将对象分成两半：从要迭代的对象中拆下在迭代过程中不可变的所有内容和在迭代器中修改的内容。

根据我所看到的：

• _lower，_upper和_delta是固定的
• _state是迭代变量

因此，您将会有：

template <typename> class NumericRangeIterator

template <unsigned N> // makes no sense having a negative here
class NumericRange {
public:
    template <typename> friend class NumericRangeIterator;

    typedef NumericRangeIterator<NumericRange> iterator;
    typedef NumericRangeIterator<NumericRange const> const_iterator;

    static unsigned const Size = N;

    // ... constructors

    iterator begin(); // to be defined after NumericRangeIterator
    iterator end();

    const_iterator begin() const;
    const_iterator end() const;

private:
    std::array<double, N> _lower, _upper, _delta;
}; // class NumericRange

template <typename T>
class NumericRangeIterator: public
    std::iterator< std::array<double, T::Size>,
                   std::forward_iterator_tag >
{
public:
    template <unsigned> friend class NumericRange;

    NumericRangeIterator(): _range(0), _state() {}

    NumericRangeIterator& operator++() {
        this->advance();
        return *this;
    }

    NumericRangeIterator operator++(int) {
        NumericRangeIterator tmp(*this);
        ++*this;
        return tmp;
    }

    std::array<double, T::Size> const& operator*() const {
        return _state;
    }

    std::array<double, T::Size> const* operator->() const {
        return _state;
    }

    bool operator==(NumericRangeIterator const& other) const {
        return _state != other._state;
    }

    bool operator!=(NumericRangeIterator const& other) const {
        return !(*this == other);
    }


private:
    NumericRangeIterator(T& t, std::array<double, T::Size> s):
        _range(&t), _state(s) {}

    void advance(unsigned index = T::Size - 1);  // as you did
    void in_range(unsigned index = T::Size - 1); // as you did

    T* _range;
    std::array<double, T::Size> _state;
}; // class NumericRangeIterator


template <unsigned N>
auto NumericRange<N>::begin() -> typename NumericRange<N>::iterator {
    return iterator(*this, _lower);
}

template <unsigned N>
auto NumericRange<N>::end() -> typename NumericRange<N>::iterator {
    return iterator(*this, _upper);
}

有了这一切的设置，你就可以编写如下代码：

for (auto const& state: nr) {
}

在此处，auto将被推断为std::array<double,nr::Size>。

注意：不确定iterator是否有用，可能只有const_iterator有用，因为它是一种虚假的迭代方式；你不能通过迭代器修改范围对象中的内容。

编辑：operator==太慢了，如何改进？

我建议作弊。

1/ 修改迭代器的构造函数

NumericRangeIterator(): _range(0), _state() {}               // sentinel value
NumericRangeIterator(T& t): _range(&t), _state(t._lower) {}

2/ 调整迭代方式，以在末尾创建新的“哨兵”值

void advance() {
    // ...

    if (not this->in_range()) {        // getting out of the iteration ?
       *this = NumericRangeIterator(); // then use the sentinel value
    }
}

3/ 根据需要更改begin和end的定义。

template <unsigned N>
auto NumericRange<N>::begin() -> typename NumericRange<N>::iterator {
    return iterator(*this);
}

template <unsigned N>
auto NumericRange<N>::end() -> typename NumericRange<N>::iterator {
    return iterator();
}

4/ 使用哨兵让==更加相等

bool operator==(NumericRangeIterator const& other) const {
    return _range == other._range and _state == other._state;
}

现在，在整个迭代过程中，==会被短路，因为其中一个_range是null而另一个不是。只有在最后一次调用时，两个_state属性的比较才会实际发生。

- Matthieu M.

---

NumericRange 如何能够访问 NumericRangeIterator 的私有构造函数 NumericRangeIterator(T& t, std::array<double, T::Size> s)？这个友元关系是否应该是相互的？ - ildjarn

@ildjarn：哎呀，确实是这样。我曾经考虑过将构造函数设为公有的，但恐怕我迷失了方向，感谢你发现了这个问题。 - Matthieu M.

@MatthieuM。很好的组织。然而问题仍然存在：使用!=测试迭代器不起作用，因为它需要在结束时完全相同。将!=运算符更改为返回in_range()在19秒内运行，但会误导其他查看代码的人。在++（前缀）运算符中添加一行if（！in_range（））_state = _range- > _upper;与编码的!=运算符配合使用，但需要33秒才能运行。很遗憾没有办法强制范围for循环使用start(); in_range(); advance();而不是迭代器... - user

@Oliver：不幸的是，这与C++中所有迭代使用都相悖（这本身源于使用指针来界定范围）。另一方面，我认为你可以通过引入哨兵来作弊。我发现in_range的实现相对奇怪，因为它只测试数组的一个值：也许当到达结尾时你可以“销毁”迭代器？ - Matthieu M.

@MatthieuM。优雅；但是它仍然需要大约28秒才能运行；我认为问题不在于比较，而是编译器无法展开循环以生成代码。性能与在整个过程中使用“vector”而不是“array”几乎相同（没有边界检查）；数组版本的主要区别在于循环的大小在编译时已知。因此，现在看来，我可以拥有迭代器（和基于范围的循环），但速度会慢2倍... X( - user