Работа с итераторами: доступ к данным, вставка данных, алгоритмы и итераторы

Итераторы

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

Итераторы можно инкрементировать с помощью обычного оператора ++, после выполнения которого итератор передвинется на следующий элемент. Косвенность со ссылок снимается оператором *, после чего можно получить значение элемента, на который ссылается итератор. В STL итератор представляет собой

объект класса iterator.

Для разных типов контейнеров используются свои итераторы. Всего существует три основных класса итераторов: прямые, двунаправленные и со случайным доступом. Прямой итератор может проходить по контейнеру только в прямом направлении, что и указано в его названии. Проход осуществляется поэлементный. Работать с ним можно, используя ++. Такой итератор не может двигаться в обратном направлении и не может быть поставлен в произвольное место контейнера. Двунаправленный итератор, соответственно, может передвигаться в обоих направлениях и реагирует как на ++, так и на —. Итератор со случайным досту-

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

Есть два специализированных вида итераторов. Это входной итератор, который может «указывать» на устройство ввода (cin или даже просто входной файл) и считывать последовательно элементы данных в контейнер, и выходной итератор, который, соответственно, указывает на устройство вывода (cout) или вы-

ходной файл и выводит элементы из контейнера.

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

Таблица 15.6. Характеристики итераторов

Тип итератора Запись/Чтение Хранение значения Направление Доступ

Со случайным

доступом Запись и чтение Возможно Оба направления Случайный

Двунаправленный Запись и чтение Возможно Оба направления Линейный

Прямой Запись и чтение Возможно Только прямое Линейный

Выходной Только запись Невозможно Только прямое Линейный

Входной Только чтение Невозможно Только прямое Линейный

Возможные проблемы с STL

Шаблонные классы STL достаточно сложны, при их обработке компилятору

приходится несладко. Не все компиляторы выдерживают.

Рассмотрим некоторые возможные проблемы.

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

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

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

_______STL может генерировать разные забавные сообщения. Например, «При преобразовании могут потеряться значащие разряды!» — это просто хит. В принципе, эти ошибки довольно безобидны, не стоит обращать на них внимания. Если

они вас сильно раздражают, можно их отключить вообще.

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

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

Алгоритмы

Алгоритмы STL выполняют различные операции над наборами данных. Они были разработаны специально для контейнеров, но их замечательным свойством является то, что они применимы и к обычным массивам C++. Это может сильно упростить работу с массивами. К тому же изучение алгоритмов для контейнеров

поможет усвоить общие принципы подобной обработки данных, безотносительно к контейнерам и STL (сами алгоритмы можно найти в приложении Е).

Алгоритм find ()

Этот алгоритм ищет первый элемент в контейнере, значение которого равно указанному. В примере FIND показано, как нужно действовать, если мы хотим найти

значение в массиве целых чисел.

Листинг 15.1. Программа FIND

// find.cpp

// найти первый объект, значение которого равно данному

#include <iostream>

#include <algorithm> //для find()

using namespace std;

int arr[] = { 11, 22, 33, 44, 55, 66, 77, 88 };

int main()

{

int* ptr;

ptr = find(arr, arr+8, 33); //найти первое вхождение 33

cout << "Первый объект со значением 33 найден в позиции "

<< (ptr-arr) << endl;

return 0;

}

Результаты программы:

Первый объект со значением 33 найден в позиции 2

Заголовочные файлы

В эту программу включен заголовочный файл ALGORITHM. (Заметим, что, как и в других заголовочных файлах Стандартной библиотеки C++, расширения типа.H не пишут.) В этом файле содержатся объявления алгоритмов STL. Другие заголовочные файлы используются для контейнеров и для иных целей. Если вы используете старые версии STL, вам может понадобиться заголовочный файл с немного другим именем: ALGO.H.

Диапазоны

Первые два аргумента алгоритма find() определяют диапазон просматриваемых элементов. Значения задаются итераторами. В данном примере мы использовали значения обычных указателей C++, которые, в общем-то, являются частным случаем итераторов.

Первый параметр — это итератор (то есть в данном случае — указатель) первого значения, которое нужно проверять. Второй параметр — итератор последней позиции (на самом деле он указывает на следующую позицию за последним нужным значением). Так как всего в нашем массиве 8 элементов, это значение равно первой позиции, увеличенной на 8. Это называется «значение после последнего».

Используемый при этом синтаксис является вариацией на тему обычного

синтаксиса цикла for в C++:

for(int j=0; j<8; j++) //от 0 до 7

{

if(arr[j] == 33)

{

cout << " Первый объект со значением 33 найден в позиции " << j << endl;

break;

}

}

Алгоритм count ()

Взглянем на другой алгоритм — count(). Он подсчитывает, сколько элементов в контейнере имеют данное значение. В примере COUNT это продемонстрировано.

Листинг 15.2. Программа COUNT

// count.cpp

// считает количество объектов, имеющих данное значение

#include <iostream>

Листинг 15.2 (продолжение)

#include <algorithm> //для count()

using namespace std;

int arr[] = { 33, 22, 33, 44, 33, 55, 66, 77 };

int main()

{

int n = count(arr, arr+8, 33); //считать, сколько раз

//встречается 33

cout << "Число 33 встречается " << n << " раз(а) в массиве." << endl;

return 0;

}

На экране в результате мы увидим следующее:

Алгоритм sort()

Листинг 15.3. Программа SORT

// sort.cpp

// сортирует массив целых чисел

#include <iostream>

#include <algorithm>

using namespace std;

// массив чисел

int arr[] = {45, 2, 22, -17, 0, -30, 25, 55};

int main()

{

sort(arr, arr+8); // сортировка

for(int j=0; j<8; j++) // вывести отсортированный

cout << arr[j] << ' '; //массив

cout << endl;

return 0;

}

Вот что мы видим на экране:

-30 -17 0 2 22 25 45 55

Алгоритм search()

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

search() ищет целую последовательность значений, заданную одним контейнером, в другом контейнере. Рассмотрим на примере.

_692________________________________________________________________

Листинг 15.4. Программа SEARCH

// search.cpp

//Ищем последовательность, заданную одним контейнером, в

// другом контейнере

#include <iostream>

#include <algorithm>

using namespace std;

int source[] = { 11, 44, 33, 11, 22, 33, 11, 22, 44 };

int pattern[] = { 11, 22, 33 };

int main()

{

int* ptr;

ptr = search(source, source+9, pattern, pattern+3);

if(ptr == source+9) // если после последнего

cout << "Совпадения не найдено\n";

else

cout << "Совпадение в позиции " << (ptr - source) << endl;

return 0;

}

Алгоритм просматривает последовательность 11, 22, 33, заданную массивом pattern, в массиве source. Видно, что эти числа подряд встречаются, начиная с четвертого элемента (позиция 3, считая с 0). Программа выводит на экран такой результат:

Совпадение в позиции 3

Если значение итератора ptr оказывается за пределами массива source, вывдится сообщение о том, что совпадения не найдено.

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

из сильных сторон STL.

Алгоритм merge()

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

Листинг 15.5. Программа MERGE

// merge.cpp

// соединение двух контейнеров в третий

#include <iostream>

#include <algorithm> //для merge()

using namespace std;

int src1[] = { 2, 3, 4, 6, 8 };

int src2[] = { 1, 3, 5 };

int dest[8];

int main()

{ //соединить src1 и src2 в dest

merge(src1, src1+5, src2, src2+3, dest);

for(int j=0; j<8; j++) // вывести dest

cout << dest[j] << ' ';

cout << endl;

return 0;

}

В итоге получается контейнер, содержимое которого таково:

1 2 3 3 4 5 6 8

Поиск по сайту: