АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I Введение
  2. I ВВЕДЕНИЕ.
  3. I. ВВЕДЕНИЕ
  4. I. ВВЕДЕНИЕ В ИНФОРМАТИКУ
  5. IDL-описаниеи библиотека типа
  6. Библиотека
  7. Библиотека для чтения» О. И. Сенковского. Тип, структура, направление журнала.
  8. Библиотека инструкций по охране труда (полный список всех инструкций)
  9. Библиотека образов Microsoft Office
  10. В Конституции (Введение), в Уставе КПК, других партийных до-
  11. В раздел библиотека
  12. Введение

 

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

Классы 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, поскольку они связывают алгоритмы с контейнерами. Их можно представить себе в виде кабеля, связывающего колонки вашей

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

 

...

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 |



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)