Обертаємо алгоритми ітератори

Здрастуйте, дорогі читачі.

Сьогодні п'ятниця, а у нас на борту триває напружений отсмотр і аналіз новинок по C++, бажано з урахуванням C++ 17. В ході цього захоплюючого заняття ми набрели на блог Яцека Галовица (Jacek Galowicz). З порівняно свіжих матеріалів нам особливо сподобалася стаття, розміщена під катом.


Буває, потрібно згенерувати діапазон чисел з будь-якого алгоритму. Будь то діапазон чисел, просто розташованих за зростанням, або лише непарні числа, або тільки прості і т. п. Деякі операції можна оптимізувати, запам'ятовуючи значення для розрахунку такого числа, точно як це робиться з числами Фібоначчі. У цій статті я розповім, як обертати такі розрахунки у ітератори, щоб виходили потужні, красиво інкапсульовані алгоритми.

Числа Фібоначчі

Ряд чисел Фібоначчі широко відомий. Генерація цих чисел – класичний приклад рекурсії, але, як мінімум, в стандартних імперативних мовах, итеративная версія виходить могутніше:

size_t fib(size_t n)
{
size_t a {0};
size_t b {1};

for (size_t i {0}; i < n; ++i) {
const size_t old_b {b};
b += a;
a = old_b;
}

return b;
}


Таким чином дуже просто створити будь-яке число Фібоначчі. Але якщо для вирішення тієї чи іншої задачі потрібно згенерувати всі числа Фібоначчі аж до деякої межі, це рішення вже не назвеш зручним. При підрахунку числа Фібоначчі
N
,
N+1
, вміст змінних a і b можна було б переиспользовать, оскільки кожне число Фібоначчі є сума двох попередніх чисел того ж ряду.

В даному випадку зручно було б мати клас, керуючий певним станом Фібоначчі, щоб з його допомогою швидко отримувати саме таке число.

Багато хто з нас просто реалізували б клас
fibonacci_number
з деяким методом
next()
, методом
current()
– і використовували його. Це, звичайно, добре, але я пропоную зробити ще один крок і нагадую: адже саме так працюють ітератори. Реалізувавши цю функціональність мовою ітераторів, її можна використовувати у комбінації з STL, значно підвищивши читабельність коду.

Ітератори

Що потрібно зробити, щоб реалізувати найпростіший можливий ітератор?

Ось що має до нас компілятор C++, якщо ми хочемо перебрати клас контейнера:

for (const auto &item : vector) {
/* тіло циклу */
}


Таке оголошення циклу існує з часів C++11. Компілятор зробить з нього ось такий еквівалентний код:

{
auto it (std::begin(vector));
auto end (std::end(vector));

for (; it != end; ++it) {
const auto &item (*it);
/* тіло циклу */
}
}


Дивимося на розширений цикл – і бачимо, що потрібно реалізувати. По-перше, потрібно розрізняти об'єкти двох видів:
vector
– це итерируемый діапазон, а
it
ітератор.

Итерируемый діапазон повинен реалізовувати функції
begin()
та
end()
. Ці функції повертають об'єкти ітератора.

Зверніть увагу: в прикладі коду повертається не vector.begin() і vector.end(), а
std::begin(vector)
та
std::end(vector)
. Ці функції STL дійсно викликають vector.begin() і end(), але вони більш універсальні, тобто, застосовуються з необробленими масивами і автоматично роблять що треба, щоб отримати початковий і кінцевий ітератори.

Ось що повинно бути реалізоване у
iterator
:

  • оператор *, виконує розіменування вказівника (покажчики – також повноцінні ітератори!)
  • оператор ++ (префіксний), що робить інкремент ітератора до наступного елемента
  • оператор !=, потрібний для перевірки того, а чи не слід завершити цикл – тобто, не досяг
    it 
    позиції, зазначеної в
    end
    .


Щоб реалізувати якої б то ні було алгоритмічно генерується діапазон, для початку потрібно зробити ітератор, який, в суті, приховує змінні і сам алгоритм реалізації
operator++
. Потім итерируемый клас просто надасть початковий і кінцевий ітератори, забезпечивши, таким чином, цикли for у стилі C++11.

class iterator
{
// ... змінні стану ...

public:
// Конструктор

iterator& operator++() { /* інкремент */ return *this; }

T operator*() const { /* повернути значення або посилання */ }

bool operator!= const (const iterator& o) { /* порівняти стану */ }
}


Найпростіший на світі ітератор – лічильний; він просто обертає цілочисельну змінну, обертає її в operator++ і повертає ціле число
operator*
.
operator!=
потім просто порівняти це число з числом з іншого ітератора.
А тепер перейдемо до ітератора Фібоначчі.

Ітератор Фібоначчі

class fibit
{
size_t i {0};
size_t a {0};
size_t b {1};

public:
constexpr fibit() = default;

constexpr fibit(size_t b_, size_t a_, size_t i_)
: i{i_}, a{a_}, b{b_}
{}

size_t operator*() const { return b; }

constexpr fibit& operator++() {
const size_t old_b {b};
b += a;
a = old_b;
++i;
return *this;
}

bool operator!=(const fibit &o) const { return i != o.i; }
};


За допомогою цього ітератора вже можна перебрати числа Фібоначчі:

fibit it;

// Оскільки оператор порівняння порівнює тільки змінну "і",
// визначаємо ітератор з одними нулями, але для "і" встановлюємо значення
// 20, щоб на ньому перебір завершився 
const fibit end {0, 0, 20};

while (it != end) {
std::cout << *it << std::endl;
++it;
}

// Або робимо це красиво як у STL: (спочатку включаємо <iterator>)
std::copy(it, end, std::ostream_iterator<size_t>{std::cout,"\n"});


Щоб все було красиво, як в C++11, нам потрібен итерируемый клас:

class fib_range
{
fibit begin_it;
size_t end_n;

public:
constexpr fib_range(size_t end_n_, size_t begin_n = 0)
: begin_it{fibit_at(begin_n)}, end_n{end_n_}
{}

fibit begin() const { return begin_it; }
fibit end() const { return {0, 0, end_n}; }
};


А тепер можна написати…

for (const size_t num : fib_range(10)) {
std::cout << num << std::endl;
}


… і вивести на екран 10 перших чисел Фібоначчі

Що робить функція
fibit_at
? Це функція
constexpr
, яка по можливості просуває ітератор Фібоначчі під час компіляції, щоб він дійшов до того числа Фібоначчі, яке потрібно користувачеві:

constexpr fibit fibit_at(size_t n)
{
fibit it;
for (size_t i {0}; i < n; ++i) {
++it;
}
return it;
}


Наприклад, ця функція дозволяє перебрати числа в ряду Фібоначчі від сотого до сто п'ятого без необхідності обчислювати перші 100 чисел Фібоначчі під час виконання, так як ми можемо підготувати потрібну стартову позицію вже під час компіляції.

При роботі з C++17
fibit_at
марна, так як її можна замінити на
std::next(fibit{}, n)
, оскільки в C++17
STLstd::next
– це функція
constexpr
.

Щоб гарантувати, що 100-е число в ряду Фібоначчі вже буде вирахувано, коли компілятор стане записувати на диск бінарну програму, можна просто внести діапазон в змінну
constexpr
:

constexpr const fib_range hundred_to_hundredfive {105, 100};

for (size_t num : hundred_to_hundredfive) {
// Робимо що-небудь
}


Комбінуємо ітератор Фібоначчі з алгоритмами STL

Припустимо, нам потрібен вектор з першими 1000 числами Фібоначчі. Ми вже обернули алгоритм Фібоначчі в зручний клас ітератора, і тепер можемо використовувати його з будь-STL-алгоритмом з простору імен
std:


std::vector<size_t> fib_nums;
fib_nums.resize(1000);

constexpr const fib_range first1000 {1000};
std::copy(std::begin(first1000), std::end(first1000), std::begin(fib_nums));


Дуже красиво і зручно. Однак, код в тому вигляді, як він представлений тут, не відбудеться створення, оскільки ми не поставили позначку ітератора. Робиться це просто: нехай
fibit
явно успадкує
std::iterator<std::forward_iterator_tag, size_t>
.

std::iterator
, будучи базовим для нашого класу
fibit
, просто додасть кілька визначень типів, які допоможуть алгоритмів STL розібратися, що це за ітератор. Для ітераторів певного типу в конкретних ситуаціях існують інші реалізації алгоритмів STL, продуктивність яких оптимізована (від користувача це акуратно приховано!).

Мітка
std::forward_iterator
означає, що перед нами ітератор, який можна просто просувати крок за кроком – і він буде рухатися тільки вперед, але не назад.

Підсумки

Багато алгоритми, генеруючі числові діапазони, можна реалізувати у вигляді ітераторів, що абсолютно природно. В C++ є смачний синтаксичний цукор для ітераторів, завдяки чому з них виходять органічні інтерфейси для абстракцій.

Разом з алгоритмами STL і будь-STL-сумісними структурами даних з них виходить зрозумілій потужний код, який легко тестувати і підтримувати.

У статті розповідається про итераторе, а не звичайному покажчику даних. Реалізація алгоритму цікава тим, що на етапі инкремента обчислюється щось більш складне, ніж нова позиція внутрішнього вказівника на наступний елемент. Цікаво, що таким чином можна инстанцировать деякий итерируемый об'єкт, що визначає діапазон – а для цього необхідні серйозні обчислення. Але вони виконані не будуть, поки хто-небудь спеціально не запросить результат (а код, запитувач результат, навіть не «знає», який алгоритм при цьому неявно, оскільки ця інформація прихована за простим інтерфейсом ітератора).

Такий стиль пов'язаний з ледачими обчисленнями – це потужний і красивий принцип з чисто функціональних мов програмування.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.