Итераторы

Контейнеры

Контейнеры STL можно разделить на два типа: последовательные и ассоциативные.

Последовательные контейнеры обеспечивают хранение конечного количества однотипных объектов в виде непрерывной последовательности. К базовым последовательным контейнерам относятся векторы (vector), списки (list) и двусторонние очереди (deque).

Есть еще специализированные контейнеры (или адаптеры контейнеров), которые реализованы на основе базовых, это — стеки (stack), очереди (queue) и очереди с приоритетами (priority_queue).

/*Между прочим, обычный встроенный массив C++ также может рассматриваться как последовательный контейнер. Проблема с массивами заключается в том, что их размеры нужно указывать в исходном коде, а часто бывает не известно заранее, сколько элементов придется хранить. Если же выделять память для массива динамически (оператором new), то алгоритм усложняется из-за необходимости отслеживать время жизни массива и вовремя освобождать память. Использование контейнера вектор вместо динамического массива резко упрощает жизнь программиста.*/

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

vector<int> aVect; // создать вектор aVect целых чисел (типа int)

1ist<Man> department; // создать список department типа Man

Ассоциативные контейнеры обеспечивают быстрый доступ к данным по ключу. Эти контейнеры построены на основе сбалансированных деревьев. Существует пять типов ассоциативных контейнеров: словари (map), словари с дубликатами (multlmap), множества (set), множества с дубликатами (multiset) и битовые множества (bitset).

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

Например, возможно следующее решение:

template <class Т>

Т* Find(T* ar, int п, const Т& value) {

for (int l = 0; l < п: ++l)

if (*(ar + 1) == value) return ar + l;

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

Попытаемся теперь расширить сферу применения нашей функции — хорошо бы, чтобы она решала задачу поиска заданного значения среди объектов, хранящихся в виде линейного списка!

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

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

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

Для всех контейнерных классов STL определен тип iterator, однако реализация его в разных классах разная.

Например, в классе vect, где объекты размещаются один за другим, как в массиве, тип итератора определяется посредством

typedef Т* iterator.

А вот в классе list тип итератора реализован как встроенный класс

iterator, поддерживающий основные операции с итераторами.

К основным операциям, выполняемым с любыми итераторами, относятся:

• Разыменование итератора: если р — итератор, то *р — значение объекта, на который он ссылается (позицию которого он сохраняет).

• Присваивание одного итератора другому.

• Сравнение итераторов на равенство и неравенство (== и!=).

• Перемещение его по всем элементам контейнера с помощью префиксного(++р) или постфиксного (р++) инкремента.

Так как реализация итератора специфична для каждого класса, то при объявлении объектов типа итератор всегда указывается область видимости в форме имя_шаблона::, например:

vector<int>:: iterator iter 1;

1ist<Man>:: iterator iter2:

Организация циклов просмотра элементов контейнеров тоже имеет некоторую специфику.

Так, если i — некоторый итератор, то вместо привычной формы

for (i =0: i < n; ++i)

используется следующая:

for (i = first; i!= last; ++i)

где first — значение итератора, указывающее на первый элемент в контейнере,

а last — значение итератора, указывающее на воображаемый элемент, который следует за последним элементом контейнера. Операция сравнения < здесь заменена на операцию !=, поскольку операции < и > для итераторов в общем случае не поддерживаются.

Как было сказано выше, для всех контейнерных классов определены унифицированные методы beg in() и end(), возвращающие адреса first и last соответственно.

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

Входные итераторы (Input Iterator ) используются алгоритмами STL для чтения значений из контейнера, аналогично тому, как программа может вводить данные из потока cin.

Выходные итераторы (OutputIterator) используются алгоритмами для записи значений в контейнер, аналогично тому, как программа может выводить данные в поток cout.

Прямые итераторы (ForwardIterator) используются алгоритмами для навигации по контейнеру только в прямом направлении, причем они позволяют и читать, и изменять данные в контейнере.

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

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

/*В то время как значения прямых, двунаправленных и итераторов произвольного доступа могут быть сохранены, значения входных и выходных итераторов сохраняться не могут (аналогично тому, как не может быть гарантирован ввод тех же самых значений при вторичном обращении к потоку cin). Следствием является то, что любые алгоритмы, базирующиеся на входных или выходных итераторах, должны быть однопроходными.*/

Вернемся к функции find(), которую мы безуспешно пытались обобщить для любых типов контейнеров. В STL аналогичный алгоритм имеет следующий прототип:

template <class InputIterator, class Т>

InputIterator find (InputIterator first, InputIterator last, const T& value);