Итераторы

Пришло время поговорить об итераторах. В максимально общем смысле, итераторы -- это универсальный способ доступа к данным в STL. Однако автору представляется совершенно необходимым, чтобы программист, использующий STL, хорошо понимал необходимость в итераторах.

Рассмотрим следующую задачу. Дан массив A длины N. Необходимо изменить порядок следования элементов в нём на обратный («развернуть массив на месте»).

Начнём издалека, с решения на чистом C.

void reverse_array_simple(int *A, int N) {
   // индексы элементов, которые мы 
   // на данном шаге меняем местами
   int first = 0, last = N-1; 
   while(first < last) { // пока есть что переставлять
      // swap(a,b) --- стандартная функция STL
      swap(A[first], A[last]); 
      first++; // смещаем левый индекс вправо
      last--; // а правый влево   
   }
}

Пока ничего сложного в этом коде нет. Его легко переписать, заменив индексы на указатели:

void reverse_array(int *A, int N) {
   int *first = A, *last = A+N-1;
   while(first < last) {
      swap(*first, *last);
      first++;
      last--;
   }
}

Рассмотрим основной цикл данной функции. Какие операции над указателями он выполняет? Всего лишь следующие:

*

сравнение указателей (first < last),

*

разыменование указателей (*first, *last),

*

инкремент и декремент указателя (first++, last-)

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

Первый вариант функции, в котором использовались индексы в массиве, работать, конечно, не будет. Если даже написать функцию обращения к элементам списка по индексу, о производительности и/или экономии памяти можно забыть.

Обратим теперь внимание на то, что второй вариант функции, который использует указатели, может работать с любыми объектами, которые обеспечивают функциональность указателя. А именно: сравнение, разыменование, инкремент/декремент. В языке C уже есть удобный, привычный многим и проверенный временем синтаксис для непрямого обращения к данным: нам лишь осталось подставить вместо указателя объект, который умеет делать то же самое.

Именно этот подход используется в STL. Конечно, для контейнера типа vector итератор -- это почти то же самое, что и указатель. Но для более сложных структур данных, например, для красно-чёрных деревьев, универсальный интерфейс просто необходим.

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

*

разыменование (int x = *it);

*

инкремент/декремент (it1++, it2-);

*

сравнение (об этом речь пойдёт позже; пока просто скажем, что это операции == и !=)

*

добавление константы (it += 20 -- сдвинуться на 20 элементов вперёд);

*

расстояние между итераторами (int dist = it2-it1);

Язык C++ предоставляет необходимые средства для создания произвольного объекта, который сможет вести себя именно таким образом.

Итак, какую функциональность должен обеспечивать итератор для двусвязного списка, чтобы наша функция reverse_array смогла функционировать? Более узкую, чем указатель, а именно: разыменование, инкремент/декремент, сравнение.

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

*

разыменование (*it);

*

инкремент (++);

*

сравнение (==).

В нашем примере с двусвязным списком, мы также предполагаем, что для его итератора определена операция -. Конечно, о добавлении константы, о сравнении двух итераторов на «больше/меньше» и, тем более, о вычислении разности между итераторами в двусвязном списке не может быть и речи.

В отличие от обычных указателей, итераторы могут также нести много другой полезной нагрузки. В качестве основных примеров, не вдаваясь в подробности, следует отметить проверку выхода за границы массива (Range Checking) и статистику использования контейнера (Profiling).

Основное преимущество итераторов, бесспорно, заключается в том, что они помогают систематизировать код и повышают коэффициент его повторного использования. Один раз реализовав некоторый алгоритм, использующий итераторы, его можно использовать с любым типом контейнера. Можете быть уверены: разработчики STL так и сделали, поэтому большую часть алгоритмов писать не придётся. С другой стороны, если вам необходимо реализовать свой тип контейнера, реализуйте ещё и механизм итераторов -- и широкий спектр алгоритмов, как стандартных, так и авторских, будет сразу доступен.

На самом деле, не всем итераторам необходимо поддерживать всю функциональность. В STL пошли по следующему пути: итератор поддерживает те операции, которые он может выполнить за O(1), т. е. независимо от размеров контейнера и параметров. Это означает, к примеру, что для итераторов по двусвязному списку, операции сравнения (<, >) и арифметические операции (it += offset или shift = it2-it1) не применимы. Действительно, время работы этих операций зависит как от размеров контейнера, так и от параметров. С другой стороны, операции сравнения (it1 == it2, it1 != it2), и инкремента/декремента (it1++, it2-), конечно, допустимы.

В свете вышесказанного, итераторы подразделяются по типам:
-- random access iterator: итератор произвольного доступа; умеет всё, что умеет делать указатель, и даже немного больше
-- normal iterator: то же, что итератор произвольного доступа, но не поддерживает арифметические операции <, >, +=, -=, -
-- forward iterator: то же, что normal iterator, но не поддерживает декремент. Пример: односвязный список.

Ввиду того, что итераторы списка нельзя сравнивать при помощи operator <, код функции обращения списка следует модифицировать:

template<typename T> void reverse_list(T *first, T *last) {
   if(first != last) { 
   // точнее, параноик написал бы if(!(first == last))
      while(true) {
         swap(*first, *last);
         first++;
         if(first == last) {
            break;
         }
         last--;
         if(first == last) {
            break;
         }
      }
   }
}

Пришло время вернуться к STL. Каждый контейнер в STL имеет собственный тип итератора, и даже часто не один. Программисту об этом знать не обязательно. Программисту лишь надо помнить, что для любого контейнера определены методы begin() и end(), которые возвращают итераторы начала и конца, соответственно.

Однако, в отличие от вышеприведённого примера, end() возвращает итератор, указывающий не на последний элемент контейнера, а на непосредственно следующий за ним элемент. Это часто бывает удобно. Например, для любого контейнера c разность (c.end() - c.begin()) всегда равна c.size(), если, конечно, итераторы данного типа контейнера поддерживают арифметические операции. А (c.begin() == c.end()) тождественно равно c.empty() -- для любых типов контейнеров.

Таким образом, STL-совместимая версия функции reverse_list приведена ниже.

template<typename T> void 
        reverse_list_stl_compliant(T *begin, T *end) {
   // Сначала мы должны уменьшить end,
   // но только для непустого диапозона
   if(begin != end) 
   {
      end--;
      if(begin != end) {
         while(true) {
            swap(*begin, *end);
            begin++;
            if(begin == end) {
               break;
            }
            end--;
            if(begin == end) {
               break;
            }
         }
      }
   }
}

Теперь эта функция полностью соответствует функции std::reverse(iterator begin, iterator end), определённой в модуле algorithm. В качестве упражнения хотелось бы порекомендовать читателю прочитать и разобрать код функции std::reverse какой-либо из стандартных реализаций STL -- например, SGI или Boost.

Каждый STL контейнер имеет так называемый интервальный конструктор: конструктор, который в качестве параметров принимает два итератора, который задают интервал объектов, тип которых приводим к типу контейнера. Это будет продемонстрировано в следующих примерах.

vector<int> v;
...
vector<int> v2(v);

// интервальный конструктор, v3 == v2
vector<int> v3(v.begin(), v.end()); 

int data[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
vector<int> primes(data,data+(sizeof(data)/sizeof(data[0])));

Последняя строка инициализирует vector<int> primes содержимым массива data при помощи интервального конструктора.

Более сложные примеры:

vector<int> v;
...
vector<int> v2(v.begin(), v.begin() + (v.size()/2));

Создаваемый вектор v2 будет содержать первую половину вектора v.

Особо следует выделить тот факт, что в качестве итератора алгоритмам STL можно передавать объекты произвольной природы -- необходимо лишь, чтобы они поддерживали соответствующий функционал. Разберём на примере функции reverse:

int data[10] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
reverse(data+2, data+6);
// интервал { 5, 7, 9, 11 } переходит в { 11, 9, 7, 5 };

Кроме того, каждый контейнер имеет также так называемые обратные итераторы -- итераторы, служащие для обхода контейнера в обратном порядке. Обратные итераторы возвращаются методами rbegin()/rend():

vector<int> v;
vector<int> v2(v.rbegin()+(v.size()/2), v.rend());

Вектор v2 содержит первую половину v, в порядке от середины к началу.

Чтобы создать объект типа итератор, следует указать его тип. Тип итератора получается приписыванием к типу контейнера ::iterator, ::const_iterator, ::reverse_iterator или ::const_reverse_iterator. Смысл этих типов уже должен быть понятен слушателю.

Таким образом, содержимое вектора можно просмотреть следующим образом:

vector<int> v;

for(vector<int>::iterator it = v.begin(); it!=v.end(); it++) {
  *it = (*it) * (*it); // возводим каждый элемент в квадрат
}

В условии цикла строго рекомендуется использовать operator !=, а не operator <.