диапазон для цикла (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 (или -std=c++0x с GCC < 4.7) работает примерно 13,8 секунд на моем компьютере.

Если изменить функцию main, чтобы использовать диапазон на основе цикл:

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

среда выполнения увеличивается до 29,8 секунд. Кстати, эта продолжительность ~ 30 секунд почти такая же, как время выполнения оригинала при использовании std::vector<double> вместо std::array<double, N>, что заставило меня поверить, что компилятор не может развернуть код, созданный циклом, основанным на диапазоне.

Есть ли способ иметь скорость оригинала и все еще использовать диапазоны для петель?

---

Что я пробовал:

я могу получить желаемую скорость с диапазона на основе цикл, изменив две функции члена в NumericRange:

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; 
} 

Однако , этот код плохо работает, потому что != operator не работает должным образом. Обычно для числовых операций я использую < для завершения работы op, а не ==. Я думал о том, чтобы найти первое значение вне диапазона, но для этого аналитически может не дать точного ответа из-за численной ошибки.

Как вы можете заставить != operator вести себя аналогично <, не вводя в заблуждение других, кто увидит мой код? Я бы просто сделал функции begin() и end() частным, но они должны быть общедоступными для цикла, основанного на диапазоне.

Большое спасибо за помощь.

Answer 1

Проблема, насколько мне известно, заключается в том, что вы не используете конструкцию range-for соответствующим образом.

---

Давайте сделаем шаг назад:

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

Обратите внимание, как диапазон-за итерацию по вектору для извлечения целые.

---

По некоторым причинам вы решили не реализовывать итераторы мост от 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, поскольку это ложная итерация в некотором роде; вы не можете попасть в объект диапазона, чтобы изменить его через итератор.

EDIT:operator== слишком медленный, как его улучшить?

Предлагаю обмануть.

1/Изменить конструкторы итератора

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

2/Tweak итерацию, чтобы создать новый "дозорный" значение в конце

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 равно нуля, а другие нет. Только при последнем вызове на самом деле происходит сравнение двух атрибутов _state.