Введение в стандартную библиотека шаблонов (STL): контейнеры, алгоритмы, итераторы

Термин структура данных говорит о том, как хранится информация в памяти компьютера, а алгоритм — как эта информация обрабатывается.

Классы C++ предоставляют прекрасный механизм для создания библиотеки структур данных. В прошлом производители компиляторов и разные сторонние разработчики ПО предлагали на рынке библиотеки классов-контейнеров для хранения и обработки данных. Теперь же в стандарт C++ входит собственная встро-

енная библиотека классов-контейнеров. Она называется Стандартной библиотекой шаблонов (в дальнейшем мы будем употреблять сокращение STL) и разрботана Александром Степановым и Менг Ли из фирмы Hewlett Packard. STL — то часть Стандартной библиотеки классов C++, которая может использоваться в качестве этакой повседневной палочки-выручалочки для хранения и обработ-

ки данных.

Введение в STL

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

Контейнер — это способ организации хранения данных. В предыдущих главах нам уже встречались некоторые контейнеры, такие, как стек, связный список, очередь. Еще один контейнер — это массив, но он настолько тривиален и популярен, что встроен в C++ и большинство других языков программирования. Контейнеры бывают самые разнообразные, и в STL включены наиболее по-

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

Под алгоритмами в STL подразумевают процедуры, применяемые к контейнерам для обработки их данных различными способами. Например, есть алгоритмы сортировки, копирования, поиска и объединения. Алгоритмы представлены в STL в виде шаблонных функций. Однако они не являются методами лассов-контейнеров. Наоборот, это совершенно независимые функции. На самом деле, одной из самых привлекательных черт STL является универсальность ее алгоритмов. Их можно использовать не только в объектах классов-контейнеров, но и в обычных массивах и даже в собственных контейнерах. (Контейнеры, тем

не менее, содержат методы для выполнения некоторых специфических задач.)

Некоторые типичные алгоритмы STL

Алгоритм Назначение

find Возвращает первый элемент с указанным значением

count Считает количество элементов, имеющих указанное значение

equal

Сравнивает содержимое двух контейнеров и возвращает true, если все

соответствующие элементы эквивалентны

search

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

copy

Копирует последовательность значений из одного контейнера в другой (или в другое место того же контейнера)

swap Обменивает значения, хранящиеся в разных местах

iter_swap Обменивает последовательности значений, хранящиеся в разных местах

fill Копирует значение в последовательность ячеек

sort Сортирует значения в указанном порядке

merge

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

accumulate Возвращает сумму элементов в заданном диапазоне

for_each Выполняет указанную функцию для каждого элемента контейнера

Допустим, вы создаете массив типа int со следующими данными:

int arr[8] = {42, 31, 7, 80, 2, 26, 19, 75};

Применим алгоритм sort() для сортировки массива:

sort(arr, arr+8);

где arr — это адрес начала массива, arr+8 — адрес конца (элемент, располагающийся позади последнего в массиве).

Алгоритм 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;

}

_690________________________________________________________________

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

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

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

стереосистемы или компьютер с его периферией.

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