стандартный интерфейс для выполнения перебора во всех видах контейнеров. Нужно только реализовать оператор префиксного инкремента
++
, оператор разыменования *
и оператор сравнения объектов ==
, и получится примитивный итератор, подходящий для работы с циклом for
, основанным на диапазоне, который появился в C++11.Чтобы немного освоиться с итераторами, рассмотрим пример реализации одного из них, который просто генерирует диапазон чисел при переборе. Он не дополняется структурой-контейнером. Числа генерируются непосредственно при переборе.
Как это делается
В этом примере мы реализуем собственный класс итератора, а затем проитерируем по нему.
1. Сначала включим заголовочный файл, который позволит выводить данные на консоль:
#include
2. Наш класс итератора будет называться
num_iterator
:
class num_iterator {
3. Его единственным членом выступит целое число, которое послужит для счета. Оно будет инициализироваться в конструкторе. Создание явных конструкторов — хороший стиль программирования, поскольку это позволяет избежать случайных неявных преобразований. Обратите внимание: мы предоставляем значение по умолчанию для переменной
position
, что делает возможным создание экземпляров класса num_iterator
с помощью конструктора по умолчанию. Хотя в данном примере мы не будем использовать такой конструктор, эта возможность очень важна, поскольку некоторые алгоритмы STL зависят от того, можно ли создать экземпляры итераторов, применяя конструкторы по умолчанию:
int i;
public:
explicit num_iterator(int position = 0) : i{position} {}
4. При разыменовании наш итератор (
*it
) генерирует целое число:
int operator*() const { return i; }
5. Инкрементирование итератора (
++it
) просто увеличит значение его внутреннего счетчика i
:
num_iterator& operator++() {
++i;
return *this;
}
6. Цикл
for
будет сравнивать итератор с конечным итератором. Если они не равны, то продолжим перебор:
bool operator!=(const num_iterator &other) const {
return i != other.i;
}
};
7. Это был класс итератора. Нам все еще нужен промежуточный объект для записи
for (int i:intermediate(a, b)) {...}
, который содержит начальный и конечный итераторы и будет перепрограммирован так, чтобы итерировал от a
до b
. Мы назовем его num_range
:
class num_range {
8. Он содержит два члена, представляющие собой целые числа. Они обозначают число, с которого начнется перебор, а также число, стоящее непосредственно за последним числом. Это значит, что если мы хотим проитерировать по числам от
0
до 9
, то a будет иметь значение 0
, а b
— 10
:
int a;
int b;
public:
num_range(int from, int to)
: a{from}, b{to}
{}
9. Нужно реализовать всего две функции-члена:
begin
и end
. Обе эти функции возвращают итераторы, которые указывают на начало и конец численного диапазона:
num_iterator begin() const { return num_iterator{a}; }
num_iterator end() const { return num_iterator{b}; }
};
10. На этом все. Можно использовать полученный объект. Напишем функцию
main
, в которой просто проитерируем по диапазону значений от 100
до 109
и выведем эти значения:
int main()
{
for (int i : num_range{100, 110}) {
std::cout << i << ", ";
}
std::cout << '\n';
}
11. Компиляция и запуск программы дадут следующий результат:
100, 101, 102, 103, 104, 105, 106, 107, 108, 109,
Как это работает
Представьте, что мы написали следующий код:
for (auto x:range) { code_block; }
Компилятор развернет его в такую конструкцию:
{
auto _begin = std::begin(range);
auto _end = std::end(range);
for (; _begin != end; ++_begin) {
auto x = *_begin;
code_block
}
}
При взгляде на этот код становится очевидно, что для создания итератора необходимо реализовать всего три оператора:
□
operator!=
— определение равенства;□
operator++
— префиксный инкремент;□
operator*
— разыменование.
Требования к диапазону данных заключаются в том, что он должен иметь методы
begin
и end
, которые будут возвращать два итератора для обозначения начала и конца диапазона.
В данной книге мы будем использовать преимущественно
std::begin(x)
вместо x.begin()
. Это хороший вариант, поскольку функция std::begin(x)
автоматически вызывает метод x.begin()
, при условии, что он доступен. Если x
представляет собой массив, не имеющий метода begin()
, то функция std::begin(x)
автоматически определит, как с этим справиться. То же верно и для std::end(x)
. Пользовательские типы, не имеющие методов begin()/end()
, не смогут работать с методами std::begin/std::end
.
В рамках этого примера мы разместили простой алгоритм счета в интерфейсе однонаправленного итератора. Реализация итератора и диапазона данных зачастую включает в себя написание минимального объема стереотипного кода, что, с одной стороны, может слегка раздражать. С другой стороны, взглянув на цикл, который использует
num_range
, мы понимаем, что это здорово, поскольку цикл выглядит очень просто!
Пролистайте книгу назад и еще раз взгляните на то, какие методы итератора и диапазон классов являются константными. Если не сделать их таковыми, то компилятор во многих ситуациях может отклонить ваш код, поскольку перебор константных объектов происходит довольно часто.
Обеспечиваем совместимость собственных итераторов с категориями итераторов STL
Какую бы структуру данных вы ни создали, для эффективного объединения ее с библиотекой STL нужно добавить интерфейсы для итераторов. В последнем разделе мы научились делать это, но затем быстро поняли, что некоторые алгоритмы STL плохо компилируются с нашими итераторами. Почему так происходит?
Проблема заключается в том, что многие алгоритмы STL пытаются больше узнать об итераторах, с которыми должны работать. Разные категории итераторов имеют разные возможности, и поэтому существует несколько вариантов реализации одного алгоритма. Например, обычные числа из одного вектора в другой можно скопировать с помощью быстрого вызова
memcpy
. Если мы копируем данные из списка или в него, то такой вызов сделать нельзя и элементы нужно копировать по одному. Авторы алгоритмов STL хорошо продумали подобную автоматическую оптимизацию. Чтобы помочь им, мы укажем некоторую информацию о наших итераторах. В этом разделе показано, как достичь той же цели.
Как это делается
В этом примере мы реализуем примитивный итератор, считающий числа, и используем его вместе с алгоритмом STL, с которым он изначально не будет компилироваться. Затем сделаем все, чтобы итератор стал совместим с STL.
1. Сначала, как обычно, включим некоторые заголовочные файлы:
#include
#include
2. Далее реализуем примитивный итератор для подсчета чисел, как было показано в предыдущем разделе. При переборе он генерирует обычные увеличивающиеся целые числа. Диапазон данных
num_range
выступает в роли удобного донора начального