Итераторы

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

Подобно указателю, итератор может ссылаться на единственный элемент данных; пара итераторов может задавать определенный диапазон контейнера; итератор может иметь т. н. запредельное значение, аналогичное NULL и означающее, что его нельзя разыменовывать.

Следует упомянуть, что при вызове различных алгоритмов для диапазона, заданного парой итераторов, второй из них соответствует не последнему значению итератора в диапазоне, а следующему за ним.

Основными операциями над итераторами- являются, как и в случае указателей, разыменование и инкремент. Если итератор i после конечного ряда приращений может стать равным итератору j, то говорят, что итератор j достижим из i. Если к итератору, достигшему верхней границы диапазона, применить операцию инкремента, он примет запредельное значение.

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

Типы итераторов

Существует пять основных форм итераторов:

Входной итератор обеспечивает доступ к контейнеру только для чтения в поступательном направлении (т. е. к итератору применима операция инкремента).

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

Поступательный итератор предоставляет доступ для чтения-записи в поступательном направлении.

Двунаправленный итератор допускает чтение и запись как в поступательном, так и реверсивном направлениях (к нему применимы как инкремент, так и декремент).

Итератор произвольного доступа предоставляет прямой доступ к данным для чтения-записи.

Итераторы, стоящие в этом списке ниже, выводятся из тех, что находятся выше. Это едва ли не единственный пример классовой иерархии в 8TL.

В следующей таблице показано, какими контейнерами стандартной библиотеки генерируются те ли иные итераторы.



Таблица 10.2. Итераторы, генерируемые стандартной библиотекой

Форма итератора	Контейнеры
входной итератор	istream iterator
выходной итератор	ostream iterator
двунаправленный итератор	List set и multiset map и multimap
итератор произвольного доступа	обычные указатели vector deque

Указатели как итераторы



Чтобы продемонстрировать, как применяются итераторы, мы рассмотрим простейший вид итератора — обычный указатель. Следующая программа вызывает стандартный алгоритм find() для поиска значения в обычном массиве.

#include <algorithm>

#include <iostream>

using namespace std;

#define SIZE 50 int iArr[SIZE] ;

int main() {

iArr[30] = 33;

int *ip = find(iArr, iArr + SIZE, 33);

if (ip != iArr + SIZE)

cout<< "Value "<< *ip<< " found at position "<< (ip - iArr)<< endl;

else

cout << "Value not found."<< endl;

return 0;

}

Прежде всего обратите внимание, что программа, применяющая стандартную библиотеку C++, должна специфицировать директивой using namespace пространство имен std.

В примере объявляется “контейнер” — обычный массив длиной в 50 элементов, одному из его элементов присваивается значение 33 и вызывается алгоритм find () для поиска этого значения.

Алгоритму find () передаются три аргумента. Два из них — итераторы, задающие диапазон поиска. Первый из них в данном случае указывает на начальный элемент массива, второй имеет запредельное значение iArr + SIZE, т. е. смещен на один элемент за верхнюю границу массива. Третий аргумент задает искомое значение.

Если find () находит его в заданном диапазоне, алгоритм возвращает соответствующий ему итератор; если нет, возвращается запредельное значение.



Итераторы контейнеров



Итераторы, генерируемые классами контейнеров, используются точно таким же образом, как указатели в показанном выше примере, но для получения граничных значений итератора вь1зываются обычно функции вроде begin () или end () конкретного контейнерного объекта. Вот совершенно аналогичный предыдущему пример для контейнера-вектора:



#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

#define SIZE 50 vector<int> iVect(SIZE);

int main() {

iVect[30] = 33;

vector<int>::iterator ii =

find (iVect. begin (), iVect.endO, 33);

if (ii != iVect.endO)

cout << "Value "<< *ii<< " found at position "

<< distance(iVect.begin(), ii) << endl;

else

cout << "Value not found." <<end1;

return 0;

Объявляемый в программе контейнер имеет тип vector<int>, а итератор — тип vector<int>: : iterator. Каждый стандартный контейнер объявляет свой собственный вложенный класс iterator.

Далее мы вкратце рассмотрим различные формы итераторов.



Входные, выходные и поступательные итераторы



Простейший из итераторов — входной. Он может перемещаться по контейнеру только в поступательном направлении и допускает только чтение данных. Первые два параметра алгоритма find (), например, должны быть входными итераторами. Выходной итератор отличается от входного правом доступа. Он допускает только запись данных в контейнер.

К обеим этим формам итераторов можно применять, по меньшей мере, операцию неравенства (!=), разыменования (*) и инкремента (++).

Ниже показан пример копирования массива в вектор при посредстве выходного итератора и алгоритма copy (). Его последним параметром может быть любой выходной итератор. На самом деле тот же итератор здесь используется и как входной — в операторе вывода.

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

double dArr[10] =

{1.0, 1.1, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9};

vector<double> dVect(lO);

int main()

{

vector<double>::iterator oi = dVect.begin ();

copy(dArr, dArr + 10, oi);

while (oi != dVect.endO) {

cout << *oi << endl;

oi++;

} return 0;

}



Итераторы потоков



Собственно, только входные и только выходные итераторы имеют смысл в основном при работе с потоками ввода-вывода, которые могут быть допускать либо только извлечение, либо только передачу данных. Любые контейнеры стандартной библиотеки генерируют более сложные, итераторы, которые, естественно, могут применяться и в качестве простых входных или выходных. / Вы уже хорошо знакомы со стандартными потоками cin и cout, извлечение и передача данных из которых производится операциями >> и <<. Однако возможен другой метод работы с этими потоками, при котором входной или выходной объект iostream преобразуется в итератор. Затем его можно передавать как аргумент стандартным алгоритмам.



Например, ниже показано, как можно применить выходной итератор для вывода на экран содержимого контейнера.

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

int main( ) {

vector<int> iVect(lO);

for (int i=0; i<10; i++) iVect[i] = i;

cout<< "The vector contents are: { ";

copy(iVect.begin (),

iVect.endf), ostream_iterator<int>(cout, " "));

cout << "}." << endl;

return 0;

}

Последний параметр алгоритма copy () конструирует выходной итератор типа ostream iterator<int>. Параметрами конструктора являются выходной поток и строка - разделитель значений.

Поступательный итератор допускает как чтение, так и запись в контейнер. Однако, как и в случае двух предыдущих, возможен только инкремент, но не декремент итератора. Поступательные итераторы могут использоваться, например, в алгоритме replace (), который определяется так:

template <class Forwardlterator, class T>

void replace(Forwardlterator first,

Forwardlterator last,

const T &old_value,

const T &new_value);

Этот алгоритм заменяет все значения old_value, содержащиеся в контейнере, на new_value.



Двунаправленные итераторы



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

template <class Bidirectioriallterator>

void reverse(Bidirectionallterator first,Bidirectionallterator.last);

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



Итераторы произвольного доступа



Эти итераторы являются наиболее универсальными с точки зрения возможностей доступа. Их можно использовать для произвольного чтения и записи данных контейнера. (Обычные указатели принадлежат, кстати, к этому виду итераторов.) Такие итераторы участвуют в алгоритмах сортировки, входящих в стандартную библиотеку.



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

template <class RandomAccessIterator>

void random shuffle(RandomAccessIterator first, RandomAccessIterator last);



Итераторы вставки

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

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

Конечные адаптеры, присоединяющие объекты в конец контейнера.

Адаптеры вставки, вставляющие данные перед произвольным элементом контейнера.

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

В типичном случае адаптер вставки применяется после поиска некоторого значения, как показано в следующем примере.

////////////////////////////////////////////////////////////////

// Inserter.срр: Демонстрация итераторов вставки. //

#include <algorithm>

#include <list>

#include <iostream>

#pragma hdrstop

#include <condefs.h>

using namespace.std;

int iArr[5] = (1, 2, 3, 4, 5);

//

// Функция вывода содержимого списка.

//

void Display(list<int> &1, const char *label)

(

cout << label<< ": { ";

copy (1 .begin (), 1.end(),

ostream_iterator<int>(cout, " "));

cout << "}" << endl;

}

int main(void) {

list<int> iLst; // Создание объекта списка.

// Копирование массива в список в обратном порядке:

copy(iArr, iArr + 5, front_inserter(iLst));

Display(iLst, "Before insertion");



// Поиск значения З:

list<int>::iterator i = find(iLst.begin(),

iLst.end(), 3) ;

// Вставка массива в список:

copy(iArr, iArr + 5, inserter(iLst, i));

Display(iLst, "After insertion ");

cin.ignore ();

return 0;

}

Рис. 11. 1 показывает результат работы программы. Можно отметить различие между inserter (iLst, i-Lst. begin ()) и front inserter (iLst). Первый адаптер вставляет данные в контейнер в прямом, а второй — в обратном порядке.



Рис. 11.1 Демонстрация адаптеров



Функции итераторов



Имеются две функции, которые могут оказаться полезными при работе с итераторами. Это advance () и distance (.) .

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

list<int> :: iterator i = find (iLst .begin (), iLst.endO, 3);

advance(i, 2); // Сдвигает итератор на 2 позиции вперед.

С функцией distance () вы уже встречались в примере параграфа “Итераторы контейнеров”, где с ее помощью выяснялась позиция итератора по отношению к началу вектора. Эта функция определяет количество инкрементов, которые нужно выполнить для перехода от одного итератора к другому. Она перегружена:

template <class Forwardlterator> iterator_traits<Forward!terator>::

difference_type distance(Forwardlterator first, Forwardlterator last) ;

template <class Forwardlterator, class Distance>

void distance(Forwardlterator first,

Forwardlterator last. Distance &n) ;

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

int d = 0;

distance (iLst, i, d);


Содержание раздела

---