Предисловие
Когда несколько лет назад в языке C++ появились шаблоны, лишь немногие из программистов на C++ могли предположить, какое влияние это окажет на стандарт библиотеки языка. Стандартная библиотека шаблонов (Standard Template Library) была первоначально разработана сотрудниками Hewlett-Packard А.А (читать далее...)стр. 0
STL для начинающих
1.1. Шаблоны,
пространства имен и тип bool
Как
легко догадаться из названия, стандартная библиотека шаблонов (STL) основывается на относительно новом понятии шаблона. Поэтому мы начнем с
краткого обсуждения этого предмета.
Шаблонные функции
Предположим, что для некоторого положительного числа .г (читать далее...)
стр. 1 2 3 4
1.2.
Знакомство с STL
Установив современный компилятор C++, мы можем сразу
начать использовать STL, например откомпилировать и запустить следующую программу. Эта
программа читает с клавиатуры переменное количество ненулевых целых чисел и
печатает их в том же порядке после того, как введен 0. (читать далее...)
стр. 5 6 7 8 9
1.3. Векторы,
списки и двусторонние очереди
В программе readwr.cpp три раза встречается слово vector.
#include
<vector>
vector<int> v;
vector<int>::iterator
i;
Применение концепции вектора обеспечивает выделение
непрерывной памяти, для чего программисты на С обычно пользуются
функциями malloc, realloc и free. (читать далее...)
стр. 10 11 12
1.4. Сортировка
Ниже следует расширение программы readwr.cpp, рассмотренной в начале раздела 1.2. Эта программа сортирует вектор v, то есть располагает элементы v в восходящем порядке:
// sortl.cpp: Сортировка
вектора. (читать далее...)
стр. 13 14 15
1.5. Алгоритм
find
Следующая программа показывает,
как мы можем находить требуемое значение в векторе:
// findl.cpp: Найти заданное значение в векторе. #include
<iostream> #include <vector> #include <a (читать далее...)
стр. 16
1.6. Алгоритм copy и итератор вставки
Мы можем использовать алгоритм сору для
копирования элементов одного контейнера в другой,
причем, например, источником может быть вектор, а приемником
- список, как показывает следующая программа:
// copyl.c (читать далее...)
стр. 17 18
1.8. Типы, определенные
пользователем
До сих пор все контейнеры, которые мы использовали,
содержали элементы типа int. Кроме стандартных типов, таких как int, в контейнерах STL можно
хранить типы, определенные пользователем. Так как вызов merge{.. (читать далее...)
стр. 19
1.9.
Категории итераторов
Как видно из раздела 1.4, мы можем использовать алгоритм
sort для массивов, векторов и двусторонних очередей, но не для списков.
Алгоритм find, напротив, может быть использован для всех четырех типов контейнеров. (читать далее...)
стр. 20 21 22 23
1.10. Алгоритмы replace и reverse
Алгоритм replace, упомянутый в таблице раздела 1.9, позволяет нам найти
все элементы с определенным значением в заданном контейнере и
заменить их другим значением. Следующая программа служит
иллюстрацией сказанного:
// replace.с (читать далее...)
стр. 24
1.11.
Возвращаясь к алгоритму sort
Функция qsort из стандартной библиотеки С
является достаточно общей, потому что она принимает в
качестве четвертого аргумента функцию сравнения,
определяемую пользователем. При использовании алгоритма sort в разделе 1.4 (читать далее...)
стр. 25
1.12.
Введение в функциональные объекты
Существует другой способ решения задачи сортировки из
предыдущего раздела. Хотя для такой простой задачи он и не нужен,
обсуждаемые принципы являются важными для других более сложных случаев,
поэтому не стоит пропускать этот раздел при чтении. (читать далее...)
стр. 26 27
1.13. Использование функций remove и remove_if
В этом разделе мы рассмотрим три алгоритма, используя их
для векторов, но имея в виду, что они также применимы к двусторонним очередям и
спискам.
Алгоритм findjf
В дополнение к алгоритму find, использовавшемуся в разделе 1.5 (читать далее...)
стр. 28 29 30
1.14. Класс auto_ptr
После того как размещена динамическая память, нужно
внимательно следить за тем, чтобы она была правильно освобождена. Обычно
программисты на С используют для этого malloc и free, а программисты на C++ используют также new и delete. (читать далее...)
стр. 31 32
Другие алгоритмы и контейнеры
2.1. Алгоритм accumulate
Нахождение суммы элементов последовательности или
подпоследовательности лучше всего достигается с помощью алгоритма accumulate. Этот алгоритм вместе с некоторыми другими, которые имеют отношение
к вычислениям,
определен в заголовке numeric, а не algorithm, как большинство остальных алгоритмов. (читать далее...)
стр. 33 34
2.2. Алгоритм foreach
Мы можем использовать алгоритм for_each для вызова функции с каждым из элементов
последовательности в качестве аргумента. Вот программа, которая
демонстрирует это:
// for_each.cpp: Алгоритм for_each. (читать далее...)
стр. 35
2.3. Подсчет
Алгоритм count подсчитывает, какое количество
элементов последовательности равно заданному значению. Давайте используем этот
алгоритм для того, чтобы подсчитать, сколько раз в строке встречается буква е.
(читать далее...)
стр. 36
2.4. Функциональные объекты, определенные в STL
Напомним, что такие функции, как found (в предыдущем разделе), называются предикатами.
Они возвращают true или fake в зависимости от соблюдения некоторого
условия. Выражение greater<int>, которое встретилось нам в разделе 1.1 (читать далее...)
стр. 37 38
2.5. Введение в ассоциативные контейнеры
Кроме массивов и списков, использующихся для реализации
последовательных
контейнеров (массивов, векторов, двусторонних очередей и списков), которые обсуждались до сих пор, сбалансированные деревья представляют собой другую классическую структуру
данных, предназначенную для их эффективного хранения и извлечения.
(читать далее...)
стр. 39
2.6.
Множества и множества с дубликатами
В этом и следующем разделе мы рассмотрим по одной
простой программе для каждого из четырех ассоциативных контейнеров: эти
разделы покрывают все возможные операции с этими контейнерами не
полностью, но они поясняют
наиболее важные их характеристики.
(читать далее...)
стр. 40 41
2.7. Словари и словари с дубликатами
Словари
Происхождение термина «ассоциативный контейнер»
становится ясным, как только мы начинаем рассматривать словари. Например,
телефонный справочник связывает (ассоциирует) имена с номерами.
(читать далее...)
стр. 42 43
2.8. Пары и сравнения
Чтобы использовать словари и словари с дубликатами более
интересным способом, нам нужно познакомиться с шаблонным классом pair (пара), который полезен также и для других целей. Этот класс
использует следующая
программа:
// pairs.с (читать далее...)
стр. 44 45
2.9. Снова словари
Поскольку словарь содержит пары (k, d), где k является ключом, a d - сопутствующими данными, можно предположить, что шаблон pair будет полезен при работе со словарями. Как и для
последовательного контейнера, для ассоциативного контейнера мы можем использовать
итератор i\ в этом случае выражение *i будет обозначать пару, в которой (*i).f (читать далее...)
стр. 46 47 48 49
2.10. Функции insert
Добавление новых записей в предыдущем разделе
осуществляется с помощью оператора доступа по индексу в следующем выражении
D[p] = nr;
Вместо этого оператора присваивания мы могли бы написать выражение
D.i (читать далее...)
стр. 50 51
2.11. Удаление элементов словаря
Для
удаления элементов словаря имеются три функции-члена erase, объявленные
следующим образом:
void
erase(iterator position);
void
erase(iterator first, iterator last);
size_type
erase(const key_type &x (читать далее...)
стр. 52
2.12. Более удобные строки
До сих пор мы использовали достаточно примитивный способ
работы со строками. Например, в программе тар.срр нам необходимо было
выполнить
два оператора
delete[] (*i).first; D.erase(i);
чтобы удалить элемент множества, на который ссылался итератор
г. (читать далее...)
стр. 53 54 55 56
Последовательные контейнеры
3.1. Векторы и связанные с ними типы
Когда идет речь о шаблонах вообще и STL в частности, новички бывают сбиты с толку сложным синтаксисом этих
выражений. Мы начнем с обсуждения синтаксиса, приводя
примеры, которые не всегда имеют практическое значение, но полезны тем, что
позволяют в нем разобраться.
(читать далее...)
стр. 57 58 59
3.2. Функции capacity и reserve
До сих пор мы принимали как данность, что векторы имеют
переменный размер, не беспокоясь о том, как это реализовано. Теперь
предположим, что мы хотим добавить к вектору элемент, так что размер
этого вектора вырастет на 1. (читать далее...)
стр. 60 61 62
3.3. Обзор функций-членов класса vector
Ниже перечислены все функции-члены класса vector с кратким описанием или ссылкой на соответствующий
раздел. Эти объявления могут содержаться
в заголовке vector, хотя многие функции-члены полностью определены, а
не только
объявлены в этом заголовке.
(читать далее...)
стр. 63 64
3.4.
Двусторонние очереди
Различные
типы контейнеров очень похожи в отношении способов их применения. Например, каждый из трех типов контейнеров (vector, deque и list) определяет конструктор, который использует в качестве параметров число повторений
и значение, например:
vector<d (читать далее...)
стр. 65 66
3.5. Списки
Как известно, преимущество списков перед векторами и
двусторонними очередями заключается в том, что вставка и удаление элементов в любой
позиции происходит за постоянное время, а недостаток
заключается в отсутствии произвольного доступа к элементам. (читать далее...)
стр. 67 68 69 70
3.6. Векторы
векторов
До сих пор в наших примерах излюбленным типом был vector<int>. Вполне очевидно, что мы можем заменить int на другой тип и использовать vector<double>, vector<char> и т. п. А вправе ли мы использовать более сложный тип, чем int, double и char, между двумя угловыми скобками?
(читать далее...)
стр. 71
3.7. Как
избавиться от явного выделения памяти
Как было отмечено в разделе 1.14, в сложных программах к
частым ошибкам приводит освобождение памяти с помощью free или delete. В данных ниже определениях функций нельзя обойтись без использования
упомянутых выражений. (читать далее...)
стр. 72 73
Ассоциативные контейнеры
4.1. Введение
Из раздела 2.5 мы узнали, что существуют четыре типа
ассоциативных контейнеров: множества, множества с дубликатами, словари и
словари с дубликатами. Множества и множества с дубликатами
характеризуются двумя параметрами шаблона, а словари и словари с дубликатами -
тремя:
template
<c (читать далее...)
стр. 74 75 76
4.2.
Функции-члены множеств
У класса set имеются три конструктора, которые могут быть определены следующим образом внутри класса:
set(const Compare&
comp = Compare!)); // 1 (по умолчанию) set(const value_type* first, const value_type*
last,
const
Compare& (читать далее...)
стр. 77 78 79 80
4.3. Объединение и пересечение множеств
В этом разделе мы рассмотрим известные математические
операции нахождения пересечения и объединения двух множеств, которые
проиллюстрированы
на рисунке 4.1.
Рисунок 4.1. Пересечение и объединение двух
множеств
Для обозначения операций пересечения и объединения мы
будем использовать операторы * и +, хотя в математике обычно
используются обозначения
Пии. (читать далее...)
стр. 81 82
4.4. Отличия множеств с дубликатами от просто
множеств
Мы уже обсуждали множества и множества с дубликатами в
разделе 2.6, и не мешает снова обратиться к тексту программы multiset.cpp, приведенному в том разделе. Напомним, что каждый элемент множества
уникален, в то время как множества с дубликатами могут содержать
несколько экземпляров одинаковых элементов. (читать далее...)
стр. 83
4.5. Словари
У словарей существуют три конструктора, объявленные следующим образом:
map
(const Compares comp = Compared); // 1
тар(const value_type*
first, const value_type* last,
const
Compares comp = Compared); (читать далее...)
стр. 84 85 86
4.6. Словари с дубликатами
Как стало ясно из раздела 2.7, словари с дубликатами
отличаются от просто словарей тем, что они допускают два и более элементов с
одинаковыми ключами. Рисунок 4.4 показывает возможное представление
словаря с дубликатами. (читать далее...)
стр. 87 88
4.7. Сводный указатель
В этом разделе мы создадим приложение, использующее
концепции словаря и множества наряду с классом string, представленным в разделе 2.12. Это будет программа сводный указатель, берущая в качестве входных
данных любой текстовый файл и для каждого слова в файле
показывающая номера строк, в которых встречается это слово. (читать далее...)
стр. 89 90 91
Адаптеры контейнеров
5.1. Стеки
Стек
(stack) представляет
собой структуру данных, которая допускает только
две операции, изменяющие ее размер: push (для добавления элемента в конце) и pop (для удаления элемента в конце). Иными словами, стек работает по принципу «последний пришел - первый ушел» (также называемому LIFO от английского Last In - First Out). (читать далее...)
стр. 92 93
5.2. Очереди
Очередь (queue) является структурой данных, в
которую можно добавлять элементы с одного конца, сзади, и удалять с другого
конца, спереди. Мы можем узнать и изменить значения элементов спереди и сзади,
как показано
на рисунке 5.2 (читать далее...)
стр. 94
5.3. Очереди с приоритетами
Очередь с приоритетами (priority queue) является структурой данных, из которой, если она
не пуста, можно удалить только наибольший элемент. Как и для стеков, наиболее
важными функциями-членами являются push, pop и top. (читать далее...)
стр. 95 96
Функциональные объекты и адаптеры
6.1.
Функциональные объекты
В разделах 1.12 и 2.4 уже рассмотрены функциональные
объекты, которые зачастую бывают трудны для восприятия, поэтому мы
немного поэкспериментируем с ними вне рамок STL. Следующая программа демонстрирует класс sq, который можно использовать для вычисления значения х2
целого
числа х:
II funobjl.c (читать далее...)
стр. 97 98 99
6.2. Унарные предикаты и привязки
В математике мы можем превратить функцию двух аргументов
в функцию одного аргумента, если один из аргументов сделаем
константой. Например,
мы можем определить функцию g как
g(x)=f(x, с)
где с является константой. (читать далее...)
стр. 100
6.3. Отрицатели
Программисты часто используют унарный оператор ! (не).
Например, выражение
!(х < у)
эквивалентно
х >= у
Подобным же образом на функции двух аргументов действует
отрицатель not2. (читать далее...)
стр. 101
6.4. Два
полезных базовых класса STL
Могли ли мы найти более простой пример для обсуждения
адаптера notl, чем
sort(a, a+5,
not2(less<int>())) ;
встречающийся в программе not2demo.cpp в предыдущем разделе? В частности, можем ли мы применить notl к написанному нами функциональному объекту, например, таким образом:
sort(a, a+5,
not2(iLessThen())) ;
(читать далее...)
стр. 102 103
6.5. Функциональные объекты и алгоритм transform
Как видно из раздела 2.4, STL определяет следующие шаблонные классы, которые мы можем
использовать как функциональные объекты, сопроводив их парой скобок:
plus<T> minus<T (читать далее...)
стр. 104 105 106
6.6. Адаптеры
итераторов
Для итераторов существуют два типа адаптеров: итераторы
вставки (insert) и обратные (reverse) итераторы. В этом разделе мы
встретим несколько типов итераторов из тех, что уже были рассмотрены, а
также некоторые другие
типы.
(читать далее...)
стр. 107 108 109
Обобщенные алгоритмы
Вступление
Эта глава дает обзор всех алгоритмов STL, называемых также обобщенными алгоритмами. Для уже рассмотренных алгоритмов мы будем ссылаться на предыдущее обсуждение, подробнее останавливаясь на не изученных нами алгоритмах.
(читать далее...)
стр. 110
7.1. Немодифицирующие последовательные алгоритмы
Алгоритмы в этом разделе «просматривают»
последовательности, не изменяя их.
7.1.1. АлгоритмыУш*/, count,
JЪг_each,
find_first_oj"иfind
end
Ссылки
в комментариях показывают, что мы уже обсуждали большую часть следующих
алгоритмов:
Inputlterator find II Обсуждался в
разделе 1.5 (читать далее...)
стр. 111 112 113 114 115
7.2. Модифицирующие
последовательные алгоритмы
Алгоритмы в этом разделе изменяют последовательность, с
которой работают. 7.2.1.
Преобразовать
Outputlterator
transform
(Inputlterator
first, Inputlterator last, Outputlterator result, UnaryOperation unary_op); (читать далее...)
стр. 116 117 118 119 120 121 122 123 124 125 126 127
7.3.
Алгоритмы, связанные с сортировкой
В этом разделе собраны алгоритмы, имеющие отношение к
сортировке. Для каждого из них существуют две версии: одна
использует оператор <, а другая - любую заданную функцию сравнения.
7.3 (читать далее...)
стр. 128 129 130 131 132 133 134 135 136 137 138 139 140 141
7.4. Обобщенные численные алгоритмы
Чтобы использовать алгоритмы, обсуждаемые в этом разделе,
мы должны написать
в программе
#include <numeric>
если работаем с версией STL, соответствующей проекту стандарта C++. Для HP STL необходимо заменить эту строчку на следующую:
#include <a (читать далее...)
стр. 142 143 144
7.5. Прикладная программа: метод наименьших квадратов
Теперь мы применим алгоритмы accumulate и inner jproduct для решения известной практической задачи. Предположим, что имеется
набор из п пар чисел (х, у), где каждая пара соответствует точке на
плоскости ху, и мы хотим найти прямую линию, которая является достаточно
разумным приближением зависимости, представленной этими точками, как
показано на рисунке 7.1 (читать далее...)
стр. 145 146 147
Прикладная программа: очень большие числа
8.1. Введение
Эта глава сильно отличается от предыдущих. В ней мы
рассмотрим полезный на практике класс large, реализующий операции с очень
большими числами, для чего он использует контейнеры и алгоритмы STL. (читать далее...)
стр. 148 149 150
8.2. Реализация класса large
Только что упомянутая строка препроцессора находится в следующем файле заголовка largeh, который мы использовали в программе largedem.cpp:
II large.h: Многоразрядная целочисленная арифметика. #include
<i (читать далее...)
стр. 151 152 153 154 155 156 157
8.3. Вычисление числа п
Хотя класс large предназначен для представления
больших целых чисел, мы
можем использовать его для приближенного представления вещественных чисел, если будем использовать
соответствующее масштабирование.
(читать далее...)
стр. 158 159 160 161