Введение в стандартную библиотеку шаблонов С++. Описание, примеры использования, учебные задачи

 

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ  
РОССИЙСКОЙ ФЕДЕРАЦИИ 
Федеральное государственное автономное  
образовательное учреждение высшего образования 
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 
 
 
 
 
М. Э. Абрамян 

 
 
 
Введение в стандартную  
библиотеку шаблонов C++ 

 
Описание, примеры использования, учебные задачи 

 
 

 
Учебник  
 
по курсу «Стандартная библиотека C++»  
для студентов направления  
02.03.02 «Фундаментальная информатика  
и информационные технологии» (бакалавриат) 

 
 
Ростов-на-Дону – Таганрог 
Издательство Южного федерального университета 
2017 

УДК 004(075.8) 
ББК  32.973я73 
         А164 
 
Печатается по решению учебно-методической комиссии  
Института математики, механики и компьютерных наук  
им. И. И. Воровича Южного федерального университета  
(протокол № 4 от 14 апреля 2017 г.) 
 
Рецензенты: 
профессор кафедры «Информатика» Ростовского государственного  
университета путей сообщения (РГУПС), доктор технических наук 
М. А. Бутакова; 

 
доцент кафедры алгебры и дискретной математики  
Института математики, механики и компьютерных наук им. И. И. Воровича  
Южного федерального университета, кандидат физико-математических наук 
С. С. Михалкович 
 
 
Абрамян, М. Э.  
А164  
Введение в стандартную библиотеку шаблонов C++. Описание, 
примеры использования, учебные задачи : учебник / М. Э. Абрамян ; 
Южный федеральный университет. — Ростов-на-Дону ; Таганрог : 
Издательство Южного федерального университета, 2017. — 178 с. 
  
ISBN  978-5-9275-2374-0 
 
Учебник состоит из трех основных разделов. Первый раздел содержит описание 
стандартной библиотеки шаблонов C++, во втором приводятся примеры ее применения, а третий представляет собой задачник из 300 учебных заданий, охватывающих все 
разделы стандартной библиотеки. При описании библиотеки учитываются нововведения стандарта C++11. В четвертом, дополнительном разделе дается обзор средств электронного задачника Programming Taskbook for STL, позволяющих выполнять учебные 
задания более быстро и эффективно. 
Для студентов бакалавриата, обучающихся по направлению подготовки 
02.03.02 «Фундаментальная информатика и информационные технологии». 
 
УДК 004(075.8)  
ББК 32.973я73 
 
ISBN  978-5-9275-2374-0 
© Южный федеральный университет, 2017 
 
© Абрамян М. Э., 2017 

Оглавление
3

Оглавление

Предисловие ............................................................................................................................. 5
Раздел 1.
Описание библиотеки STL.................................................................................. 8

1.1. Итераторы ..................................................................................................................... 8

1.1.1. Общее описание ......................................................................................................8
1.1.2. Итераторы потоков ввода-вывода .........................................................................9

1.2. Контейнеры................................................................................................................. 10

1.2.1. Общее описание ....................................................................................................10
1.2.2. Типы, определенные в контейнерах. Параметры конструкторов ....................14
1.2.3. Функции-члены всех контейнеров......................................................................16
1.2.4. Функции-члены последовательных контейнеров..............................................17
1.2.5. Дополнительные функции-члены класса list......................................................20
1.2.6. Функции-члены ассоциативных контейнеров....................................................21
1.2.7. Вставка и удаление в последовательных контейнерах .....................................24
1.2.8. Контейнеры-адаптеры и контейнеры, добавленные в стандарт C++11...........26
1.2.9. Дополнение: обратные итераторы.......................................................................32

1.3. Алгоритмы .................................................................................................................. 34

1.3.1. Общее описание ....................................................................................................34
1.3.2. Соглашения об именовании параметров ............................................................35
1.3.3. Алгоритмы общего назначения ...........................................................................36
1.3.4. Численные алгоритмы ..........................................................................................53
1.3.5. Дополнение: итераторы вставки..........................................................................55

1.4. Стандартные функциональные объекты.................................................................. 57

1.4.1. Общее описание ....................................................................................................57
1.4.2. Функциональные адаптеры..................................................................................58
1.4.3. Функциональные объекты для арифметических и логических 
операций...........................................................................................................................60

Раздел 2.
Использование библиотеки STL....................................................................... 62

2.1. Знакомство с итераторами и алгоритмами: STL1Iter17 ......................................... 62

2.1.1. Установка задачника, создание проекта-заготовки и знакомство 
с заданием ........................................................................................................................62
2.1.2. Выполнение задания.............................................................................................68
2.1.3. Другой вариант правильного решения ...............................................................74

2.2. Работа с последовательными контейнерами: STL2Seq22...................................... 76

2.2.1. Создание проекта-заготовки и знакомство с заданием.....................................76
2.2.2. Выполнение задания.............................................................................................78

2.3. Использование алгоритмов ....................................................................................... 81

2.3.1. Преобразование списка с использованием различных видов 
итераторов: STL3Alg35 ..................................................................................................81
2.3.2. Преобразование символьных строк: STL4Str27.................................................85

2.4. Использование ассоциативных контейнеров и дополнительных видов 

функциональных объектов ........................................................................................88

2.4.1. Группировка данных с применением отображений: STL5Assoc20................. 88
2.4.2. Дополнительные виды функциональных объектов: STL6Func9 ..................... 95

2.5. Применение различных средств стандартной библиотеки C++: STL7Mix4 ......103

2.5.1. Создание проекта-заготовки и знакомство с заданием. 
Дополнительные средства окна задачника, связанные с просмотром 
файловых данных ......................................................................................................... 103
2.5.2. Выполнение задания .......................................................................................... 109
2.5.3. Другие варианты решения................................................................................. 113

Раздел 3.
Учебные задачи.................................................................................................117

3.1. Знакомство с итераторами и алгоритмами.............................................................120
3.2. Последовательные контейнеры...............................................................................125

3.2.1. Заполнение контейнеров и доступ к элементам. Обратные итераторы........ 126
3.2.2. Вставка элементов.............................................................................................. 128
3.2.3. Удаление элементов........................................................................................... 130

3.3. Обобщенные алгоритмы ..........................................................................................132

3.3.1. Алгоритмы поиска.............................................................................................. 133
3.3.2. Базовые модифицирующие алгоритмы. Итераторы вставки ......................... 136
3.3.3. Сортировка и слияние........................................................................................ 139
3.3.4. Перестановки и работа с кучей ......................................................................... 140
3.3.5. Численные алгоритмы........................................................................................ 142

3.4. Строки как последовательные контейнеры ...........................................................143
3.5. Ассоциативные контейнеры....................................................................................146

3.5.1. Множества. Теоретико-множественные алгоритмы....................................... 147
3.5.2. Отображения. Группировка и объединение данных....................................... 149

3.6. Функциональные объекты: дополнительные возможности .................................156
3.7. Применение различных средств стандартной библиотеки C++ ..........................162

3.7.1. Избранные задачи из группы STL7Mix............................................................ 163
3.7.2. Указания к задачам группы STL7Mix .............................................................. 165

Раздел 4.
Приложение. Средства ввода-вывода, реализованные в задачнике 

Programming Taskbook .........................................................................................................173

4.1. Поток ввода-вывода pt и связанные с ним итераторы ..........................................173
4.2. Вывод отладочной информации: функции Show и ShowLine..............................174
4.3. Вывод отладочной информации: вспомогательные функции..............................176

Литература ............................................................................................................................177

Предисловие
5

Предисловие

Книга, предлагаемая вашему вниманию, представляет собой практико
ориентированный учебник по стандартной библиотеке шаблонов языка
C++. Для библиотеки шаблонов часто используется название STL (Standard 
Template Library), которое является неформальным, однако позволяет отличить ее от остальных частей стандартной библиотеки C++. Начиная 
с 1998 г. библиотека STL входит в стандарт C++ ISO/IEC 14882 (C++98); 
она содержит средства для создания и преобразования различных структур 
данных и использует технологию обобщенного программирования. Архитектура библиотеки STL базируется на трех основных компонентах: контейнерах, итераторах и алгоритмах. Контейнеры предназначены для хранения наборов объектов в памяти; STL включает две группы контейнеров: 
последовательные и ассоциативные, в каждую группу входят контейнеры 
с различными свойствами, что позволяет выбирать контейнер, наиболее 
подходящий для решения поставленной задачи. Итераторы обеспечивают
унифицированные средства доступа к содержимому контейнера. Благодаря 
концепции итераторов, базирующейся на средствах обобщенного программирования, оказалось возможным реализовать универсальные алгоритмы – вычислительные процедуры, предназначенные для анализа и преобразования контейнеров. Один и тот же алгоритм может быть применен 
к любым контейнерам, обладающим требуемыми для этого алгоритма 
свойствами (точнее, имеющим итераторы того типа, который необходим 
для корректной работы алгоритма). Еще одной составной частью библиотеки STL являются функциональные объекты, представляющие собой
обобщения функций и фигурирующие во многих алгоритмах. В пересмотренном стандарте C++ ISO/IEC 14882:2011 (C++11) библиотека STL была 
дополнена рядом новых возможностей.

Библиотека STL является одной из наиболее трудных для изучения 

частей стандартной библиотеки С++. Во-первых, это достаточно большая 
часть стандартной библиотеки: она включает 5 основных видов итераторов, а также их модификации, 7 основных и ряд дополнительных контейнеров, около 70 (в стандарте C++11 – около 90) алгоритмов, большинство 
из которых реализовано в нескольких вариантах, и большое число стандартных функциональных объектов. Во-вторых, архитектура библиотеки 

STL основана на шаблонах – весьма сложном разделе языка C++ [3]. Следует заметить, что особенности механизма шаблонов языка C++ затрудняют поиск и исправление ошибок, допущенных при использовании средств 
библиотеки STL (в частности, сообщения компилятора об ошибке нередко 
связываются с фрагментами стандартного программного кода, а не с теми 
операторами разрабатываемой программы, в которых фактически была допущена ошибка). В то же время библиотека STL относится к тем основным
частям стандартной библиотеки, владение которыми является обязательным условием для квалифицированной разработки программ на языке C++.

По библиотеке STL имеется обширная учебная литература, в том чис
ле и на русском языке. Можно отметить книги [2, 4, 6, 7], целиком посвященные STL, а также соответствующие разделы в известных учебниках 
[5, 8]. Однако очень немногие издания содержат наборы упражнений, 
позволяющие закрепить полученные знания (в частности, из перечисленных книг упражнения содержат лишь учебники универсального содержания [5, 8]). При этом предлагаемые упражнения не охватывают все возможности библиотеки и являются достаточно сложными, что затрудняет 
их использование при проведении лабораторных занятий. Настоящее издание призвано восполнить этот пробел. Помимо компактного, но в то же 
время достаточно подробного описания всех элементов стандартной библиотеки шаблонов, приведенного в разделе 1, а также примеров их применения (которым посвящен раздел 2), оно содержит набор из 300 задач
по всем основным разделам стандартной библиотеки и, таким образом, позволяет не только ознакомиться с ее возможностями, но и освоить эту библиотеку на практике. Задачи разбиты на 7 групп; содержание групп, 
их особенности и формулировки всех задач приведены в разделе 3. 

В описании основных компонентов библиотеки STL учитываются но
вовведения стандарта C++11. Задания ориентированы в основном на базовый вариант библиотеки STL, соответствующий стандарту C++98, однако 
при их выполнении вполне допустимо (и более удобно) использовать новые возможности, появившиеся в стандарте C++11.

Все задачи, приведенные в книге, входят в состав электронного за
дачника Programming Taskbook for STL (PT for STL), являющегося одним из 
дополнений универсального задачника по программированию Programming Taskbook. Задачник PT for STL может использоваться совместно 
со средами программирования Microsoft Visual Studio 2008, 2010, 2012, 
2013, 2015, 2017 и Code::Blocks, начиная с версии 13. Он позволяет генерировать программы-заготовки для выбранных заданий, предоставляет 
программам наборы тестовых исходных данных, проверяет правильность 
полученных результатов, диагностирует различные виды ошибок и отображает на экране все данные, связанные с заданием. Все эти возможности 

Предисловие
7

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

Получить дополнительную информацию об электронном задачнике

Programming Taskbook и его дополнении Programming Taskbook for STL
(а также других его дополнениях) и скачать их дистрибутивы можно на 
сайте электронного задачника – http://ptaskbook.com/.

Автор считает своим приятным долгом выразить искреннюю благо
дарность Денису Владимировичу Дуброву и Артему Михайловичу Пеленицыну, которые прочитали первый вариант рукописи и высказали много 
ценных замечаний.

Раздел 1. Описание библиотеки STL

1.1. Итераторы

1.1.1. Общее описание

В библиотеке STL используются пять основных видов итераторов: 

итераторы чтения;


итераторы записи;


однонаправленные итераторы;


двунаправленные итераторы;


итераторы произвольного доступа.

Для каждого вида итераторов определен набор операций, причем дву
мя операциями, доступными для всех видов итераторов, являются операция инкремента ++, которая передвигает итератор p на следующий элемент 
последовательности (++p и p++), и операция разыменования *, возвращающая значение текущего элемента (*p и вариант p->m для доступа к члену m
разыменованного объекта).

Операция разыменования имеет следующие особенности:

в случае итераторов чтения операция * не может использоваться 
для изменения элемента;


в случае итераторов записи операция * не может использоваться 
для получения значения элемента (выражение *p можно использовать только в левой части присваивания);


для прочих итераторов операция * может использоваться как для 
получения значения элемента, так и для изменения этого значения.

Операции сравнения итераторов на равенство == и != реализованы 

для всех итераторов, кроме итераторов записи.

Для однонаправленных итераторов не определяются новые операции 

(по сравнению с итераторами чтения или записи).

Для двунаправленных итераторов в дополнение к операции инкремен
та ++ вводится операция декремента -- (также в двух видах: --p и p--).

Наконец, для итераторов произвольного доступа добавляются опера
ция индексирования [ ], позволяющая сразу обратиться к элементу последовательности с требуемым индексом (p[i]), и операция смещения на указанное количество элементов, причем в оба направления (p + i и p - i). Имеется
также операция разности двух итераторов, позволяющая определить расстояние между элементами, с которыми они связаны (p2 - p1).

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

Раздел 1. Описание библиотеки STL
9

Для итераторов, не являющихся итераторами произвольного доступа, 

также можно выполнять действия, связанные со смещением и определением расстояния, используя функции из заголовочного файла <iterator>:


advance(p, n) – передвигает итератор p на n позиций вперед (n >= 0); 
для двунаправленного итератора можно использовать n < 0 для перемещения назад;


distance(p1, p2) – возвращает расстояние между итераторами p1 и p2
(в предположении, что расстояние неотрицательно, т. е. что итератор p1 предшествует итератору p2 или совпадает с ним; для двунаправленных итераторов p2 может предшествовать итератору p1, 
в этом случае расстояние будет отрицательным).

Два итератора обычно используются для задания диапазона элемен
тов, при этом предполагается, что первый итератор (first) указывает на начальный элемент диапазона, а второй итератор (last) указывает на позицию 
за конечным элементом диапазона (причем эта позиция может не быть 
связана с существующим элементом). Чтобы подчеркнуть отмеченные 
особенности для диапазонов, определяемых итераторами, они часто записываются в виде полуинтервала [first, last) (левая граница диапазона включается, правая – нет). Полуинтервал [first, first) не содержит ни одного элемента.

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

Для всех видов итераторов определены их модификации – констант
ные итераторы, отличающиеся от обычных тем, что их разыменование 
дает константное значение.

Особыми итераторами являются итераторы потоков ввода–вывода

(см. п. 1.1.2), обратные итераторы (см. п. 1.2.9) и итераторы вставки
(см. п. 1.3.4).

1.1.2. Итераторы потоков ввода-вывода

Стандартные потоковые итераторы istream_iterator<T> и ostream_iterator<T>

(шаблонные классы) определены в заголовочном файле <iterator>.

Имеются два варианта конструктора для итератора потокового чте
ния istream_iterator: вариант с параметром-потоком stream создает итератор 
для чтения из данного потока, вариант без параметров создает итератор, 
обозначающий конец потока (все итераторы, обозначающие конец потока, 

считаются равными друг другу и не равными никаким другим итераторам 
потокового чтения). 

Ниже перечислены свойства потоковых итераторов чтения: 

тип T определяет тип элементов данных, которые считываются 
из потока;


чтение элемента из потока выполняется в начальный момент работы с итератором, а затем при каждой операции инкремента ++; 


имеются два варианта операции ++: префиксный инкремент (++p) 
и постфиксный инкремент (p++);


операция * (и ее вариант ->) возвращает последнее прочитанное 
значение, причем эту операцию можно использовать неоднократно 
для получения того же самого значения; 

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

Для итератора потоковой записи ostream_iterator<T> также определены 

два конструктора: первый конструктор содержит единственный параметр 
stream, задающий поток вывода, а второй конструктор дополнительно к параметру stream содержит второй параметр delim, задающий разделитель, который добавляется в поток вывода после каждого выведенного элемента 
(если параметр delim не указан, то между выводимыми элементами никакой 
разделитель не добавляется). 

Ниже перечислены свойства потоковых итераторов записи: 

специальный конструктор для создания итератора конца потока 
вывода не предусмотрен;


операции * и ++ не выполняют никаких действий и просто возвращают сам итератор;


операция присваивания p = выражение (где p – имя итератора записи) 
записывает значение выражения в поток вывода.

1.2. Контейнеры

1.2.1. Общее описание

Данный раздел посвящен контейнерам, входящим в стандартную биб
лиотеку шаблонов C++. Подробно описываются те основные виды последовательных и ассоциативных контейнеров, с которыми связаны задания, 
приводимые в книге: это векторы (vector), деки (deque), списки (list), множества (set), мультимножества (multiset), отображения (map) и мультиотобра

Раздел 1. Описание библиотеки STL
11

жения (multimap), а также текстовые строки (string), которые относят к псевдоконтейнерам. Другие виды контейнеров кратко описываются в п. 1.2.8: 
это контейнеры-адаптеры стек (stack), очередь (queue) и очередь с приоритетом (priority_queue), а также контейнеры, добавленные в библиотеку STL 
в стандарте C++11 (array, forward_list и ассоциативные контейнеры на базе 
хеш-функций). Все контейнеры определены в пространстве имен std. 

В таблицах 1 и 2 перечислены характеристики основных видов после
довательных и ассоциативных контейнеров. 

Таблица 1

Последовательные контейнеры

Имя
Описание
Итераторы
Заголовочный файл

vector<T>
Вектор с элементами 
типа T

Произвольного доступа
<vector>

deque<T>
Дек с элементами типа T

Произвольного доступа
<deque>

list<T>
Список с элементами 
типа T

Двунаправленные
<list>

string
Строка с элементами 
типа char

Произвольного доступа
<string>

Таблица 2

Ассоциативные контейнеры

Имя
Описание
Итераторы
Заголовочный файл

set<Key[, 
Compare]>

Множество с элементами типа Key и операцией 
сравнения Compare

Двунаправленные
<set>

multiset
<Key[, 
Compare]>

Мультимножество
с элементами типа Key
и операцией сравнения 
Compare

Двунаправленные
<set>

map
<Key, T[, 
Compare]>

Отображение с ключами типа Key, значениями 
типа T и операцией 
сравнения для ключей 
Compare

Двунаправленные
<map>

multimap
<Key, T[, 
Compare]>

Мультиотображение
с ключами типа Key, значениями типа T
и операцией сравнения 
для ключей Compare

Двунаправленные
<map>

В описаниях шаблонов контейнеров, приводимых в таблицах 1 и 2, 

и далее при описании конструкторов и функций-членов этих контейнеров 
(см. п. 1.2.2–1.2.6) не указывается дополнительный тип Alloc, который 
обычно устанавливается по умолчанию. Необязательные параметры заключаются в квадратные скобки, набранные полужирным шрифтом: [ ]. 
В частности, если в шаблоне ассоциативного контейнера не указывается 
операция сравнения Compare, то она считается равной less<Key>.

Контейнеры могут содержать данные только тех типов T, которые 

удовлятворяют некоторым естественным условиям (например, в стандарте 
C++98 требуется, чтобы для типа T был определен конструктор копирования и операция присваивания). 

Все рассматриваемые последовательные контейнеры допускают 

вставку новых элементов в любую позицию и удаление элементов из любой позиции. Векторы оптимизированы для быстрого (за константное 
время) выполнения операций вставки и удаления, связанных с концом последовательности элементов (функции-члены push_back и pop_back), а деки –
для операций, связанных как с началом, так и с концом последовательности (функции-члены push_back и pop_back, push_front и pop_front). В то же 
время, векторы обладают рядом особенностей, отсутствующих у деков; 
в частности, они имеют такую характеристику, как емкость, которая доступна и для чтения (функция-член capacity) и для изменения (функциячлен reserve). Текстовые строки string обладают возможностями, аналогичными возможностям векторов с символьными элементами. Списки позволяют выполнять быструю вставку и удаление элементов для любой позиции, однако доступ к элементу списка по его номеру требует линейного 
времени (т. е. зависит от текущего размера списка). По этой причине для 
списков не реализована операция индексирования, а связанные со списками итераторы являются двунаправленными (а не итераторами произвольного доступа, как для всех остальных последовательных контейнеров). 
Еще одной особенностью списка является то, что операции вставки и удаления не влияют на корректность итераторов и ссылок, связанных с другими его элементами, в то время как для векторов и деков вставка или удаление элементов может приводить к тому, что некоторые (или все) итераторы и/или ссылки окажутся недействительными (подробности приведены 
в п. 1.2.7). Кроме того, для списков предусмотрен набор дополнительных 
функций-членов, отсутствующих у других последовательных контейнеров 
и представляющих собой оптимизированные реализации соответствующих 
алгоритмов (см. п. 1.2.5).

Все рассматриваемые ассоциативные контейнеры хранят последова
тельности своих элементов в отсортированном виде. Сортировка выполняется по ключу, причем для множеств и мультимножеств ключами выступают сами элементы (типа T), а в отображениях и мультиотображениях