close

Вход

Забыли?

вход по аккаунту

?

Bukunov Sozd pril STL

код для вставкиСкачать
С. В. БУКУНОВ, О. В. БУКУНОВА
СОЗДАНИЕ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ
ПРИЛОЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ
СТАНДАРТНЫХ БИБЛИОТЕК КЛАССОВ.
БИБЛИОТЕКА STL
Министерство образования и науки
Российской Федерации
Санкт-Петербургский государственный
архитектурно-строительный университет
С. В. БУКУНОВ, О. В. БУКУНОВА
СОЗДАНИЕ ОБЪЕКТНООРИЕНТИРОВАННЫХ ПРИЛОЖЕНИЙ
С ИСПОЛЬЗОВАНИЕМ СТАНДАРТНЫХ
БИБЛИОТЕК КЛАССОВ.
БИБЛИОТЕКА STL
Учебное пособие
Санкт-Петербург
2018
УДК 004.42
Рецензенты: д-р физ.-мат. наук, профессор Б. Г. Вагер (СПбГАСУ);
канд. техн. наук, доцент Т. Н. Костюнина (Международный банковский институт)
Букунов, С. В.
Создание объектно-ориентированных приложений с использованием стандартных библиотек классов. Библиотека STL : учеб. пособие / С. В. Букунов, О. В. Букунова; СПбГАСУ. – СПб., 2018. – 103 с.
ISBN 978-5-9227-0854-8
Содержит основные сведения по созданию приложений с использованием стандартной библиотеки шаблонных классов С++ (библиотеки STL).
Рассматриваются основные сущности библиотеки: алгоритмы, контейнеры
и итераторы. Основное внимание уделяется вопросам их применимости для
обработки данных различных типов.
Представлены необходимый теоретический материал, упражнения
и примеры программ с подробными комментариями, даны задания для самостоятельной работы.
Предназначено для студентов старших курсов, обучающихся по специальности «Прикладная математика и информатика».
Табл. 12. Ил. 95. Библиогр.: 3 назв.
Рекомендовано Учебно-методическим советом СПбГАСУ в качестве
учебного пособия.
ISBN 978-5-9227-0854-8
© С. В. Букунов, О. В. Букунова, 2018
© Санкт-Петербургский государственный
архитектурно-строительный университет, 2018
ВВЕДЕНИЕ
Настоящее пособие предназначено для студентов 4-го курса
специальности «Прикладная математика и информатика», изучающих предмет «Объектно-ориентированное программирование».
В нем излагается третья часть курса, посвященная использованию стандартной библиотеки шаблонных классов С++ при написании компьютерных программ.
Для хранения и обработки различных типов данных с помощью компьютеров используются примерно одинаковые способы.
Классы C++ предоставляют прекрасные возможности для создания библиотеки структур данных. Термин «структура данных»,
как правило, подразумевает способ хранения информации в памяти компьютера. Для описания способа обработки информации
обычно используют понятие «алгоритм».
Если раньше на рынке программного обеспечения предлагались библиотеки от разных производителей, то в настоящее время
в стандарт C++ входит собственная встроенная библиотека классов-контейнеров для хранения и обработки данных – стандартная
библиотека шаблонов (STL – Standard Template Library). STL – это
часть стандартной библиотеки классов C++, которая может использоваться для хранения и обработки данных различных типов.
Использование готовых структур и методов обработки данных существенно упрощает и ускоряет процесс создания приложений, поскольку программист избавляется от необходимости
изобретать велосипед и может сосредоточить основные усилия
на решении конкретной прикладной задачи. В результате программы, написанные с использованием стандартных библиотек
классов, получаются более компактными и, как правило, более
эффективными, а время, затраченное на их создание, оказывается существенно меньше, чем в случае самостоятельной разработки всех блоков.
5
Введение
Важное преимущество STL при создании приложений заключается в том, что это библиотека именно шаблонных классов,
т. е. в контейнерах STL могут храниться и обрабатываться данные
как стандартных, так и нестандартных (созданных самим пользователем) типов. Сочетание этой возможности с механизмом перегрузки стандартных операций для нестандартных типов данных
делает библиотеку STL мощным и эффективным средством для
разработки приложений на языке С++.
В свое время библиотека STL произвела настоящий переворот
в программировании на С++, однако ее освоение традиционно
считается весьма сложной задачей.
Цель настоящего пособия заключается в ознакомлении студентов с основными сущностями библиотеки STL, такими как
контейнеры, алгоритмы и итераторы, и выработке навыков создания с их помощью эффективных объектно-ориентированных
программ.
Для написания всех программ использовалась интегрированная среда разработки Microsoft Visual Studio.
6
Глава 1. ОСНОВНЫЕ СУЩНОСТИ STL
Библиотека STL работает с несколькими основными сущностями. К наиболее важным из них относятся:
• контейнеры;
• алгоритмы;
• итераторы.
Контейнер – это структура для хранения данных. Различные
контейнеры отличаются способами организации хранения данных. Существует достаточно большое количество разнообразных
контейнеров: стек, связный список, очередь и др. Самый популярный (и в то же время тривиальный) контейнер – это массив,
поэтому он является встроенным как в C++, так и в большинстве
других языков программирования. Контейнеры STL подключаются к программе с помощью шаблонных классов, следовательно
в них могут храниться данные любого типа – как стандартного,
так и пользовательского.
Алгоритмы – это процедуры, которые применяются к контейнерам для обработки содержащихся в них данных различными
способами. К наиболее популярным алгоритмам относятся сортировка, копирование, поиск, объединение, удаление, замена
данных. Алгоритмы представляют собой шаблонные функции,
не являющиеся методами классов-контейнеров (т. е. это независимые функции).
Одна из отличительных особенностей STL состоит в универсальности ее алгоритмов, которые можно использовать не только в объектах классов-контейнеров, но и в обычных массивах,
и в собственных контейнерах.
Итераторы – это ключевая часть STL, они связывают алгоритмы и контейнеры. Итераторы представляют собой обобщение
концепции указателей: они ссылаются на элементы контейнера,
их можно инкрементировать и т. д.
7
Глава 1. Основные сущности STL
Связи между тремя основными компонентами STL показаны
на рис. 1.1.
1.1. Контейнеры
К ассоциативным контейнерам относятся:
• множества;
• мультимножества;
• отображения;
• мультиотображения.
1.1.1. Последовательные контейнеры
Контейнеры представляют собой структуры для хранения данных. Тип данных не имеет значения – в контейнерах могут храниться как данные базовых типов (int, float и т. д.), так и объекты
различных пользовательских классов.
В STL содержатся семь основных типов контейнеров и три
производных типа.
Контейнеры STL подразделяются на две группы:
• последовательные;
• ассоциативные.
К последовательным контейнерам относятся:
• векторы;
• списки;
• очереди с двусторонним доступом.
Наследниками последовательных контейнеров выступают:
• стек;
• очередь;
• приоритетная очередь.
В последовательных контейнерах данные хранятся в ряд,
т. е. друг за другом. Каждый элемент связан с другим посредством номера своей позиции в ряду. Все элементы, кроме последнего, имеют по одному соседу с каждой стороны.
В STL реализованы три вида последовательных контейнеров:
• вектор;
• список;
• очередь с двусторонним доступом.
К последовательным контейнерам можно также отнести
и обычные массивы. Но у них имеется целый ряд недостатков,
основные из которых:
• потеря памяти (зарезервированный объем памяти превышает реальные потребности программы);
• переполнение (зарезервированный объем памяти недостаточен для удовлетворения потребностей программы);
• необходимость сдвига элементов массива при добавлении
нового элемента в произвольное место списка или удалении элемента из произвольного места.
Контейнер «вектор» лишен первых двух недостатков массивов,
поскольку в нем не нужно заботиться о размерах контейнера, а контейнер «список» избавлен от третьего недостатка, так как основан
на идее связного списка и позволяет решить проблему добавления
новых данных простой перестановкой нескольких указателей.
Контейнер «очередь с двусторонним доступом» представляет
собой комбинацию стека и обычной очереди, т. е. в нем реализован комбинированный порядок обмена данными: добавлять элементы и извлекать их можно с обеих сторон.
Сравнительный анализ последовательных контейнеров STL
и обычных массивов представлен в табл. 1.1.
8
9
Рис. 1.1
1.1. Контейнеры
Глава 1. Основные сущности STL
1.1. Контейнеры
Таблица 1.1
Сравнение последовательных контейнеров STL
и обычных массивов
Контейнер
Обычный
массив
Вектор
Список
Очередь
с двусторонним
доступом
Характеристика
Достоинства
Недостатки
Фиксированный размер
Быстрый случайный Медленные вставдоступ (по индексу) ка и извлечение данных из середины.
Размер не может
быть изменен
в процессе работы
программы
ПерераспреБыстрый случайный Медленные вставка
деляемый рас- доступ (по индексу). и извлечение данширяемый
Быстрые вставка
ных из середины
массив
и извлечение данных из конца
Аналог связБыстрый доступ
Медленный слуного списка
к обоим концам.
чайный доступ
Быстрые вставка и извлечение
данных из любого
места
Аналог векто- Быстрый случайный Медленные вставка
ра, но доступ доступ.
и извлечение данс обоих конБыстрые вставка
ных из середины
цов
и извлечение данных из начала или
конца
Практическая реализация контейнера STL достаточно проста.
Для этого необходимо:
• включить в программу нужный заголовочный файл;
• указать, какого типа данные будут храниться в контейнере.
Пример 1.1
10
Пример 1.2
Замечание. Как видно из приведенных выше примеров, отличительная особенность контейнеров STL заключается в отсутствии необходимости указывать их размер. Контейнеры сами
заботятся о размещении своих данных в памяти компьютера.
1.1.2. Ассоциативные контейнеры
В ассоциативных контейнерах данные располагаются не последовательно. Доступ к ним осуществляется посредством ключей.
Ключи – это атрибуты, которые используются для упорядочивания данных и модифицируются контейнерами автоматически.
Как правило, это просто номера строк. Если известен ключ, то
доступ к данным осуществляется очень легко: вводится нужное
слово (значение ключа), а контейнер конвертирует его в адрес
элемента в памяти.
В STL реализованы ассоциативные контейнеры двух типов:
• множества;
• отображения.
Данные в них хранятся в виде дерева, что позволяет быстро
осуществлять вставку, удаление и поиск. Но выполнять сортировку и другие операции, требующие случайного доступа к данным,
в таких контейнерах неудобно.
Контейнер «множество» является наиболее популярным (очевидно, из-за относительной простоты). Множество хранит набор
элементов, содержащих ключи. Например, оно может хранить
объекты класса person, которые упорядочиваются по алфавиту.
Роль ключа при этом может играть поле name. Такая организация
данных позволяет очень быстро найти нужный объект, осуществляя поиск по его имени (ищем объект класса person по атрибуту
name). Если во множестве хранятся значения одного из базовых
типов данных (int, float и др.), ключом является сам элемент.
В контейнере «отображение» хранятся пары объектов. Один
элемент состоит из двух «атрибутов»: ключевого объекта
11
Глава 1. Основные сущности STL
1.1. Контейнеры
и целевого (ассоциированного) объекта. Такая конструкция часто
используется в качестве контейнера, несколько напоминающего массив. Разница заключается в том, что доступ к данным осуществляется не по номеру элемента, а по специальному индек­су
произвольного типа. При этом ключевой объект служит индексом, а целевой объект – значением этого индекса.
Контейнеры «множество» и «отображение» разрешают сопоставлять одному ключу только одно значение. Это может подходить,
например, для хранения списков работников, в которых каждому
имени сопоставляется уникальный идентификационный номер.
Контейнеры «мультимножество» и «мультиотображение» позволяют хранить несколько значений для одного ключа: так, ключевому слову в словаре может быть сопоставлено несколько статей.
Характеристики всех ассоциативных контейнеров STL представлены в табл. 1.2.
Ассоциативные контейнеры STL
Контейнер
Множество
Мультимножество
Отображение
Мультиотображение
Таблица 1.2
Характеристика
Хранит только ключевые объекты. Каждому ключу
соответствует одно значение
Хранит только ключевые объекты. Одному ключу
может быть сопоставлено несколько значений
Ассоциирует ключевой объект с целевым объектом, хранящим значение. Одному ключу соответствует одно значение
Ассоциирует ключевой объект с целевым объектом, хранящим значение. Одному ключу может
быть сопоставлено несколько значений
Процессы создания ассоциативных и последовательных контейнеров аналогичны.
Пример 1.3
Пример 1.4
1.1.3. Методы
Для выполнения простых операций, специфичных для конкретных контейнеров, применяются различные методы. Общее
число методов, используемых в контейнерах или категориях контейнеров, достаточно велико. Наиболее распространенные методы, имена и назначения которых одинаковы для большинства
классов контейнеров, представлены в табл. 1.3.
Таблица 1.3
Наиболее популярные методы контейнеров
Метод
Назначение
size()
Возвращает количество элементов в контейнере
empty()
Возвращает true, если контейнер пуст
max_size() Возвращает максимально допустимый размер контейнера
begin()
Возвращает итератор на начало контейнера (итерации
будут производиться в прямом направлении)
end()
Возвращает итератор на последнюю позицию в контейнере (итерации в прямом направлении будут закончены)
rbegin()
Возвращает реверсивный итератор на последнюю позицию в контейнере (итерации будут производиться в обратном направлении)
rend()
Возвращает реверсивный итератор на начало контейнера
(итерации в обратном направлении будут закончены)
1.1.4. Адаптеры контейнеров
На базе основных контейнеров STL при помощи так называемых адаптеров можно создавать специализированные контейнеры, обладающие более простым интерфейсом.
12
13
Глава 1. Основные сущности STL
1.2. Алгоритмы
В STL реализовано три вида специализированных контейнеров:
• стек;
• очередь;
• приоритетная очередь.
В приоритетной очереди данные загружаются с одного конца
в произвольном порядке, а извлекаются с другого конца в строгом
соответствии с величиной хранящегося значения. При этом приоритетом обладают данные с наибольшим значением. Таким образом, приоритетная очередь автоматически сортирует хранящуюся
в ней информацию.
Характеристики специализированных контейнеров даны
в табл. 1.4.
Замечание. При построении таких конструкций необходимо
обязательно ставить пробел между двумя закрывающими угловыми скобками, иначе компилятор будет интерпретировать конструкцию >> как оператор извлечения данных из потока.
Таблица 1.4
Специализированные контейнеры STL
Контейнер
Стек
Очередь
Приоритетная очередь
Реализация
Характеристики
Реализуется, как вектор,
список или очередь с двусторонним доступом
Реализуется, как список
или очередь с двусторонним доступом
Реализуется, как вектор
или очередь с двусторонним доступом
Загрузка и извлечение данных только с одного конца
Загрузка данных с одного
конца, извлечение – с другого
Загрузка данных с одного
конца в случайном порядке, извлечение – с другого
конца, упорядоченное
Стеки, очереди и приоритетные очереди могут создаваться на
базе разных последовательных контейнеров.
В примере 1.5 показано создание объекта типа «стек», содержащего значения типа int, порожденного классом «очередь с двусторонним доступом» (deque).
Пример 1.6
1.2. Алгоритмы
Алгоритм – это функция, которая производит определенные
действия над элементами контейнера.
Алгоритмы в STL не являются ни методами шаблонных классов, ни даже дружественными функциями по отношению к контейнерам. В стандарте языка C++ алгоритмы – это независимые
шаблонные функции. Их можно использовать при работе как
с обычными массивами C++, так и с пользовательскими классами-контейнерами. Некоторые наиболее популярные алгоритмы
STL перечислены в табл. 1.5.
Таблица 1.5
Наиболее распространенные алгоритмы STL
Алгоритм
find()
count()
equal()
search()
copy()
Пример 1.5
swap()
14
Назначение
Возвращает первый элемент с указанным значением
Считает количество элементов, имеющих указанное
значение
Сравнивает содержимое двух контейнеров и возвращает true, если все соответствующие элементы эквивалентны
Ищет последовательность значений в одном контейнере, которая соответствует такой же последовательности в другом контейнере
Копирует последовательность значений из одного контейнера в другой (или в другое место того же
контейнера)
Производит обмен значений, находящихся в разных
местах
15
Глава 1. Основные сущности STL
Окончание табл. 1.5
Алгоритм
iter_swap()
fill()
sort()
merge()
accumulate()
for_each()
Назначение
Производит обмен последовательностей значений, находящихся в разных местах
Копирует значение в последовательность ячеек
Сортирует значения в указанном порядке
Комбинирует два отсортированных диапазона значений для получения наибольшего диапазона
Возвращает сумму элементов в заданном диапазоне
значений
Выполняет указанную функцию для каждого элемента контейнера
1.3. Итераторы
Итераторы – это сущности, напоминающие указатели, которые используются для получения доступа к данным в кон­тейнере.
Процесс последовательного продвижения по контейнеру от
элемента к элементу называется итерацией.
Итераторы можно инкрементировать с помощью обычного оператора ++. В результате итератор передвинется на следующий элемент
контейнера. Применяя к итератору операцию разыменовывания *,
можно получить значение элемента, на который ссылается итератор.
В STL каждый итератор представляет собой объект класса iterator.
Для разных типов контейнеров используются свои итераторы.
Существует три основных класса итераторов:
• прямые итераторы;
• двунаправленные итераторы;
• итераторы со случайным доступом.
Прямой итератор может проходить по контейнеру только в прямом направлении и при этом поэлементно. При работе
с ним можно использовать операцию инкрементирования ++. Такой итератор не может двигаться в обратном направлении и не
может быть поставлен в произвольное место контейнера.
Двунаправленный итератор может перемещаться по контейнеру в обоих направлениях с использованием как операции инкрементирования ++, так и операции декрементирования --.
16
1.3. Итераторы
Итератор со случайным доступом может как перемещаться
по контейнеру в обоих направлениях, так и вставать в произвольное место.
В STL есть еще два специализированных вида итераторов:
• входной итератор;
• выходной итератор.
Входной итератор может указывать на устройство ввода (cin
или входной файл) и последовательно считывать элементы данных в контейнер.
Выходной итератор может указывать на устройство вывода
(cout или выходной файл) и последовательно выводить элементы
данных из контейнера.
Значения основных итераторов можно сохранять, поскольку они указывают на некоторый адрес в памяти. Значения специализированных итераторов сохраняться не могут, так как эти
итераторы указывают на устройства ввода/вывода, для которых
хранить какой-то «указатель» невозможно.
Основные характеристики итераторов STL приведены в табл. 1.6.
Таблица 1.6
Характеристики итераторов STL
Итератор
Запись / чтение
Хранение
значения
Направление
Доступ
Со случайным доступом
Двунаправленный
Прямой
Запись и чтение Возможно
Оба направ- Случайления
ный
Запись и чтение Возможно
Выходной
Только запись
Входной
Только чтение
Оба направления
Только прямое
Только прямое
Только прямое
Запись и чтение Возможно
Невозможно
Невозможно
17
Линейный
Линейный
Линейный
Линейный
2.1. Алгоритм find()
Результат работы программы представлен на рис. 2.2.
Глава 2. АЛГОРИТМЫ
Алгоритмы STL выполняют различные операции над наборами данных. Они были созданы специально для контейнеров, но
могут применяться и для упрощения работы с обычными массивами C++. Изучение алгоритмов для контейнеров также способствует лучшему пониманию общих принципов обработки данных
безотносительно к контейнерам и STL.
В данной главе представлены примеры использования наиболее популярных алгоритмов STL.
2.1. Алгоритм find()
Алгоритм find() ищет первый элемент в контейнере, значение
которого равно заданному значению (рис. 2.1).
Упражнение 2.1. Применение алгоритма find()
к целочисленному массиву
Рис. 2.2
Для работы с алгоритмом find() в программе был подключен
заголовочный файл algorithm, в котором содержатся объявления
всех алгоритмов STL.
Первые два аргумента алгоритма find() определяют диапазон
просматриваемых значений. Значения задаются с помощью итераторов, функцию которых в данной программе выполняют обычные указатели С++, являющиеся частным случаем итераторов.
Первый аргумент алгоритма – это итератор, указывающий на
первое значение, которое нужно проверять. В данном случае это
указатель на начало массива, роль которого играет имя массива. Второй аргумент – это итератор, указывающий на последнюю позицию.
Фактически он указывает на позицию, следующую за последним
значением в массиве. Такое значение называется «значением после
последнего». Поскольку всего в массиве содержится NMAX элементов, это значение равно первой позиции, увеличенной на NMAX.
Замечание. Использование алгоритма find() позволяет избежать
применения в программе обычного для C++ цикла for (рис. 2.3).
Рис. 2.3
Рис. 2.1
Для данного небольшого примера такая замена может показаться непринципиальной, но на практике довольно часто удается
заменить алгоритмами очень сложные и длинные коды.
18
19
Глава 2. Алгоритмы
2.4. Алгоритм search()
2.2. Алгоритм count()
Алгоритм count() подсчитывает, сколько элементов в контейнере имеют заданное значение (рис. 2.4).
Упражнение 2.2. Применение алгоритма count()
к целочисленному массиву
Рис. 2.6
Результат работы программы представлен на рис. 2.7.
Рис. 2.4
Результат работы программы представлен на рис. 2.5.
Рис. 2.5
2.3. Алгоритм sort()
Алгоритм sort() сортирует элементы контейнера по возрастанию (рис. 2.6).
Упражнение 2.3. Сортировка целочисленного массива
с помощью алгоритма sort()
Рис. 2.7
Замечание. В STL существуют и другие варианты алгоритма
sort(), которые будут рассмотрены в следующих главах.
2.4. Алгоритм search()
Алгоритм search() ищет последовательность значений, заданную одним контейнером, в другом контейнере (рис. 2.8).
Упражнение 2.4. Поиск последовательности, заданной одним
контейнером, в другом контейнере
В данном случае алгоритм search() ищет в массиве array последовательность чисел 15, 25, 35, заданную массивом mask.
20
21
Глава 2. Алгоритмы
2.6. Функциональные объекты
Если значение итератора ptr окажется за пределами массива array, на экран будет выведено сообщение о том, что совпадения
не найдено.
Упражнение 2.5. Соединение двух контейнеров
Рис. 2.8
Результат работы программы представлен на рис. 2.9.
Рис. 2.10
Рис. 2.9
Замечание. Аргументами алгоритма search() не обязательно должны быть контейнеры одного и того же типа. Исходный
контейнер может быть, например, вектором STL, а маска поиска (в данном случае – массив mask) – обычным массивом. Такая
универсальность алгоритмов является одним из основных достоинств STL.
Результат работы программы представлен на рис. 2.11.
Рис. 2.11
2.5. Алгоритм merge()
2.6. Функциональные объекты
Алгоритм merge() работает с тремя контейнерами, объединяя
элементы из двух контейнеров в третий – целевой (рис. 2.10).
Некоторым алгоритмам в качестве аргумента требуются так
называемые функциональные объекты.
22
23
Глава 2. Алгоритмы
2.7. Пользовательские функции в роли функциональных объектов
Функциональный объект – это объект шаблонного класса, в котором имеется единственный метод: перегруженная операция ().
Использование такого объекта в алгоритме sort() позволяет, например, изменить режим сортировки (рис. 2.12).
В обычном режиме алгоритм sort() сортирует элементы контейнера по возрастанию, но использование функционального
объекта greater<>() в качестве третьего аргумента изменяет режим на сортировку по убыванию.
Упражнение 2.6. Сортировка массива по убыванию
с помощью функционального объекта
Замечания
1. Для сортировки по возрастанию в качестве третьего аргумента алгоритма sort() можно использовать функциональный
объект less<>():
2. В STL существуют и другие функциональные объекты как
для арифметических, так и для логических операций.
2.7. Пользовательские функции в роли
функциональных объектов
Рис. 2.12
Результат работы программы представлен на рис. 2.13.
Функциональные объекты могут работать только с базовыми
типами данных языка C++ и с классами, для которых определены соответствующие операторы (+, –, <, == и т. д.). Если необходимо применить алгоритмы STL к данным других типов, можно
определить собственную пользовательскую функцию для функционального объекта.
Например, оператор < не определен для обычных строк типа
char*. Чтобы применить алгоритм sort() для сортировки таких
строк, можно написать функцию, выполняющую сравнение,
и использовать ее адрес (имя) вместо функционального объекта
(рис. 2.14).
Упражнение 2.7. Сортировка массива строк с помощью
пользовательской функции сравнения
Рис. 2.13
В данной программе третьим аргументом алгоритма sort()
является адрес функции text_comp(), которая сравнивает две
24
25
Глава 2. Алгоритмы
2.8. Алгоритмы с окончанием _if
строки типа char* и возвращает true или false в зависимости от
того, правильно ли для них осуществлена лексикографическая
сортировка.
Результат работы программы представлен на рис. 2.15.
Упражнение 2.8. Сортировка массива строк с помощью
функционального объекта класса string
Рис. 2.16
Рис. 2.14
Результат работы программы представлен на рис. 2.17.
Рис. 2.17
Рис. 2.15
2.8. Алгоритмы с окончанием _if
Замечание. На самом деле писать собственные функциональные объекты для работы с текстом не обязательно. Для этого достаточно использовать класс string из стандартной библиотеки
C++, поскольку в нем есть встроенные функциональные объекты, такие как less<>() и greater<>() (рис. 2.16).
Некоторые алгоритмы имеют версии с окончанием _if. Таким
алгоритмам требуется дополнительный аргумент, называемый
предикатом, который является функциональным объектом или
функцией.
Например, алгоритм find() находит все элементы контейнера,
равные заданному значению. Можно написать функцию, которая
работает с алгоритмом find_if() и находит элементы по какому-то
26
27
Глава 2. Алгоритмы
2.9. Алгоритм for_each()
дополнительному признаку. В следующем упражнении для поиска в массиве строки с конкретным значением алгоритму find_if()
передается пользовательская функция is_name() (рис. 2.18).
массива, то алгоритм find_if() возвращает значение итератора
этого элемента. В противном случае возвращается указатель на
адрес «после последнего» элемента массива.
Замечание. Существуют _if-версии и других алгоритмов, например count(), replace(), remove().
Упражнение 2.9. Поиск строки в массиве типа string
с помощью алгоритма find_if()
2.9. Алгоритм for_each()
Алгоритм for_each() позволяет выполнять над каждым элементом в контейнере определенное действие, описанное в пользовательской функции. Эта функция не может изменять данные,
но может использовать их в своей работе.
В следующей программе с помощью алгоритма for_each()
осуществляется перевод значений расстояний из сантиметров
в данные типа Distance и вывод их на экран для всех элементов
массива centim[ ]. Адрес функции cent_to_dist(), которая преобразует данные из одного типа в другой, передается алгоритму
for_each() в качестве третьего аргумента (рис. 2.20).
Упражнение 2.10. Перевод значений расстояний из
сантиметров в данные типа Distance с выводом на экран
Рис. 2.18
Поскольку имя «Михаил» действительно встречается в массиве, то результат работы программы будет таким, как показано
на рис. 2.19.
Рис. 2.19
В программе адрес функции is_name() служит третьим аргументом алгоритма find_if(). Алгоритм применяет функцию is_
name() к каждому элементу массива names[ ]. Если функция
is_name() возвращает значение true для какого-либо элемента
28
29
Глава 2. Алгоритмы
Задания для самостоятельной работы
Рис. 2.20
Результат работы программы представлен на рис. 2.21.
Рис. 2.22
Рис. 2.21
2.10. Алгоритм transform()
Алгоритм transform() не только производит определенное
действие с каждым элементом контейнера, но и помещает результат в другой (или тот же) контейнер. В этом алгоритме действие,
совершаемое над данными, по-прежнему определяется пользовательской функцией, но при этом тип возвращаемого ею результата должен соответствовать типу целевого контейнера.
Программа из следующего упражнения совершает те же преобразования данных, что и в упражнении 2.10, с той лишь разницей, что вместо вывода на экран функция cent_to_dist() выводит
значения типа Distance в новый массив, а затем уже функция
main() выводит содержимое этого массива на экран (рис. 2.22).
Результаты работы программы аналогичны показанным на
рис. 2.21.
Замечание. В данной главе рассмотрена лишь незначительная часть основных алгоритмов STL. Полный список алгоритмов
STL насчитывает несколько десятков наименований [1, 2].
Задания для самостоятельной работы
Упражнение 2.11. Перевод значений расстояний из
сантиметров в данные типа Distance с выводом в новый массив
1. Составьте программу по сортировке массива значений типа
Distance с помощью алгоритма sort():
• с помощью директивы include подключите необходимые
стандартные заголовочные файлы;
• с помощью директивы include подключите заголовочный
файл, содержащий класс Distance с перегруженными операциями сравнения < и >;
• напишите пользовательскую функцию dist_comp_greater() для сравнения объектов класса Distance; подумайте, нужно
ли в данном случае создавать пользовательскую функцию dist_
comp_less(); используйте адрес (имя) пользовательской функции
в качестве третьего аргумента при вызове алгоритма sort().
В функции main():
• создайте массив объектов класса Distance (например,
с именем dist);
• с помощью алгоритма sort() реализуйте сортировку элементов массива dist сначала по возрастанию, а затем по убыванию;
30
31
Глава 2. Алгоритмы
• выведите все три массива на экран.
Возможный результат работы программы представлен на
рис. 2.23.
Задания для самостоятельной работы
Возможный результат работы программы показан на рис. 2.24.
Рис. 2.24
Рис. 2.23
2. Напишите программу, которая будет преобразовывать массив значений времени, заданных в секундах, в массив значений
типа time:
• с помощью заголовочного файла подключите разработанный ранее класс time с перегруженной операцией вставки данных в поток <<;
• напишите пользовательскую функцию, например с именем
sec_to_time(), которая будет преобразовывать значения времени
в секундах в значения типа time.
В функции main():
• создайте целочисленный массив, содержащий несколько
значений времени в секундах;
• создайте массив значений типа time;
• с помощью алгоритма transform() преобразуйте целочисленный массив в массив значений типа time, используя при этом
написанную функцию sec_to_time() в качестве четвертого аргумента алгоритма transform();
• выведите оба массива на экран.
32
33
3.1. Векторы
например, метод push_back() для векторов будет работать и со
списками, и с очередями.
Глава 3. ПОСЛЕДОВАТЕЛЬНЫЕ КОНТЕЙНЕРЫ
Контейнеры STL подразделяются на две основные категории:
• последовательные;
• ассоциативные.
Список всех контейнеров, определенных в STL, приведен в табл. 3.1.
Контейнеры STL
Контейнер
deque
Описание
Двунаправленная очередь
list
map
Линейный список
Хранит пары «ключ/значение», где
каждый ключ ассоциирован только
с одним значением
multimap
Хранит пары «ключ/значение», где
каждый ключ может быть ассоциирован с двумя или более значениями
multiset
Множество, в котором каждый элемент не обязательно уникален
priority_queue Очередь с приоритетами
queue
Очередь
set
Множество уникальных элементов
stack
Стек
vector
Динамический массив
Таблица 3.1
Требуемый
заголовок
<deque>
<list>
<map>
<map>
3.1. Векторы
Векторы – это умные динамические массивы. Они сами размещают себя в памяти и сами занимаются увеличением и уменьшением своих размеров по мере добавления или удаления данных.
Векторы в какой-то мере можно использовать как массивы, применяя при обращении к элементам массива привычный оператор
доступа по индексу[ ].
К преимуществам векторов относятся быстрый случайный доступ и добавление (или проталкивание) новых данных в конец
вектора. При добавлении нового элемента размер вектора автоматически увеличивается, чтобы положить новое значение.
3.1.1. Методы push_back(), size() и оператор [ ]
Метод push_back() вставляет значение своего аргумента в конец вектора, который располагается там, где находится самый
большой индекс (рис. 3.1).
Упражнение 3.1. Применение методов push_back(),
size() и оператора [ ]
<set>
<deque>
<deque>
<set>
<stack>
<vector>
В данной главе рассматриваются последовательные контейнеры трех типов – векторы, списки и очереди с двусторонним доступом, а также их методы.
Следует отметить, что различные контейнеры могут использовать методы с одинаковыми именами и характеристиками:
Рис. 3.1
34
35
Глава 3. Последовательные контейнеры
3.1. Векторы
В данной программе для создания вектора vec используется
конструктор вектора без параметров. Для задания типа переменных, которые будут храниться в векторе, используется шаблонный формат (в данном случае это тип int).
Замечание. Размерность вектора задавать не нужно, поэтому
вначале она равна нулю, а потом изменяется по мере добавления
элементов.
Как только в векторе появляются данные, к ним сразу же может быть получен доступ с помощью перегруженного оператора [ ], т. е. после заполнения с вектором можно работать, как
с обычным массивом.
Метод size() возвращает текущее число элементов, находящихся в контейнере, которое затем используется в цикле for для
вывода значений элементов вектора на экран.
Результат работы программы представлен на рис. 3.2.
Упражнение 3.2. Пример использования конструкторов
векторов и методов swap(), empty(), back(), pop_back()
Рис. 3.2
Замечание. Существует еще один метод – max_size(), возвращающий максимальный размер, до которого может расшириться контейнер. Это число зависит от типа хранимых данных
(чем больше места в памяти занимает один элемент данного типа, тем меньше элементов сможет поместиться в контейнер), типа контейнера и операционной системы. Например, для
вектора из упражнения 3.1 функция max_size() вернула число
1 073 741 823.
3.1.2. Методы swap(), empty(),
back(), pop_back()
В следующей программе показан пример использования еще
нескольких методов и векторов (рис. 3.3).
36
Рис. 3.3
В данной программе создаются два вектора для хранения значений типа float, а затем, после их инициализации, с помощью
метода swap() производится обмен векторов содержимым.
Программа демонстрирует два варианта инициализации векторов. Вектор v1 инициализируется значениями обычного массива, переданного ему в качестве аргумента. Инициализация
вектора v2 осуществляется путем указания его размера, равного пяти. Значение самого вектора при этом не передается – таким
образом, содержимое его неизвестно (это может быть «мусор»
или нулевые значения).
Результат работы программы представлен на рис. 3.4.
37
Глава 3. Последовательные контейнеры
3.1. Векторы
Рис. 3.4
Метод back() возвращает значение последнего элемента вектора. Метод pop_back() удаляет последний элемент вектора.
Таким образом, чтобы последовательно перемещаться по контейнеру (т. е. чтобы на каждой итерации в цикле последний
элемент вектора имел разные значения), методы back() и pop_
back() при работе с векторами всегда необходимо использовать
в паре.
Замечание. Некоторые методы, например swap(), существуют
и в виде алгоритмов. В таких случаях предпочтение, как правило, отдается методу, поскольку работа с методом для конкретного
контейнера обычно оказывается более эффективной.
3.1.3. Методы insert(), erase()
Метод insert() вставляет данные в произвольное место контейнера, а метод erase() удаляет данные из произвольной по­
зиции.
Эти методы не рекомендуется использовать с векторами, поскольку их эффективность в данном случае невысока, так как
при каждом добавлении или извлечении данных приходится пересматривать структуру всего контейнера (разжимать или
сжимать его), что сопряжено с дополнительными затратами времени. Применение этих методов может оказаться целесообразным, только если скорость работы программы не играет важной
роли (рис. 3.5).
Упражнение 3.3. Пример использования методов
insert(), erase()
Результат работы программы представлен на рис. 3.6.
Метод insert() имеет два параметра: будущее положение нового элемента в контейнере и значение элемента.
38
Рис. 3.5
Рис. 3.6
Например, чтобы заменить четвертый элемент контейнера, необходимо прибавить число 3 к индексу первого элемента вектора
(его значение, равное нулю, возвращается методом begin()). При
вставке нового элемента имеющиеся элементы от точки вставки до конца вектора сдвигаются таким образом, чтобы освободить место для вставляемого элемента. Размер контейнера после
вставки автоматически увеличивается на единицу.
Метод erase() удаляет элемент из указанной позиции. После
удаления оставшиеся элементы сдвигаются, а размер контейнера
автоматически уменьшается на единицу.
39
Глава 3. Последовательные контейнеры
3.2. Списки
3.2. Списки
Список – это контейнер STL, представляющий собой дважды
связный список, каждый элемент которого хранит указатель не
только на последующий, но и на предыдущий элемент.
Контейнер содержит адреса первого и последнего элементов
списка, поэтому доступ к обоим концам списка осуществляется
очень быстро.
3.2.1. Методы push_front(), front(), pop_front()
В программе из следующего упражнения демонстрируются
возможности методов STL по добавлению, чтению и извлечению
элементов списка (рис. 3.7).
Упражнение 3.4. Пример использования
методов push_front(), front(), pop_front()
Рис. 3.7
В данной программе начальный список формируется из элементов целочисленного массива arr[ ], а затем в него добавляются еще два элемента: один – в начало, другой – в конец. Эта
процедура повторяется дважды, но в первом случае элементы результирующего списка выводятся на экран, начиная с начала списка, а во втором случае – начиная с конца.
Результат работы программы представлен на рис. 3.8.
Рис. 3.8
Методы push_front(), front() и pop_front() аналогичны методам push_back(), back() и pop_back(), использованным в предыдущих программах при работе с векторами.
Замечания
1. Произвольный доступ к элементам списка осуществляется достаточно медленно (оператор [ ] даже не определен для
40
41
Глава 3. Последовательные контейнеры
3.3. Очереди с двусторонним доступом
списков), поэтому при его необходимости целесообразнее использовать векторы или очереди с двусторонним доступом.
Списки, как правило, применяют в случаях, когда требуются
частые операции вставки и/или удаления записей где-нибудь
в середине списка. Для этого в списке достаточно будет изменить значения нескольких указателей, а не сдвигать все элементы над точкой вставки или удаления (как в векторе или
очереди).
2. Из результатов работы программы видно, что операция вывода на экран уничтожает весь список. Несмотря на это, применение сочетания методов back() и pop_back() для извлечения
элементов из конца списка или методов front() и pop_front() для
извлечения элементов из начала списка – это единственный способ последовательного доступа к элементам списка без использования итераторов.
3.2.2. Методы reverse(), merge(), unique()
Некоторые методы используются только со списками (хотя
в отдельных случаях они могут быть заменены алгоритмами, выполняющими схожие функции).
В следующей программе демонстрируется применение методов reverse(), merge() и unique() (рис. 3.9).
Упражнение 3.5. Пример использования методов reverse(),
merge(), unique() для списков
В программе создаются два целочисленных списка: list1 и list2.
Затем с помощью метода reverse() список list1 переворачивается, чтобы элементы в нем располагались по возрастанию. Далее
посредством метода merge() производится объединение списков
с записью результата в список list1. После этого метод unique()
удаляет из списка все повторяющиеся значения. Содержимое результирующего списка выводится на экран.
Результат работы программы представлен на рис. 3.10.
Рис. 3.9
Рис. 3.10
3.3. Очереди с двусторонним доступом
Очередь с двусторонним доступом (deque) сочетает в себе
черты вектора и связного списка. С вектором ее объединяет
42
43
Глава 3. Последовательные контейнеры
поддержание произвольного доступа к элементам с помощью
оператора [ ], а со списками – возможность доступа и к началу,
и к концу очереди. В целом очередь с двусторонним доступом напоминает вектор с двумя концами. Для нее поддерживаются методы front(), push_front() и pop_front().
Резервирование компьютерной памяти для контейнеров vector и deque несколько отличается. Вектор, как и обычный массив,
всегда занимает смежные ячейки памяти, поэтому при увеличении его размера резервируется новый участок памяти, в котором
контейнер может поместиться целиком. Двусторонняя очередь,
как и связный список, может размещаться в разных участках памяти, не обязательно смежных. Благодаря этому очередь практически всегда гарантированно размещается в памяти, однако
доступ к ее сегментированным участкам осуществляется не так
быстро, как для векторов.
Максимально возможный размер контейнера vector можно узнать с помощью метода capacity(), но для контейнера deque данный метод не поддерживается, поскольку никаких перемещений
по памяти для контейнера этого типа не требуется.
В следующей программе показан пример применения некоторых рассмотренных ранее методов к контейнеру deque
(рис. 3.11).
Задания для самостоятельной работы
Рис. 3.11
В данной программе контейнер deque заполняется целочисленными элементами с двух концов, после чего производится замена четвертого элемента, а затем вставка нового элемента
в четвертую позицию. Содержимое результирующего контейнера
выводится на экран.
Результат работы программы представлен на рис. 3.12.
Упражнение 3.6. Использование методов последовательных
контейнеров для двусторонней очереди
Рис. 3.12
Задания для самостоятельной работы
1. Составьте программу по сортировке записей в файле
NAMES.TXT (отсортируйте записи по возрастанию регистрационного номера банка):
44
45
Глава 3. Последовательные контейнеры
Задания для самостоятельной работы
• считайте данные из файла NAMES.TXT и запишите их
в вектор соответствующего типа (например, с именем vname);
• напишите пользовательскую функцию, например с именем
comp_num_less(), по сортировке данных типа names по возрастанию регистрационного номера банка (поле number в структуре names);
• используя функцию comp_num_less() в качестве третьего аргумента алгоритма sort(), отсортируйте элементы вектора
vname по возрастанию регистрационного номера банка;
• с помощью еще одной функции, например write_names(),
запишите отсортированный вектор vname во внешний файл, например NAMES_sort.TXT.
Возможные результаты работы программы представлены
на рис. 3.13–3.15.
Рис. 3.13
Рис. 3.14
46
Рис. 3.15
2. Создайте программу для работы со списками сотрудников с помощью очереди с двусторонним доступом. Для этого напишите четыре функции, которые будут выполнять следующие
действия:
• считывать данные о сотрудниках из определенного файла
и записывать их в соответствующий контейнер;
• добавлять содержимое одного контейнера к содержимому
другого контейнера;
• выводить содержимое результирующего контейнера на
экран;
• выводить содержимое результирующего контейнера
в файл.
• В функции main() реализуйте:
• считывание списков сотрудников из файлов;
• запись каждого списка в отдельный контейнер типа deque
(например, deq и deq_1);
• вывод содержимого каждого контейнера на экран;
47
Глава 3. Последовательные контейнеры
• добавление содержимого контейнера deq_1 к содержимому контейнера deq;
• вывод результирующего списка из контейнера deq на экран;
• запись результирующего списка из контейнера deq в файл.
Возможные результаты работы программы показаны
на рис. 3.16, 3.17.
Глава 4. ИТЕРАТОРЫ
Итераторы – это специальные указатели. Они являются объектами специальных шаблонных классов и не зависят от типа
контейнера, на элементы которого указывают.
4.1. Общие сведения об итераторах
Рис. 3.16
Итераторы играют роль интеллектуальных указателей и мостов, соединяющих между собой контейнеры и алгоритмы, и выполняют две основные задачи:
• реализуют доступ к элементам контейнеров и работу
с ними;
• определяют совместимость конкретных алгоритмов и контейнеров.
Необходимость использования итераторов при работе с контейнерами, более сложными, чем массивы, обусловлена невозможностью применения в этих случаях обычных указателей.
4.1.1. Итераторы в роли интеллектуальных указателей
Рис. 3.17
48
Если элементы контейнера хранятся в памяти не последовательно (как у массива), а сегментированно (как у связного списка), нельзя просто инкрементировать указатель для перемещения
от элемента к элементу, необходимо идти по цепочке ссылок.
Кроме того, при изменении структуры данных контейнера (например, при добавлении или удалении элементов) обычные указатели не могут корректно сохранять информацию об адресах
элементов.
Для решения такого рода проблем в библиотеке STL созданы
специальные классы интеллектуальных указателей, объектами
которых и являются итераторы. Итераторы играют роль некоторой оболочки для методов, работающих с обычными указателями
49
Глава 4. Итераторы
4.1. Общие сведения об итераторах
(например, операций инкрементирования, декрементирования,
разыменовывания и др.). В результате перегрузки в этих классах соответствующих операторов (++, --, * и др.) все действия
с элементами контейнера осуществляются корректно даже в том
случае, если элементы расположены в памяти компьютера не последовательно или изменяют свое местоположение.
Общая схема работы интеллектуального указателя представлена на рис. 4.1.
Итераторы позволяют решать эти проблемы путем установления соответствия алгоритмов контейнерам. В этом смысле итератор можно уподобить кабелю, один конец которого вставляется
в контейнер, а другой – в алгоритм. Не каждый кабель можно воткнуть в любой контейнер и, соответственно, в любой алгоритм.
При попытке использовать слишком мощный для данного контейнера алгоритм найти подходящий итератор, скорее всего, не
удастся, о чем и будет сообщать компилятор.
В STL существует пять типов итераторов. На рис. 4.2 они показаны в порядке усложнения снизу вверх.
Итераторы случайного доступа
Двунаправленные итераторы
Прямые итераторы
Входные итераторы
Выходные итераторы
Рис. 4.1
Рис. 4.2
4.1.2. Итераторы как интерфейс между
алгоритмами и контейнерами
Входные итераторы применяются в тех случаях, когда алгоритму необходимо продвинуться на один шаг по контейнеру для
осуществления последовательного чтения данных. На практике
они используются не с контейнерами, а при чтении данных из
файлов или из потока cin.
Выходные итераторы применяются, когда алгоритму необходимо продвинуться на один шаг по контейнеру для осуществления
последовательной записи данных. На практике они используются
не с контейнерами, а при записи данных в файл или в поток cout.
Прямой итератор используется с теми алгоритмами, которым
нужно продвигаться по контейнеру в прямом направлении и совершать при этом как чтение, так и запись данных.
Двунаправленный итератор используется в тех случаях, когда алгоритму необходимо продвигаться по контейнеру как в прямом, так и в обратном направлении.
В принципе, любой алгоритм можно применить к любому контейнеру. Как правило, так и следует поступать. Более того, эта возможность является одним из основных достоинств STL. Однако
некоторые алгоритмы очень неэффективны при работе с определенными типами контейнеров. Например, алгоритму sort() требуется произвольный доступ к элементам того контейнера, который
он пытается отсортировать (в противном случае приходится проходить последовательно все элементы, пока не найдется нужный,
что при больших размерах контейнера неизбежно ведет к значительным затратам времени), а для эффективной работы алгоритма reverse() необходима возможность прохождения контейнера
как в прямом, так и в обратном направлении.
50
51
Глава 4. Итераторы
4.1. Общие сведения об итераторах
Итераторы случайного (произвольного) доступа применяются, если алгоритму нужен прямой доступ к произвольному элементу контейнера без каких-либо поэлементных движений. Эти
итераторы могут изменяться с помощью таких арифметических
выражений, как
iter = iter +5;
Замечание. Алгоритм может использовать итераторы с более
широкими возможностями, чем ему необходимо. Так, если алгоритму требуется прямой итератор, он может использовать также
двунаправленный итератор или итератор произвольного доступа.
Соответствие итераторов и поддерживаемых ими операций
показано в табл. 4.1.
Не все контейнеры STL поддерживают работу со всеми итераторами. Соответствие итераторов и основных контейнеров STL
показано в табл. 4.2.
Таблица 4.1
Соответствие итераторов и операций
Операции
Тип
итератора
Произвольного доступа
Двунаправленный
Прямой
Входной
Выходной
«Шаг впе- Чтение
Запись
«Шаг
ред» ++ value=*i *i=value назад» -+
+
+
+
+
+
+
+
+
+
+
+
+
+
Произвольный
доступ [n]
Таблица 4.2
Соответствие итераторов и основных контейнеров STL
Контейнеры
Тип
итератора
+
+
Из табл. 4.1 видно, что:
• все итераторы поддерживают операцию инкрементирования для продвижения по контейнеру в прямом направлении;
• входной итератор может использоваться с оператором *
справа от знака равенства;
• выходной итератор может использоваться с оператором *
слева от знака равенства;
• прямой итератор поддерживает и чтение, и запись данных;
• двунаправленный итератор может быть как инкрементирован, так и декрементирован;
• итератор произвольного доступа поддерживает оператор
[ ] для скоростного обращения к любому элементу контейнера.
52
4.1.3. Итераторы и контейнеры
Произвольного доступа
Двунаправленный
Прямой
Входной
Выходной
Очередь
Муль- ОтоМноВек- Спи- с двустотибражетор сок
ронним
множе- жество
доступом
ство
ние
+
Мультиотображение
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
Из табл. 4.2 видно, что векторы и очереди с двусторонним доступом могут работать с любым итератором, а списки, множества, мультимножества, отображения и мультиотображения – со
всеми итераторами, кроме итераторов произвольного доступа.
Для правильного подключения нужного итератора к контейнеру необходимо при определении итератора указать, для какого
типа контейнера он будет использоваться.
Например, если в программе определен список значений типа
person:
53
Глава 4. Итераторы
то для того, чтобы определить для него итератор, необходимо записать:
После этого STL автоматически создаст двунаправленный
итератор, поскольку именно такой итератор требуется контейнеру типа «список». Для вектора или очереди с двусторонним
доступом автоматически будет создан итератор произвольного
доступа.
Замечание. Автоматизация процесса создания итератора нужного типа достигается за счет того, что класс итератора конкретного типа является наследником класса более общего итератора:
например, итераторы для векторов и очередей с двусторонним доступом являются наследниками класса random_access_iterator,
а итераторы для списков – наследниками класса bidirectional_
iterator.
4.1.4. Итераторы и алгоритмы
4.1. Общие сведения об итераторах
Таблица 4.3
Соответствие итераторов и основных алгоритмов STL
Итераторы
Алгоритм
Входной
Выходной
for_each()
find()
count()
copy()
replace()
unique()
reverse()
sort()
nth_element()
merge()
accumulate()
+
+
+
+
+
Прямой
ПроизДвунаправвольного
ленный
доступа
+
+
+
+
+
+
+
+
Каждому алгоритму, так же как и контейнеру, в зависимости
от выполняемых функций требуется свой тип итератора. Если
нужно обращаться к произвольным элементам контейнера, то
необходим итератор произвольного доступа, а если требуется
последовательное перемещение по контейнеру от элемента к элементу, можно использовать и менее мощный прямой итератор.
Соответствие итераторов и основных алгоритмов STL показано в табл. 4.3.
Как и в случае с контейнерами, несмотря на то, что каждому алгоритму требуется определенный уровень возможностей,
более мощные итераторы всегда будут работать там, где можно
было обойтись и менее мощными. Например, алгоритму unique()
требуется прямой итератор, но он будет нормально работать
и с двунаправленным итератором, и с итератором произвольного доступа.
По табл. 4.2 и 4.3 можно определить, с какими контейнерами
будет работать тот или иной алгоритм. Так, например, из табл. 4.3
следует, что алгоритму sort() требуется итератор произвольного доступа. Из табл. 4.2 видно, что итераторы данного типа поддерживают работу только с такими контейнерами, как векторы и очереди
с двусторонним доступом. Отсюда следует, что применить алгоритм
sort() к спискам, множествам, отображениям и т. д. не получится.
Взаимодействие контейнеров, итераторов и алгоритмов схематически изображено на рис. 4.3.
Из рис. 4.3 видно, что более мощный итератор будет работать
с менее мощным алгоритмом. Обратное же неверно – более мощный алгоритм не будет работать с менее мощным итератором.
Таким образом, любой алгоритм, которому не требуется итератор произвольного доступа, будет работать с любым контейнером,
так как все контейнеры поддерживают работу с двунаправленными итераторами, которые находятся лишь на одну ступень ниже
54
55
Глава 4. Итераторы
4.2. Работа с итераторами
уровня итераторов произвольного доступа. Поскольку итераторы
произвольного доступа необходимы относительно малому числу алгоритмов, основная часть алгоритмов STL будет работать
с большинством контейнеров.
оператора [ ] (т. е. так же просто, как в обычном массиве). В контейнерах, не поддерживающих произвольный доступ (списках
и др.), доступ к данным более сложен: так, в программе из упражнения 3.4 попытка вывода на экран элементов списка приводит
к уничтожению его содержимого (пример так называемого деструктивного чтения данных).
В программе из следующего упражнения эта проблема решается с помощью итераторов (рис. 4.4).
Упражнение 4.1. Использование итератора для вывода
данных из контейнера типа «список»
Результат работы программы представлен на рис. 4.5: теперь после вывода элементов на экран содержимое списка не из­меняется.
Рис. 4.3
Замечание. Если у какого-либо контейнера есть метод, имя которого совпадает с именем одного из алгоритмов STL (например,
у множеств и отображений есть свой собственный метод find()),
то при работе с таким контейнером предпочтительнее использовать его метод, а не одноименный алгоритм.
4.2. Работа с итераторами
Работа с итераторами во многом напоминает работу с обычными указателями.
Рис. 4.4
4.2.1. Доступ к контейнеру
В контейнерах, поддерживающих работу с итераторами
произвольного доступа, итерация производится с помощью
Рис. 4.5
56
57
Глава 4. Итераторы
Из программы видно следующее:
• как и в случае с обычными указателями, перед началом использования итератор необходимо инициализировать каким-либо
значением (адресом); в данном случае инициализация осуществляется значением, возвращаемым методом begin() (т. е. указателем на начало списка);
• итератор можно инкрементировать оператором ++;
• для получения значения того элемента, на который указывает итератор, можно использовать операцию разыменовывания *;
• итератор можно сравнивать с каким-либо другим значением; в данном случае текущее значение итератора сравнивается со значением, возвращаемым методом end() (т. е. указателем
на конец списка).
4.2.2. Вставка данных в контейнер
4.2. Работа с итераторами
Рис. 4.7
4.2.3. Удаление данных из контейнера
Для удаления данных из контейнера используется метод erase().
Его аргументами могут быть итераторы, указывающие на элемент
(в случае одного аргумента) или на диапазон элементов (в случае
двух аргументов), которые необходимо удалить из контейнера.
В следующей программе из списка из четырех элементов вначале удаляется первый элемент, а затем два последних. В результате в контейнере остается только второй элемент (рис. 4.8).
Упражнение 4.3. Использование метода erase() для удаления
данных из контейнера типа «список»
Итераторы можно использовать для заполнения контейнеров
данными (рис. 4.6).
Упражнение 4.2. Использование итератора для заполнения
данными контейнера типа «список»
Рис. 4.6
Результат работы программы представлен на рис. 4.7.
58
Рис. 4.8
Результат работы программы представлен на рис. 4.9.
59
Глава 4. Итераторы
4.2. Работа с итераторами
Рис. 4.9
4.2.4. Взаимодействие итераторов
и алгоритмов
Как отмечалось выше, алгоритмы могут использовать итераторы в качестве параметров, а также возвращать их. В программе
из упражнения 4.4 показан пример применения алгоритма find()
к контейнеру типа «список» (это возможно потому, что алгоритму
требуется только входной итератор – см. табл. 4.3).
Алгоритм find() имеет три параметра: первые два – это значения итераторов, определяющие диапазон поиска, а третий – искомое значение. Если алгоритм возвращает итератор, указывающий
на конец диапазона поиска, это означает, что искомый элемент не
найден. В противном случае возвращается итератор, указывающий на искомый элемент (рис. 4.10).
Упражнение 4.4. Возвращение итератора
алгоритмом find()
Результат работы программы представлен на рис. 4.11.
Замечание. Можно ли с помощью значения итератора выяснить, какую именно позицию в контейнере занимает искомое
число 16? На первый взгляд кажется, что да: для этого достаточно
найти смещение итератора для найденного значения относительно начала диапазона. Однако компилятор расценит такую попытку как ошибку (рис. 4.12).
Причина невозможности определения позиции найденного
числа в контейнере заключается в том, что итератор, используемый для списков, может быть в лучшем случае двунаправленным
60
Рис. 4.10
Рис. 4.11
Рис. 4.12
(см. табл. 4.1), а этот тип итераторов не поддерживает арифметические операции (в частности, операцию вычитания). Такие операции поддерживают только итераторы произвольного доступа,
которые не работают со списками (см. табл. 4.1). Поэтому установление позиции искомого элемента возможно только при использовании контейнера соответствующего типа – вектора или
двунаправленной очереди, что и демонстрирует программа из
следующего упражнения (рис. 4.13).
61
Глава 4. Итераторы
4.2. Работа с итераторами
Упражнение 4.5. Использование итератора для вычисления
позиции элемента в контейнере
результирующий вектор, а только скопированный диапазон. Чтобы вывести все содержимое вектора v2 и добавлять скопированные элементы не в начало вектора, а, например, начиная со
второй позиции, необходимо внести в программу некоторые изменения (рис. 4.17).
Результат работы программы представлен на рис. 4.14.
Рис. 4.13
Рис. 4.14
В следующей программе показано применение итераторов
в качестве аргументов алгоритма copy(). В данном случае пользователь задает диапазон значений, которые должны быть скопированы из одного вектора в другой, а программа осуществляет
это копирование. Диапазон вычисляется с помощью итераторов
(рис. 4.15).
Рис. 4.15
Рис. 4.16
Упражнение 4.6. Использование итераторов
с алгоритмом copy()
Возможный результат работы программы показан на рис. 4.16.
Из рис. 4.16 видно, что на экран выводится не весь
62
Рис. 4.17
63
Глава 4. Итераторы
4.3. Специализированные итераторы
Возможный результат работы скорректированной программы
показан на рис. 4.18.
пример использования такого итератора для вывода содержимого
списка в обратном порядке (рис. 4.19).
Упражнение 4.7. Пример использования обратного итератора
Рис. 4.18
4.3. Специализированные итераторы
В STL существует два типа специализированных итераторов:
• адаптеры итераторов;
• потоковые итераторы.
Адаптеры итераторов могут модифицировать поведение обычных итераторов. В STL имеется три варианта такой модификации:
• обратный итератор – позволяет проходить контейнер
в обратном направлении;
• итератор вставки – позволяет изменять поведение отдельных алгоритмов (copy(), merge() и др.) так, чтобы они именно вставляли, а не перезаписывали данные;
• итератор неинициализированного хранения – позволяет хранить данные в участке памяти, который еще не инициали­
зирован.
Потоковые итераторы – это объекты шаблонных классов
разных типов ввода/вывода, которые позволяют интерпретировать файлы и устройства ввода/вывода (потоки cin и cout) как
итераторы и, следовательно, использовать их в качестве параметров алгоритмов.
В STL реализованы два потоковых итератора: ostream_iterator
и istream_iterator.
4.3.1. Обратные итераторы
Обратные итераторы применяются для обратного (реверсного) прохода контейнеров. В следующей программе показан
64
Рис. 4.19
Результат работы программы представлен на рис. 4.20.
Рис. 4.20
При использовании обратного итератора вместо методов
begin() и end() необходимо применять методы rbegin() и rend().
При этом значение самого итератора, так же как и при прямом
проходе, нужно инкрементировать.
4.3.2. Итераторы вставки
Итераторы вставки позволяют вставлять данные в заданное
место контейнера.
В STL существует три варианта итераторов данного типа:
• back_inserter – вставляет новые элементы в конец кон­тейнера;
• front_inserter – вставляет новые элементы в начало контейнера;
65
Глава 4. Итераторы
• inserter – вставляет новые элементы в заданное место контейнера.
В программе из следующего упражнения содержимое одного контейнера с помощью итератора вставки добавляется в конец
другого контейнера (рис. 4.21).
Замечание. Для работы с итераторами вставки необходимо
подключение заголовочного файла <iterator>.
Упражнение 4.8. Использование итератора вставки
при работе с двусторонней очередью
4.3. Специализированные итераторы
Результат работы программы представлен на рис. 4.22.
Рис. 4.22
Для вставки содержимого контейнера d2 в начало контейнера
d1 необходимо изменить в программе только одну строку:
Результат работы такой программы показан на рис. 4.23.
Рис. 4.23
Чтобы вставить содержимое контейнера d2 в произвольное
место контейнера d1 (например, начиная с третьей позиции), необходимо реализовать в программе вызов алгоритма copy() со
следующими параметрами:
Результат работы программы в этом случае показан на рис. 4.24.
Рис. 4.21
Рис. 4.24
66
67
Глава 4. Итераторы
4.3. Специализированные итераторы
С помощью итераторов вставки можно также осуществлять
вставку произвольного количества элементов контейнеров. Например, для вставки второго и третьего элементов контейнера v2
в контейнер v1 начиная с четвертой позиции необходимо реализовать в программе вызов алгоритма copy() со следующими параметрами:
Результат работы программы показан на рис. 4.25.
Рис. 4.25
Замечание. Итератор front_inserter не работает с векторами,
поскольку у них отсутствует метод push_front() и доступ возможен только к концу контейнера.
4.3.3. Выходные итераторы
Объекты класса ostream_iterator могут использоваться в качестве параметров любого алгоритма, работающего с выходным
итератором.
В следующей программе показано применение выходного итератора как параметра алгоритма copy() (рис. 4.26).
Упражнение 4.9. Пример использования
ostream_iterator
Результат работы программы представлен на рис. 4.27.
68
Рис. 4.26
Рис. 4.27
В данной программе итератор ositer, являющийся объектом
класса ostream_iterator, предназначается для вывода целочисленных значений типа int в соответствующий поток. При создании этого итератора запускается конструктор класса с двумя
параметрами: первым параметром служит выходной поток, а вторым – строка-разделитель, которая будет выводиться после каждого значения.
Значением потока, как правило, является либо имя файла,
в который будет записываться информация, либо поток cout
(при выводе информации на экран). Строка-разделитель применяется для разделения выводимых значений и может состоять из любых символов (в данном случае использован обычный
пробел).
69
Глава 4. Итераторы
4.3. Специализированные итераторы
Алгоритм copy() копирует содержимое контейнера в выходной
поток cout. Итератор выходного потока (имя объекта назначения
вывода) используется в качестве третьего аргумента алгоритма.
В следующей программе итератор выходного потока применяется для записи массива значений типа Distance из контейнера
типа «список» в файл ITER.TXT (рис. 4.28).
4.3.4. Входные итераторы
Упражнение 4.10. Использование ostream_iterator
при работе с файлом
Объекты класса istream_iterator могут использоваться в качестве параметров любого алгоритма, который работает с входным
итератором.
В следующем упражнении показано использование входных
итераторов в качестве сразу двух аргументов алгоритма copy().
В программе введенные с клавиатуры числа сохраняются в контейнере типа «список» (рис. 4.30).
Упражнение 4.11. Пример использования istream_iterator
Рис. 4.28
Результат работы программы представлен на рис. 4.29.
Рис. 4.29
Замечание. В данной программе реализация вывода в файл
значений типа Distance стала возможной благодаря тому, что операция вставки данных в поток << была перегружена для объектов
класса Distance, а сам класс подключен с помощью соответствующего заголовочного файла.
70
Рис. 4.30
Результат работы программы представлен на рис. 4.31.
Рис. 4.31
71
Глава 4. Итераторы
Задания для самостоятельной работы
В данной программе используются два входных итератора
класса istream_iterator. Первый итератор с именем cin_iter создается с помощью конструктора класса istream_iterator с одним
параметром (объектом cin). Он устанавливает связь с потоковым объектом (в данном случае – с объектом cin). Второй итератор с именем end_of_stream создается с помощью конструктора
без аргументов и предназначается для указания конца потока
данных.
Замечания
1. Для сообщения об окончании ввода данных пользователю
необходимо нажать комбинацию клавиш Ctrl+Z, в результате
чего в поток передается стандартный символ конца файла. Нажатие клавиши Enter остановит ввод чисел, но не приведет к установке признака окончания файла.
Для вывода содержимого контейнера в программе используется выходной итератор класса ostream_iterator.
2. Любые операции вывода на экран (типа: «Введите 5 чисел»
и т. п.) необходимо выполнять до определения входного итератора, так как после этого вывод любой информации на экран оказывается недоступен, поскольку программа находится в режиме
ожидания ввода данных.
В программе из следующего упражнения для считывания содержимого файла вместо потока cin используется файловый потоковый объект класса ifstream (рис. 4.32).
Упражнение 4.12. Использование istream_iterator
при работе с файлом
Результат работы программы представлен на рис. 4.33.
В данной программе для вставки считанных из файла данных
в контейнер iList используется итератор back_inserter. Это позволяет не задавать изначально размер контейнера. Как правило,
именно такой подход применяется при чтении из файлов, содержащих неизвестное количество данных.
72
Рис. 4.32
Рис. 4.33
Задания для самостоятельной работы
Составьте программу, которая будет добавлять записи в список сотрудников и удалять их оттуда с помощью итераторов.
В функции main():
• с помощью директивы #include подключите заголовочный
файл, содержащий ранее созданный класс employee;
• создайте два контейнера типа deque для хранения списков
из обоих файлов;
• с помощью потоковых итераторов класса istream_iterator
реализуйте считывание данных о сотрудниках из файлов;
• с помощью алгоритма copy() и итератора вставки запишите считанные данные в соответствующие контейнеры типа deque;
• с помощью алгоритма copy() и потокового итератора класса
ostream_iterator выведите содержимое обоих списков на экран;
• с помощью алгоритма copy() и итератора вставки добавьте содержимое контейнера с данными из файла list_1.txt в конец
контейнера с данными из файла list.txt;
73
Глава 4. Итераторы
• с помощью алгоритма copy() и потокового итератора класса ostream_iterator выведите содержимое обновленного списка
из файла list.txt на экран;
• с помощью метода erase() удалите из последнего списка
добавленные записи;
• с помощью алгоритма copy() и потокового итератора класса ostream_iterator выведите содержимое восстановленного списка из файла list.txt на экран;
• с помощью алгоритма copy() и итератора вставки добавьте
содержимое контейнера с данными из файла list_1.txt в середину
контейнера с данными из файла list.txt;
• с помощью алгоритма copy() и потокового итератора класса ostream_iterator выведите содержимое обновленного списка
из файла list.txt на экран.
Возможный результат работы программы показан на рис. 4.34.
Рис. 4.34
74
Глава 5. АССОЦИАТИВНЫЕ
КОНТЕЙНЕРЫ
Ассоциативные контейнеры представляют собой более сложные структуры, чем последовательные контейнеры. Данные в них
хранятся не в виде линейной последовательности, а в виде дерева, таблицы и пр. Основным преимуществом ассоциативных контейнеров является высокая скорость поиска данных.
5.1. Общие сведения
В ассоциативных контейнерах поиск элементов производится
с помощью ключей, представляющих собой числа или строки, которые могут быть как атрибутом объекта в контейнере, так и самим объектом.
Все ассоциативные контейнеры STL подразделяются на две
основные категории:
• множества;
• отображения.
Во множестве хранятся объекты, содержащие ключи. Отображение можно представить в виде таблицы из двух столбцов,
в первом столбце которой хранятся объекты, содержащие ключи,
а во втором – объекты, содержащие значения.
Как множества, так и отображения могут хранить только один
экземпляр ключа. Каждому ключу соответствует свое уникальное
значение (такой подход используется, в частности, в словарях, где
каждому слову ставится в соответствие только одна статья).
Для обработки структур данных, в которых одному ключу может соответствовать несколько значений, в STL существуют еще
две разновидности ассоциативных контейнеров:
• мультимножества;
• мультиотображения.
75
Глава 5. Ассоциативные контейнеры
5.2. Множества
Ассоциативные контейнеры имеют как общие с другими
контейнерами STL методы (insert(), find() и др.), так и специфические, используемые только с контейнерами данного типа
(lower_band(), upper_band(), equal_range() и др.). Некоторые
методы в принципе не работают с ассоциативными контейнерами: например, семейство методов проталкивания и выталкивания
(push_back(), pop_back() и др.). Отсутствие необходимости в их
использовании связано с тем, что в ассоциативных контейнерах
элементы должны проталкиваться и выталкиваться в определенном порядке, но не в конец или начало контейнера.
и удалять из него данные, выводить данные с помощью итераторов и т. д.
5.2. Множества
Множества, как правило, применяются для хранения объектов пользовательских классов. Объекты в таких контейнерах упорядочены, а доступ к ним осуществляется по ключу, при этом
весь объект является ключом.
В следующей программе показан пример работы с множеством строковых объектов типа string. Для определения множества, так же как и для последовательных контейнеров,
необходимо указывать тип хранимых данных (в данном случае
это объекты стандартного класса string). Кроме того, нужно указать функциональный объект, который будет использоваться для
упорядочивания элементов множества (в данном случае выбран
функциональный объект less<> для упорядочивания строк по алфавиту) (рис. 5.1).
Замечание. Для работы с ассоциативными контейнерами
«множество» и «мультимножество» необходимо подключить заголовочный файл <set>.
Упражнение 5.1. Использование множества для хранения
объектов типа string
Рис. 5.1
Рис. 5.2
Результат работы программы представлен на рис. 5.2.
Из текста программы видно, что механизм работы с ассоциативным контейнером напоминает работу с другими контейнерами: можно инициализировать множество массивом, вставлять
Результаты работы программы показывают следующее:
• элементы множества действительно сортируются по алфавиту на этапе инициализации множества массивом;
• попытка добавить во множество уже имеющийся элемент
(имя «Сергей») оказалась неудачной (в результирующем списке
76
77
Глава 5. Ассоциативные контейнеры
5.2. Множества
это имя представлено в единственном экземпляре), поскольку,
как отмечалось выше, множество может хранить только один экземпляр ключа или ключевого объекта;
• вставка во множество нового элемента и удаление из него
одного из старых элементов не нарушили порядок следования
элементов в контейнере – все они по-прежнему отсортированы
по алфавиту.
Замечание. Конечно, на таком маленьком множестве трудно
заметить выигрыш в скорости поиска по сравнению с последовательными контейнерами, но при достаточно большом количестве
элементов эта разница будет действительно очень ощутимой.
В следующем упражнении показан пример использования методов lower_bound() и upper_bound(), которые работают только с ассоциативными контейнерами. Они позволяют выбирать
из множества элементы, расположенные в заданном диапазоне
(рис. 5.3).
Упражнение 5.2. Работа с диапазонами во множестве
объектов типа string
В программе вначале на экран выводится весь список элементов множества cars (как и в упражнении 5.1, он оказывается отсортированным по алфавиту), а затем элементы множества,
входящие в заданный пользователем диапазон.
Возможный результат работы программы представлен
на рис. 5.4.
В данном случае метод lower_bound():
• принимает в качестве аргумента значение того же типа, что
и ключ;
• возвращает итератор, указывающий на первый элемент
множества, значение которого не меньше значения аргумента
(при этом чтó именно означает «не меньше», в каждом случае
определяется конкретным функциональным объектом, используемым при определении множества).
Метод upper_bound() возвращает итератор, указывающий на
элемент, значение которого больше, чем значение аргумента.
78
Рис. 5.3
Рис. 5.4
79
Глава 5. Ассоциативные контейнеры
5.3. Отображения
5.3. Отображения
его на экран. Затем на экран выводится содержимое всего отображения, т. е. все пары «модель – цена».
Результат работы программы представлен на рис. 5.6.
Отображение всегда хранит пару значений, одно из которых
представляет собой ключевой объект, а другое – объект, содержащий значение.
Ключевой объект содержит ключ, по которому ищется значение, а объект-значение – данные, которые пользователь запрашивает с помощью ключа. В ключевом объекте могут храниться
числа, строки и более сложные объекты. Значениями также могут
быть числа, строки или другие объекты, вплоть до контейнеров.
Например, ключом может быть слово, а значением – число, говорящее о том, сколько раз это слово встречалось в тексте (такое
отображение задает частотную таблицу), или список номеров
страниц книги, на которых встречается данное слово (своеобразный индекс популярности слова). Или, например, ключом может
быть число, обозначающее регистрационный номер кредитной
организации, а значением – ее наименование.
Наиболее популярным примером использования отображения
является ассоциативный массив. В отличие от обычного массива, в котором индексом элемента служит целое число, тип данных для индекса элемента ассоциативного массива может быть
произвольным.
Замечание. Для работы с ассоциативными контейнерами «отображение» и «мультиотображение» необходимо подключить заголовочный файл <map>.
Рис. 5.5
В следующем упражнении показан пример использования отображения в качестве ассоциативного массива. Ключами в программе выступают марки автомобилей, а значениями – цены на
них (рис. 5.5).
Упражнение 5.3. Использование отображения в качестве
ассоциативного массива
Рис. 5.6
При запуске данной программы пользователь вводит название
модели автомобиля, которое используется в качестве ключа для
поиска в отображении значения цены на данную модель и вывода
Замечание. Как и в предыдущих программах, список автомобилей упорядочен по алфавиту, несмотря на то что в исходном
массиве названия автомобилей не упорядочены.
80
81
Глава 5. Ассоциативные контейнеры
5.4. Мультимножества
Как видно из программы, определение отображения имеет три
шаблонных аргумента:
В следующем упражнении мультимножество используется для
хранения объектов класса person, представляющего собой виртуальный телефонный справочник (рис. 5.7). Данными класса служат фамилия, имя и телефонный номер абонента. Пользователь
взаимодействует с программой, вводя данные о нужном человеке. Результаты поиска выводятся на экран. При этом возможны
ситуации, когда два и более объектов класса имеют одинаковые
имена.
Первый аргумент задает тип ключа (в данном случае – string),
второй – тип значений, хранящихся в контейнере (в данном случае – float), а третий – порядок сортировки ключей (в данном случае – less<string>, т. е. по алфавиту).
Входные данные изначально хранятся в двух разных массивах
(в реальных проектах они могут храниться в разных файлах). Для
занесения их в контейнер используется не совсем обычный синтаксис:
Упражнение 5.4. Применение мультимножества для хранения
объектов класса person
Это напоминает заполнение простого массива, однако в данном случае индексом служит не целое число, а строка, являющаяся элементом исходного массива models[ ].
Подобный механизм используется и при получении значения
цены на заданный автомобиль:
С помощью итераторов можно получить доступ одновременно к обеим частям отображения: ключам и значениям. Ключ получают по выражению (*iter).first, а значение – по выражению
(*iter).second.
При иных вариантах обращения итератор работает в отображениях так же, как и в других контейнерах.
5.4. Мультимножества
Мультимножества применяются, как правило, для хранения
пользовательских объектов.
82
83
Глава 5. Ассоциативные контейнеры
5.5. Мультиотображения
В данной программе перегруженная операция < определяет
способ сортировки элементов мультимножества таким образом,
чтобы записи сортировались по фамилиям, а в случае их совпадения – по именам. Поскольку данные хранятся в мультимножестве, они сортируются автоматически.
Методы lower_bound() и upper_bound() позволяют выводить
все элементы мультимножества из заданного диапазона. В случае поиска повторяющихся записей (т. е. людей с одинаковыми
именами и фамилиями) верхняя и нижняя границы диапазона поиска совпадают. При этом для решения задачи создается некий
фиктивный объект searchPers с данными о человеке, указанными
в запросе пользователя.
Замечание. Поиск нужных записей во множествах и мультимножествах реализуется очень быстро.
5.5. Мультиотображения
Рис. 5.8
Мультиотображения в отличие от отображений могут содержать дублирующие значения ключей. Тип данных элементов
мультиотображений может быть любым, но, как правило, мультиотображения, как и мультимножества, используются для хранения пользовательских объектов.
В мультиотображениях реализуется автоматическая сортировка элементов по ключам, значения элементов не влияют на
ее порядок. Если критерий сортировки ключей не указан, то по
умолчанию используется критерий less<>. Поэтому, если в качестве ключей применяются объекты пользовательских типов данных (например, объекты класса person), необходимо перегрузить
операцию сравнения < для объектов пользовательского класса.
Автоматическая сортировка устанавливает важное ограничение для отображений и мультиотображений: ключ элемента нельзя изменить напрямую, так как это нарушит упорядоченность
элементов. Для изменения ключа необходимо удалить элемент со
старым ключом, а затем вставить новый элемент с новым ключом и старым значением. Таким образом, с точки зрения итератора, ключ элемента является константным, однако прямая
84
85
Рис. 5.7
Результат работы программы представлен на рис. 5.8.
Глава 5. Ассоциативные контейнеры
модификация значения элемента разрешена (если оно не принадлежит к константному типу).
Множества и мультимножества можно рассматривать как
частные случаи отображений и мультиотображений, у которых
значения элементов тождественны ключам. Следовательно, отображения и мультиотображения обладают всеми свойствами
и поддерживают все операции множеств и мультимножеств.
5.5.1. Вставка данных в мультиотображение
В отличие от отображений мультиотображения не поддерживают прямой доступ к элементам (т. е. в данном случае нельзя
использовать операцию индексирования [ ]), поэтому для обращения к ним обычно применяются итераторы. Итераторы отображений и мультиотображений, как и во всех классах ассоциативных контейнеров, являются двунаправленными.
Так как мультиотображения не поддерживают операцию индексирования [ ], вставка данных в них отличается от вставки
данных в отображения.
Существует несколько способов вставки данных в мультиотображение. Наиболее удобный из них основан на использовании функции make_pair(key, value), которая создает объект pair
из двух компонентов, передаваемых ей в аргументах key и value,
например:
Замечание. Функцию make_pair() можно использовать и для
заполнения отображений наряду с операцией индексирования [ ].
5.5.2. Удаление данных из отображения
и мультиотображения
5.5. Мультиотображения
Таблица 5.1
Функции для удаления данных из контейнеров в STL
Операция
Описание
c.erase(elem)
Удаляет все элементы со значением elem и возвращает количество удаленных элементов
c.erase(pos)
Удаляет элемент в позиции итератора pos и не возвращает значения
c.erase(beg,end) Удаляет все элементы из интервала [beg,end] и не
возвращает значения
c.clear()
Удаляет все элементы
Например, при использовании функции erase() в выражении
из мультиотображения prim будут удалены все записи, начинающиеся со слова Honda, и возвращено количество удаленных записей. Очевидно, что для отображений данная версия функции erase()
будет возвращать либо ноль (если не будет найдено ни одной записи), либо единицу (если запись с заданным ключом будет найдена).
Если мультиотображение содержит дубликаты ключей (т. е. несколько записей с одинаковыми ключами), то удалить с помощью
вышеописанной версии функции erase() только одну какую-либо
запись (например, первую) не удастся. Для решения этой задачи
можно использовать следующий подход:
Для удаления из отображения или мультиотображения всех
элементов с известным ключом достаточно вызвать функцию
erase(), имеющую в STL несколько версий (табл. 5.1).
В данном случае алгоритм find() вернет указатель на первую
найденную запись, начинающуюся со слова Honda. Этот указатель будет передан функции erase(), которая и удалит только одну
запись.
86
87
Глава 5. Ассоциативные контейнеры
5.5. Мультиотображения
В следующей программе показан пример работы с объектами
класса person с помощью мультиотображения: контейнер заполняется теми же данными, что и в упражнении 5.4, а затем из него удаляются все записи для человека, заданного пользователем (рис. 5.9).
В отличие от программы из упражнения 5.4 полями данных
класса person служат только фамилия и имя. Номер телефона не
входит в состав данных класса и передается в функцию display()
как аргумент.
Упражнение 5.5. Применение мультиотображения
для хранения объектов класса person
Рис. 5.9
Результат работы программы представлен на рис. 5.10.
Рис. 5.10
88
89
Глава 5. Ассоциативные контейнеры
5.6. Использование функциональных объектов
5.6. Использование функциональных объектов
Функциональные объекты, перечисленные в табл. 5.2, могут
работать с большинством операторов С++. Из таблицы видно, что
существуют функциональные объекты для выполнения арифметических и логических операций и операций сравнения.
В следующем упражнении показан пример использования
арифметического функционального объекта plus<>() при работе
с объектами пользовательского класса timetable в последовательном контейнере типа «список». Объекты класса timetable представляют собой значения времени в часах и минутах (без секунд)
и хорошо подходят для составления расписаний поездов, самолетов и пр. (рис. 5.11).
Основное применение функциональных объектов заключается
в передаче их алгоритмам STL в качестве аргументов.
В гл. 2 уже приводились примеры использования предопределенных функциональных объектов less<>() и greater<>() для сортировки данных соответственно по возрастанию и убыванию.
В STL существуют и другие функциональные объекты. Кроме
того, для большего контроля над алгоритмами STL можно создавать и собственные функциональные объекты.
5.6.1. Предопределенные функциональные объекты
Все предопределенные функциональные объекты расположены в заголовочном файле <functional> (табл. 5.2).
Таблица 5.2
Предопределенные функциональные объекты
Функциональный объект
Упражнение 5.6. Использование алгоритма accumulate()
и функционального объекта plus<>()
Возвращаемое значение
T = plus(T, T)
x+y
T = minus(T, T)
x–y
T = times(T, T)
x*y
T = divide(T, T)
x/y
T = modulus(T, T)
x%y
T = negate(T)
–x
bool = equal_to(T, T)
x = = y
bool = not_equal_to(T, T)
x != y
bool = greater(T, T)
x>y
bool = less(T, T)
x<y
bool = greater_equal(T, T)
x >= y
bool = less_equal(T, T)
x <= y
bool = logical_and(T, T)
x && y
bool = logical_or(T, T)
x||y
bool = logical_not(T, T)
!x
Примечания
1. Буквой Т обозначается класс, при работе с данными которого используется объект (это может быть один из базовых классов С++ либо
пользовательский класс).
2. x и y – это объекты класса Т, передаваемые в функцию в качестве
параметров.
90
91
Глава 5. Ассоциативные контейнеры
5.6. Использование функциональных объектов
В STL имеется две версии этого алгоритма:
• версия с тремя аргументами – всегда производит только
суммирование значений из заданного диапазона с помощью перегруженной операции +;
• версия с четырьмя аргументами – производит со значениями действия, определяемые функциональным объектом, передаваемым в качестве четвертого параметра.
В программе из упражнения 5.6 для реализации сложения значений типа timetable в качестве четвертого параметра алгоритма
accumulate() был использован функциональный объект plus<timetable>(). Аналогичным образом можно реализовать вычитание, умножение или деление значений типа timetable: для этого
в определение класса timetable необходимо добавить методы по
перегрузке соответствующих операций и передать алгоритму accumulate() нужный функциональный объект (в данном случае –
minus<timetable>(), times<timetable>() или divide<timetable>()).
Логические функциональные объекты, такие как logical_
and<>(), следует использовать с объектами тех классов, в которых объекты могут принимать значения типа bool.
Рис. 5.11
Результат работы программы представлен на рис. 5.12.
Рис. 5.12
В данной программе вычисляется сумма всех введенных пользователем значений типа timetable. Для этого, помимо функционального объекта plus<timetable>(), используется алгоритм
accumulate().
92
5.6.2. Собственные функциональные объекты
Если ни один из предопределенных функциональных объектов
не в состоянии обеспечить решение заданной проблемы, можно
создать свой собственный функциональный объект.
В программе из следующего упражнения показан пример использования собственных функциональных объектов в качестве
аргументов алгоритмов sort() и for_each(). Такой подход применен для сортировки списка из упражнения 5.4. Для повышения
эффективности алгоритма сортировки в контейнер типа vector
заносятся не сами объекты, а указатели на них. Хранение указателей вместо объектов оправдано в тех случаях, когда размеры
объектов достаточно велики, поскольку это позволяет избежать
копирования каждого объекта при помещении в контейнер.
Для адекватной работы алгоритма sort() с контейнером указателей в программе реализован специальный функциональный
объект, задающий порядок сортировки данных типа person.
93
Глава 5. Ассоциативные контейнеры
5.6. Использование функциональных объектов
В программе вначале создается вектор указателей на объекты класса person. Затем с помощью операции new производится
инициализация указателей адресами объектов. Инициализированные указатели заносятся в контейнер.
После этого вначале осуществляется сортировка содержимого
вектора обычным способом. В результате список данных никак
не изменяется, поскольку в этом случае происходит сортировка
не данных, а самих указателей, которые уже упорядочены при занесении в контейнер.
Затем производится сортировка содержимого контейнера с использованием собственного функционального объекта compPers().
Он упорядочивает данные списка, на которые ссылаются указатели, а
не сами значения указателей. В результате элементы списка (т. е. объекты класса person) оказываются упорядоченными по алфавиту.
Листинг программы приведен на рис. 5.13.
Упражнение 5.7. Использование собственных
функциональных объектов
Рис. 5.13
Результат работы программы показан на рис. 5.14.
94
95
Глава 5. Ассоциативные контейнеры
Задания для самостоятельной работы
Такая запись означает, что функциональный объект dispPers()
выводится для каждого элемента данных в векторе. В результате
с помощью одного вызова функции на экран выводится содержимое всего контейнера.
Замечание. Как видно, функциональные объекты могут изменять поведение контейнеров. В частности, они позволяют осуществлять сортировку данных во множестве указателей не по
адресам последних, а по их содержимому, т. е. сортировать реальные объекты, а не ссылки на них. Соответственно, если при
определении контейнера задать для него подходящий функциональный объект, то можно упорядочить содержимое контейнера,
не прибегая к использованию алгоритма sort().
Задания для самостоятельной работы
Из рис. 5.14 видно, что использование алгоритма sort() с двумя
аргументами действительно приводит только к сортировке указателей по их адресам в памяти, но никак не влияет на упорядочивание данных в списке. Однако такая сортировка требуется
крайне редко.
Для упорядочивания данных списка в программе производится
вызов алгоритма sort() с функциональным объектом compPers()
в качестве третьего аргумента. Этот объект является объектом нового класса compPers, содержащего один метод operator(), который получает в качестве аргументов два указателя на объекты
класса person, а сравнивает значения объектов, на которые они
указывают.
Кроме того, в программе не совсем обычным образом реализуется вывод содержимого контейнера на экран. Вместо простой
итерации с поэлементным выводом используется метод for_
each() с собственным функциональным объектом dispPers() в качестве третьего аргумента:
1. Составьте программу по сортировке записей в файле
NAMES.TXT с помощью контейнеров типа «отображение». Реализуйте в программе два варианта сортировки данных:
• сортировка по наименованию банка (алгоритм сортировки – по алфавиту);
• сортировка по регистрационному номеру банка (алгоритм
сортировки – по возрастанию).
Решите эту задачу с помощью отображений двух типов:
• ключами служат наименования банков, а значениями – их
регистрационные номера;
• ключами служат регистрационные номера, а значениями –
наименования банков.
Для этого создайте в программе две функции, например с именами read_names() и write_names(), которые должны работать
следующим образом:
• функция read_names() должна считывать неотсортированные данные из входного файла NAMES.TXT, записывать их в отображение и возвращать отображение с отсортированными данными;
• функция write_names() должна получать отсортированные
разными способами отображения и с помощью соответствующих
итераторов записывать данные из отображений в выходные файлы
(например, с именами NAMES_name.TXT и NAMES_numb.TXT).
96
97
Рис. 5.14
Глава 5. Ассоциативные контейнеры
Задания для самостоятельной работы
В функции main():
• объявите переменные, хранящие имена входного и выходных файлов;
• создайте два отображения разных типов, например с именами mapNames и mapNumb;
• с помощью функции read_names() считайте данные из
входного файла и запишите их в одно из отображений, например
в mapNames;
• заполните второе отображение mapNumb, переписав туда
соответствующим образом данные из первого отображения;
• с помощью функции write_names() реализуйте запись содержимого обоих контейнеров в соответствующие выходные
файлы: отображения mapNames – в файл NAMES_name.TXT,
а отображения mapNumb – в файл NAMES_numb.TXT.
Возможный результат работы программы показан на рис. 5.15–
5.18.
Рис. 5.17
Рис. 5.15
Рис. 5.16
Рис. 5.18
98
99
Глава 5. Ассоциативные контейнеры
2. Напишите программу, в которой пользователь сможет изменять номер телефона произвольного абонента. При этом выделите в самостоятельные функции следующие процедуры:
• получение данных об абоненте;
• поиск в списке старой информации об абоненте и ее удаление;
• получение нового телефонного номера абонента и занесение его в обновленный список;
• вывод содержимого списка на экран.
Для хранения данных об абонентах используйте контейнер
типа «мультиотображение», в котором ключами будут служить
объекты класса person, а значениями – строки типа string.
Реализуйте автоматическую сортировку данных в контейнере
по алфавиту.
Для удаления данных из контейнера используйте один из вариантов функции erase().
Для добавления данных в контейнер используйте функции insert() и make_pair().
Возможный результат работы программы показан на рис. 5.19.
Рекомендуемая литература
1. Мейерс С. Эффективное использование STL / С. Мейерс. – СПб. :
Питер, 2002. – 224 с. – (Серия «Библиотека программиста»).
2. Мюссер Д. Р. С++ и STL : Справочное руководство : Программирование на С++ с применением стандартной библиотеки шаблонов /
Д. Р. Мюссер, Ж. Дж. Дердж, А. Сейни. – 2-е изд. – М. : Вильямс, 2010. –
325 с.
3. Хортон А. Visual C++ 2010 : Полный курс / А. Хортон. – М. : Вильямс, 2011. – 1216 с.
Рис. 5.19
100
101
Оглавление
3.2.2. Методы reverse(), merge(), unique()...................................... 40
3.3. Очереди с двусторонним доступом........................................... 41
Задания для самостоятельной работы.............................................. 43
Оглавление
ВВЕДЕНИЕ.............................................................................................. 3
Глава 1. ОСНОВНЫЕ СУЩНОСТИ STL.............................................. 5
1.1. Контейнеры.................................................................................... 6
1.1.1. Последовательные контейнеры.............................................. 7
1.1.2. Ассоциативные контейнеры................................................... 9
1.1.3. Методы....................................................................................11
1.1.4. Адаптеры контейнеров..........................................................11
1.2. Алгоритмы.................................................................................... 13
1.3. Итераторы..................................................................................... 14
Глава 2. АЛГОРИТМЫ.......................................................................... 16
2.1. Алгоритм find()............................................................................ 16
2.2. Алгоритм count().......................................................................... 18
2.3. Алгоритм sort()............................................................................. 18
2.4. Алгоритм search()........................................................................ 19
2.5. Алгоритм merge()......................................................................... 20
2.6. Функциональные объекты.......................................................... 21
2.7. Пользовательские функции в роли функциональных
объектов........................................................................................ 23
2.8. Алгоритмы с окончанием _if...................................................... 25
2.9. Алгоритм for_each()..................................................................... 27
2.10. Алгоритм transform()................................................................. 28
Задания для самостоятельной работы.............................................. 29
Глава 3. ПОСЛЕДОВАТЕЛЬНЫЕ КОНТЕЙНЕРЫ............................ 32
3.1. Векторы........................................................................................ 33
3.1.1. Методы push_back(), size() и оператор [ ]........................... 33
3.1.2. Методы swap(), empty(), back(), pop_back()........................ 34
3.1.3. Методы insert(), erase().......................................................... 36
3.2. Списки.......................................................................................... 38
3.2.1. Методы push_front(), front(), pop_front()............................. 38
102
Глава 4. ИТЕРАТОРЫ............................................................................ 47
4.1. Общие сведения об итераторах.................................................. 47
4.1.1. Итераторы в роли интеллектуальных указателей.............. 47
4.1.2. Итераторы как интерфейс между алгоритмами
и контейнерами................................................................................ 48
4.1.3. Итераторы и контейнеры...................................................... 51
4.1.4. Итераторы и алгоритмы........................................................ 52
4.2. Работа с итераторами.................................................................. 54
4.2.1. Доступ к контейнеру............................................................. 54
4.2.2. Вставка данных в контейнер................................................ 56
4.2.3. Удаление данных из контейнера.......................................... 57
4.2.4. Взаимодействие итераторов и алгоритмов......................... 58
4.3. Специализированные итераторы............................................... 62
4.3.1. Обратные итераторы............................................................. 62
4.3.2. Итераторы вставки................................................................ 63
4.3.3. Выходные итераторы............................................................ 66
4.3.4. Входные итераторы............................................................... 69
Задания для самостоятельной работы.............................................. 71
Глава 5. АССОЦИАТИВНЫЕ КОНТЕЙНЕРЫ................................... 73
5.1. Общие сведения........................................................................... 73
5.2. Множества.................................................................................... 74
5.3. Отображения................................................................................ 78
5.4. Мультимножества........................................................................ 80
5.5. Мультиотображения.................................................................... 83
5.5.1. Вставка данных в мультиотображение................................ 84
5.5.2. Удаление данных из отображения и мультиотображения.... 84
5.6. Использование функциональных объектов............................... 88
5.6.1. Предопределенные функциональные объекты................... 88
5.6.2. Собственные функциональные объекты............................. 91
Задания для самостоятельной работы.............................................. 95
Рекомендуемая литература.................................................................... 99
103
ДЛЯ ЗАПИСЕЙ
Учебное издание
Букунов Сергей Витальевич,
Букунова Ольга Викторовна
СОЗДАНИЕ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ
ПРИЛОЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ СТАНДАРТНЫХ
БИБЛИОТЕК КЛАССОВ. БИБЛИОТЕКА STL
Учебное пособие
Редактор Т. В. Ананченко
Корректор Т. В. Ананченко
Компьютерная верстка В. Е. Королевой
Подписано к печати 21.08.2018. Формат 60×84 1/16. Бум. офсетная.
Усл. печ. л. 6. Тираж 100 экз. Заказ 96. «С» 59.
Санкт-Петербургский государственный архитектурно-строительный университет.
190005, Санкт-Петербург, 2-я Красноармейская ул., д. 4.
Отпечатано на ризографе. 190005, Санкт-Петербург, ул. Егорова, д. 5/8, лит. А.
ДЛЯ ЗАПИСЕЙ
Документ
Категория
Без категории
Просмотров
3
Размер файла
3 098 Кб
Теги
bukunov, stl, sozd, pril
1/--страниц
Пожаловаться на содержимое документа