Итераторы

Итератор — это мощный программный паттерн, который позволяет абстрагировать логику обхода коллекции элементов.

Пример паттерна «итератор»

Представьте, что у вас есть дерево, и вы хотите выполнить обход в глубину, выводя все значения.

Это довольно просто, но что, если вы еще хотите посчитать сумму всех значений в узлах? Придется продублировать функцию обхода, изменив лишь то, что она делает:

int sumDFS(const Node* node)
{
    int result = node->value;
    for (size_t i = 0; i < node->children.size(); i++)
        result += sumDFS(node->children[i]);
    return result;
}

Уже видно, как это может стать проблемой, если логика обхода сложнее, чем просто рекурсивный перебор потомков.

Одним из способов решения была бы стратегия (strategy pattern): передавать функцию, которую нужно выполнить при посещении узла. Как это сделать, будет описано позже.

Здесь же мы обсудим паттерн «итератор» — еще одно решение этой проблемы, причем более гибкое. Он позволяет приостановить обход и возобновить его позже, выполнять с элементами любые операции и обращаться к любым вашим переменным.

Идея в том, чтобы хранить текущее состояние итерации в объекте, фактически воспроизводя то, как выглядел бы стек при рекурсивном обходе, и определить функции для перехода итератора к следующему элементу (и, возможно, дополнительные функции, например для перехода к предыдущему). Еще понадобится способ сообщить, что итерация завершена. См. код.

Рекомендую потратить некоторое время в отладчике, чтобы разобраться, как работает эта программа.

Да, так сложнее, особенно из-за того, что в данном случае стек приходится имитировать вручную (делать это нужно не всегда), и в целом такой обход выходит сложнее обычной итерации, но дополнительная гибкость плюс устранение дублирования кода могут оказаться очень ценными.

Итераторы в C++

В C++ есть «стандартный» способ делать итераторы; он требуется, чтобы работали некоторые шаблонные функции стандартной библиотеки:

• Тип итератора перегружает оператор ++, что соответствует методу advance из моего примера. Он также может перегрузить оператор --, чтобы можно было вернуться к предыдущему элементу.

• Тип итератора перегружает оператор *, что соответствует методу value из моего примера. * работает так же, как разыменование указателя. По возможности этот оператор должен возвращать ссылку.

• У итератора есть особое состояние, означающее конец итерации. В моем случае я определил метод empty, но это «пустое» состояние можно было бы представить и тем, что оба вектора пусты. Пустота при этом проверяется сравнением итератора с этим особым состоянием.

• Типы, для которых возможен только один способ итерации, могут определить методы begin и end, возвращающие состояние итератора, установленного на первый элемент, и особое «пустое» состояние соответственно.

См. тот же пример, что и раньше, но с использованием стандартного паттерна итератора.

Замысел такого дизайна — сымитировать интерфейс, к которому вы привыкаете при работе с указателями. ++p сдвигает указатель на один элемент, *p читает значение по адресу, а p == start+count проверяет, например, достигли ли мы конца массива.

Преимущества стандартного способа

Если сделать итератор так, как принято в C++, вы получите приятный синтаксис для итерации по диапазону. Если у вашего типа есть методы begin и end, его можно использовать в цикле range-based for. См. пример.

Этот синтаксис доступен для большинства типов-контейнеров, потому что они следуют этому паттерну: определяют методы begin и end, а также тип итератора с описанными выше операциями.

Не обязательно заводить отдельный тип. Если для вашей структуры данных разумна только одна разновидность итерации или какой-то способ итерации очевидно должен быть стандартным, можно определить методы begin и end прямо у типа контейнера. Для DynamicArray, скажем, это имеет смысл, а для графа — скорее всего нет.

static_cast, reinterpret_cast, bit_cast

static_cast выполняет проверки во время компиляции и для примитивных типов делает ожидаемое преобразование значения. Приведение в стиле C, например (int)x, шире: оно может сделать то же, что и static_cast, а при необходимости — то, что умеют const_cast (снятие константности) и reinterpret_cast (переинтерпретация битов).

В контексте наследования static_cast может выполнять приведение — потенциально изменяя значение указателя — к менее производному типу, но не наоборот; фактический тип объекта во время выполнения он не проверяет (для этого есть dynamic_cast).

reinterpret_cast — это приведение, которое просто меняет тип указателя, не меняя адрес, и пропускает проверку корректности преобразования.

Тонкость: значение указателя гарантированно сохраняется, только если целевой тип предъявляет подходящие требования к выравниванию; иначе использование результата может быть неопределенным. Разыменовывать такой указатель допустимо, лишь когда по этому адресу действительно можно читать объект целевого типа.

bit_cast позволяет переинтерпретировать биты значения одного типа как значение другого типа. Например:

float a = 5.0f; // 40 a0 00 00 = 5.0
int b = std::bit_cast<int>(a); // 40 a0 00 00 = 1084227584
int c = static_cast<int>(a); // 5

Обратите внимание: число выше — просто пример вывода, который я получил, запустив этот код на своей машине, у вас может получиться другое значение. Оно зависит от того, что float хранится по IEEE 754, int занимает 32 бита, а порядок байтов младший (little-endian).