[Из песочницы] Упрощаем for-цикл по индексам: range-based версия
Волею судеб мне довелось заняться одной задачей автоматизации при помощи Python-скрипта. Изучая базовые конструкции, наибольший интерес у меня вызвал следующий код:
for index in range(0,10) :
do_stuff()
Удобно, читаемо, лаконично (модно, стильно, молодежно)! Почему бы не организовать такой же цикл в С++? Что из этого вышло — под катом.
Попытка первая — макросы
О недостатках макросов написано много. И главное правило гласит: «Если можно что-то реализовать не используя макросы — так и сделай». Но иногда использование макросов вполне оправданно.
Макросы часто используют для расширения языка нестандартными конструкциями — например, чтобы ввести ключевое слово вечного цикла для большей читаемости кода:
#define infinite_loop while(true)
infinite_loop
{
do_stuff();
}
Кстати, мы ведь тоже задались вопросом реализации нестандартного цикла. Что если попробовать реализовать это дело с помощью макросов. Примерно вот так:
#include
#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
std::vector range(T min, T max, T step)
{
const bool is_unsigned = std::is_unsigned::value;
if (is_unsigned && min > max)
return std::vector(0);
size_t size = size_t((max - min) / step);
if (!is_unsigned && size < 0)
return std::vector();
if (size == 0)
return std::vector(1, min);
std::vector 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
std::vector range(T min, T max)
{
return range(min, max, 1);
}
template
std::vector range(T max)
{
return range(0, max);
}
Учитывая новый синтаксис для перебора значений коллекции в стандарте С++11, возможно написать следующий код:
int main()
{
std::cout << '[';
for (int i : range(10))
std::cout << i << ' ';
std::cout << ']' << std::endl;
std::cout << '[';
for (int i : range(0, 10))
std::cout << i << ' ';
std::cout << ']' << std::endl;
std::cout << '[';
for (int i : range(0, 10, 2))
std::cout << i << ' ';
std::cout << ']' << std::endl;
std::cout << '[';
for (int i : range(10, 2))
std::cout << i << ' ';
std::cout << ']' << std::endl;
std::cout << '[';
for (int i : range(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
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((m_max - m_min) / m_step);
}
range_iterator> begin()
{
return range_iterator>(this, m_min);
}
range_iterator> end()
{
return range_iterator>(this, m_min + size() * m_step);
}
private:
T m_min;
T m_max;
T m_step;
};
Все, что необходимо хранить — это границы диапазона и шаг. Тогда любой элемент диапазона можно получить с помощью простой арифметики (см. operator[]). Основная же работа возлагается на класс итератора:
template
class range_iterator sealed
{
public:
typedef T range_type;
typedef range_iterator 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(m_value, other.m_value, m_range->step())));
}
bool operator!=(const self_type& other) const {
return !((*this) == other);
}
private:
template 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 (). При чем в нашем случае абсолютная погрешность — это шаг диапазона.
Вот теперь действительно можно написать цикл в необходимой нам форме и при этом не сильно тратиться на накладные расходы.
Полная версия кода:
template
class range_iterator : std::iterator
{
public:
typedef T range_type;
typedef range_iterator 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(m_value, other.m_value, m_range->step())));
}
bool operator!=(const self_type& other) const {
return !((*this) == other);
}
private:
template 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
class range sealed
{
static_assert(std::is_arithmetic::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 self_type;
typedef class range_iterator iterator;
typedef std::reverse_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((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;
};
