...

пятница, 14 августа 2015 г.

[Из песочницы] Упрощаем for-цикл по индексам: range-based версия

Волею судеб мне довелось заняться одной задачей автоматизации при помощи Python-скрипта. Изучая базовые конструкции, наибольший интерес у меня вызвал следующий код:
for index in range(0,10) :
  do_stuff()


Удобно, читаемо, лаконично (модно, стильно, молодежно)! Почему бы не организовать такой же цикл в С++? Что из этого вышло — под катом.

Попытка первая — макросы


О недостатках макросов написано много. И главное правило гласит: «Если можно что-то реализовать не используя макросы — так и сделай». Но иногда использование макросов вполне оправданно.
Макросы часто используют для расширения языка нестандартными конструкциями — например, чтобы ввести ключевое слово вечного цикла для большей читаемости кода:
#define infinite_loop while(true)
infinite_loop 
{
  do_stuff();
}


Кстати, мы ведь тоже задались вопросом реализации нестандартного цикла. Что если попробовать реализовать это дело с помощью макросов. Примерно вот так:
#include <iostream>

#define ranged_for(var, min, max, step) for(auto var = (min); var < (max); var += (step) )
int main()
{
  ranged_for(i, 0, 10, 1) 
  {
    std::cout << i << std::endl;
  }
  return 0;
}


Конечно такой код свою задачу выполняет, но цель более чем не достигнута — вместо того, чтобы сделать код более читаемым и лаконичным, мы скорее еще больше запутали его.

Кроме того есть и ряд других недостатков:

  • Нечитаемые имена. Макросы — это автозамена. Если использовать простые имена в названии и аргументах макроса, то велик шанс коллизий с пользовательским кодом. Показательный пример — коллизия макроса min\max из Windows.h с функциями стандартной библиотеки std::min\std::max. Поэтому часто приходится использовать нечитаемые имена во благо избежания описанной проблемы.
  • Никакой перегрузки. Макросы — это автозамена. Если написать несколько макросов с одинаковым именем, то доступен будет только один и з них. Поэтому написать несколько версий одного и того же макроса нельзя. А нам бы хотелось чтоб прям совсем как в Python.

Да и что уж тут говорить — это абсолютно не похоже на пример из Python.

Попытка вторая — функция-генератор коллекции


Если внимательно почитать документацию по range() из Python, то можно увидеть, что range() генерирует список сразу всех значений из диапазона. Поступим точно так же и напишем функцию, которая будет возвращать std::vector где каждый элемент — это значение индекса:
template<typename T>
std::vector<T> range(T min, T max, T step)
{
    const bool is_unsigned = std::is_unsigned<T>::value;
    if (is_unsigned && min > max)
        return std::vector<T>(0);

    size_t size = size_t((max - min) / step);
    if (!is_unsigned && size < 0)
        return std::vector<T>();
    if (size == 0)
        return std::vector<T>(1, min);

    std::vector<T> values;
    values.reserve(size);
    if (step < 0)
    {
        for (T i = min; i > max; i += step)
        {
            values.push_back(i);
        }
    }
    else
    {
        for (T i = min; i < max; i += step)
        {
            values.push_back(i);
        }
    }
    return values;
}

template<typename T>
std::vector<T> range(T min, T max)
{
    return range<T>(min, max, 1);
}

template<typename T>
std::vector<T> range(T max)
{
    return range<T>(0, max);
}


Учитывая новый синтаксис для перебора значений коллекции в стандарте С++11, возможно написать следующий код:
int main() 
{
    std::cout << '[';
    for (int i : range<int>(10))
        std::cout << i << ' ';
    std::cout << ']' << std::endl;
    
    std::cout << '[';
    for (int i : range<int>(0, 10))
        std::cout << i << ' ';
    std::cout << ']' << std::endl;

    std::cout << '[';
    for (int i : range<int>(0, 10, 2))
        std::cout << i << ' ';
    std::cout << ']' << std::endl;

    std::cout << '[';
    for (int i : range<int>(10, 2))
        std::cout << i << ' ';
    std::cout << ']' << std::endl;

    std::cout << '[';
    for (int i : range<int>(10, 2, -1))
        std::cout << i << ' ';
    std::cout << ']' << std::endl;
    return 0;
}


Вооот, это уже похоже на то, чего мы хотим достигнуть. Теперь это читается как «По всем i в диапазоне от 0 до 10». Согласитесь, звучит лучше, чем «От i равного 0, пока меньше 10, увеличивать на 1». В итоге вывод программы будет следующим:

[0 1 2 3 4 5 6 7 8 9 ]
[0 1 2 3 4 5 6 7 8 9 ]
[0 2 4 6 8 ]
[]
[10 9 8 7 6 5 4 3 ]

Это решение имеет очевидный недостаток, который следует из определения, — чрезмерное для данной операции потребление ресурсов. И чем больше диапазон значений — тем больше ресурсов потребляет промежуточное звено. В Python для решения данной проблемы существует функция xrange(), которая позволяет генерировать значения на лету.

К сожалению, функции-генераторы нам недоступны, поэтому прийдется искать другое решение.

Попытка третья, финальная — псевдо-коллекция


Чтобы пользовательский класс-коллекция поддерживал проход с помощью range-based циклов необходимо всего нечего — реализовать функции begin() и end(), которые возвращают итераторы на начало и конец коллекции соответственно. Дополнительно необходимо реализовать класс самого итератора. Но что если реализовать класс, который коллекцией будет только на уровне интерфейса, но внутренняя реализация хранить все значения не будет, а сгенерирует их по мере необходимости?

Тогда упрощенная реализация нашего класса может выглядеть следующим образом:

template<typename T>
class range sealed
{
public:

    range(T _min, T _max, T _step = T(1))
      : m_min(_min), m_max(_max), m_step(_step)
    { }

    T operator[](size_t index)
    {
      return (m_min + index * m_step);
    }

    size_t size() 
    {
      return static_cast<size_type>((m_max - m_min) / m_step);
    }
    range_iterator<range<T>> begin() 
    {
      return range_iterator<range<T>>(this, m_min);
    }

    range_iterator<range<T>> end()
    {
      return range_iterator<range<T>>(this, m_min + size() * m_step);
    }

private:
    T m_min;
    T m_max;
    T m_step;
};


Все, что необходимо хранить — это границы диапазона и шаг. Тогда любой элемент диапазона можно получить с помощью простой арифметики (см. operator[]). Основная же работа возлагается на класс итератора:
template<typename T>
class range_iterator sealed
{
public:
    typedef T range_type;
    typedef range_iterator<range_type> self_type;
    typedef typename range_type::value_type value_type;

    range_iterator(const range_type* const range, value_type start_value)
        : m_range(range), m_value(start_value)
    { }

    operator value_type() const 
    { 
        return m_value; 
    }

    value_type& operator*() {
        return m_value;
    }

    self_type& operator++() {
        m_value += m_range->step();
        return *this;
    }

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

    bool operator==(const self_type& other) const {
        return ((m_range == other.m_range) &&
            (equals<value_type>(m_value, other.m_value, m_range->step())));
    }

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

private:
    template<typename R> static bool equals(R a, R b, R e) {
        return a == b;
    }

    template<> static bool equals(double a, double b, double e) {
        return std::abs(a - b) < std::abs(e);
    }

    template<> static bool equals(float a, float b, float e) {
        return std::abs(a - b) < std::abs(e);
    }

    const range_type* const m_range;
    value_type m_value;
};


Думаю, дополнительно стоит пояснить наличие функции equals(). Предположим у нас диапазон нецелочисленный, а, допустим, от 0 до 10 с шагом 0.1. Сравнение итераторов основано на сравнении текущих значений из диапазона, хранящихся в каждом из них. Но сравнивать числа с плавающей точкой в С++ просто так нельзя. Подробнее почему можно почитать вот здесь. Скажу лишь, что если сравнивать «в лоб», то скорее всего цикл будет бесконечным. Лучший способ — это сравнивать разницу с допустимой абсолютной погрешностью. Это и реализовано в функции equals(). При чем в нашем случае абсолютная погрешность — это шаг диапазона.

Вот теперь действительно можно написать цикл в необходимой нам форме и при этом не сильно тратиться на накладные расходы.

Полная версия кода:

range.h
template<typename T>
class range_iterator : std::iterator<std::random_access_iterator_tag, typename T::value_type>
{
public:
    typedef T range_type;
    typedef range_iterator<range_type> self_type;
    typedef std::random_access_iterator_tag iterator_category;
    typedef typename range_type::value_type value_type;
    typedef typename range_type::size_type size_type;
    typedef typename range_type::difference_type difference_type;
    typedef typename range_type::pointer pointer;
    typedef typename range_type::const_pointer const_pointer;
    typedef typename range_type::reference reference;
    typedef typename range_type::const_reference const_reference;

    range_iterator(const range_type* const range, value_type start_value)
        : m_range(range), m_value(start_value)
    { }

    range_iterator(const self_type&) = default;
    range_iterator(self_type&&) = default;
    range_iterator& operator=(const range_iterator&) = default;
    ~range_iterator() = default;

    operator value_type() const { 
        return m_value; 
    }

    value_type& operator*() {
        return m_value;
    }

    self_type& operator++() {
        m_value += m_range->step();
        return *this;
    }

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

    self_type& operator--() {
        m_value -= m_range->step();
        return *this;
    }

    self_type operator--(int) {
        self_type tmp(*this);
        --(*this);
        return tmp;
    }

    self_type operator+(difference_type n) {
        self_type tmp(*this);
        tmp.m_value += m_range->step() * n;
        return tmp;
    }

    self_type& operator+=(difference_type n) {
        m_value += n * m_range->step();
        return (*this);
    }

    self_type operator-(difference_type n) {
        self_type tmp(*this);
        tmp.m_value -= n * m_range->step();
        return tmp;
    }

    self_type& operator-=(difference_type n) {
        m_value -= n * m_range->step();
        return (*this);
    }

    bool operator==(const self_type& other) const {
        return ((m_range == other.m_range) &&
            (equals<value_type>(m_value, other.m_value, m_range->step())));
    }

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

private:
    template<typename T> static bool equals(T a, T b, T e) {
        return a == b;
    }

    template<> static bool equals(double a, double b, double e) {
        return std::abs(a - b) < std::abs(e);
    }

    template<> static bool equals(float a, float b, float e) {
        return std::abs(a - b) < std::abs(e);
    }

    const range_type* const m_range;
    value_type m_value;
};

template<typename T>
class range sealed
{
    static_assert(std::is_arithmetic<T>::value, "Template type should be a integral-type");

public:
    typedef T          value_type;
    typedef T*         pointer;
    typedef const T*   const_pointer;
    typedef T&         reference;
    typedef const T&   const_reference;
    typedef size_t     size_type;
    typedef ptrdiff_t  difference_type;
    typedef range<value_type>               self_type;
    typedef class range_iterator<self_type> iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;

    range(value_type _min, value_type _max, value_type _step = value_type(1))
        : m_min(_min), m_max(_max), m_step(_step) {
        if (m_step == 0) {
            throw std::invalid_argument("Step equals zero");
        }
    }

    range(const self_type&) = default;
    range(self_type&&) = default;
    range& operator=(const self_type&) = default;
    ~range() = default;

    bool operator==(const self_type& _obj) const {
        return (m_max == _obj.max()) &&
            (m_min == _obj.min()) &&
            (m_step == _obj.step());
    }

    bool operator!=(const self_type& _obj) const {
        return !(this == _obj);
    }

    value_type operator[](size_type _index) const {
#ifdef _DEBUG
        if (_index > size()) {
            throw std::out_of_range("Index out-of-range");
        }
#endif
        return (m_min + (_index * m_step));
    }

    bool empty() const {
        bool is_empty = ((m_max < m_min) && (m_step > 0));
        is_empty |= ((m_max > m_min) && (m_step < 0));
        return is_empty;
    }

    size_type size() const {
        if (empty()) {
            return 0;
        }
        return static_cast<size_type>((m_max - m_min) / m_step);
    }

    value_type min() const {
        return m_min; 
    }

    value_type max() const {
        return m_max;
    }

    value_type step() const {
        return m_step;
    }

    iterator begin() const {
        iterator start_iterator(this, m_min);
        return start_iterator;
    }

    iterator end() const {
        iterator end_iterator(this, m_min + size() * m_step);
        return end_iterator;
    }

    reverse_iterator rbegin() const {
        reverse_iterator start_iterator(end());
        return start_iterator;
    }

    reverse_iterator rend() const {
        reverse_iterator end_iterator(begin());
        return end_iterator;
    }

private:

    value_type m_min;
    value_type m_max;
    value_type m_step;
};

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Комментариев нет:

Отправить комментарий