БХВ-Петербург", 190005, Санкт-Петербург, Измайловский пр., 29. Гигиеническое заключение на продукцию, товар № .953.Д.0015 от г. выдано Департаментом ГСЭН Минздрава России. Отпечатано с готовых диапозитивов в ГУП “Типография "Наука" 199034, Санкт-Петербург, 9 линия, 12 (англ.) (рус.) О 2001, Prentice Hall PTR, Prentice-Hall, Inc. О Перевод на русский язык “БХВ-Петербург", 2004 П редисловие........................................................................................................................*...........15 Стандарт C++........................................................................................................................................ 15 Расширение STL................................................................................................................................... 17 Структура книги................................................................................................................................... 17 Код ........................................................................................................................................................18 Благодарности...................................................................................................................................... 19 Введение............................................................................................................................................. 21 Обзор..................................................................................................................................................... 21 Комитеты X3J16 (ANSI) и WG21 (ISO)....................................................................................22 Стандартная библиотека шаблонов (STL)................................................................................22 Алгоритмы...................................................................................................................................23 Контейнеры..................................................................................................................................24 Итераторы....................................................................................................................................25 Код Hewlett-Packard.................................................................................................................... 26 Коммерческие компиляторы...................................................................................................... 28 Функциональное описание................................................................................................................. 29 Стандартные заголовки.............................................................................................................. 29 Пространство имен std ............................................................................................................... 30 Свобода выбора...........................................................................................................................30 Ограничения.................................................................................................................................31 Использование STL..............................................................................................................................31 Пространства имен..................................................................................................................... 32 Диалекты...................................................................................................................................... 32 Реализация STL....................................................................................................................................33 Стиль программирования.......................................................................................................... 33 Реализация заголовков............................................................................................................... 34 Директивы include.......................................................................................................................35 Пространства имен......................................................................................................................37 Коммерческий код.......................................................................................................................37 Зарезервированные имена.......................................................................................................... 39 Тестирование STL................................................................................................................................39 Простейшие тесты...................................................................................................................... 40 Упражнения..........................................................................................................................................41 Г л ав а 1. И т е р а т о р ы ...................................................................................................................... 43 Обзор................................................. Функциональное описание................................................................................................................. 43 Итераторы вывода...................................................................................................................... 44 Итераторы ввода..........................................................................................................................46 Значение маркера end-of-sequence............................................................................................. 47 Последовательные итераторы.................................................................................................... 48 Двунаправленные итераторы..................................................................................................... 51 Итераторы произвольного доступа........................................................................................... 52 Использование итераторов..................................................................................................................53 Категории итераторов......................................... Упражнения.......................................................................................................................................... 55 Г л а в а 2. ...............................................................................................................................56 Обзор..................................................................................................................................................... 56 Пара (pair) ....................................................................................................................................56 Функция makejoair......................................................................................................................57 Операторы operator== и operator<.......................................................................................... 57 Оператор operator!=....................................................................................................................58 Операторы operator>, operator<= и operator>=.....................................................................58 Функциональное описание..................................................................................................................59 Функция make_pair..................................................................................................................... 60 Оператор operator! - ....................................................................................................................60 Оператор operator==................................................................................................................. 60 Оператор operator<.....................................................................................................................60 Оператор operator<=................................................................................................................. 61 Оператор operator>.....................................................................................................................61 Оператор operator>=..................................................................................................................61 Шаблонный класс p a ir................................................................................................................61 Использование заголовка .................................................................................................... 62 Шаблонный класс pair и функция make_pair...........................................................................62 Функции operator!=, operator>, operator<= и operator>=.................................................. 63 Реализация .............................................................................................................................63 Тестирование .........................................................................................................................65 Упражнения.......................................................................................................................................... 66 Г л а в а 3. ............................................................................................................................68 Обзор..................................................................................................................................................... 68 Свойства итератора.....................................................................................................................68 Итератор....................................................................................................................................... 69 Теги итератора.............................................................................................................................69 Категории итератора.................................................................................................................. 70 Шаблонный класс iteratorJraits................................................................................................ 72 Шаблонная функция Iter_cat..................................................................................................... 73 Шаблонная функция V aljype.................................................................................................... 74 Шаблонная функция D istjype................................................................................................... 75 Шаблонные функции advance и distance.................................................................................. 76 Специализированные итераторы............................................................................................... 77 Функциональное описание................................................................................................................. 83 Функция advance................................................ Шаблонный класс back insert iterator......................................................................................85 Функция backjnserter................................................................................................................ 87 Тип bidirectional iterator_tag.................................................................................................... 87 Функция distance......................................................................................................................... 87 Тип forward iterator tag............................................................................................................ 88 Шаблонный класс front insert iterator.....................................................................................88 Функция front inserter................................................................................................................ 90 Тип input iteratorJ a g ................................................................................................................. 90 Шаблонный класс insert iterator...............................................................................................90 Функция inserter..........................................................................................................................92 Шаблонный класс istream iterator............................................................................................92 Шаблонный класс istreambuf iterator.......................................................................................94 Шаблонный класс iterator.......................................................................................................... 96 Шаблонный класс iterator traits................................................................................................ 96 Оператор operator!=................................................................................................................... 98 Оператор operator==................................................................................................................. 98 Оператор operator<.................................................................................................................... 98 Оператор operator<=................................................................................................................. 99 Оператор operator>.................................................................................................................... 99 Оператор operator>=................................................................................................................. 99 Оператор operator+.................................................................................................................... 99 Оператор operator-..................................................................................................................... 99 Шаблонный класс ostream iterator......................................................................................... 100 Шаблонный класс oslreambuf iterator.................................................................................... 101 Тип output iterator tag..............................................................................................................103 Тип random access iterator ta g .............................................................................................. 103 Шаблонный класс reverse iterator................................................................................ Использование заголовка ................................................................................................107 Итераторы.................................................................................................................................. 107 Теги итератора........................................................................................................................... 109 Итераторы вставки....................................................................................................................110 Потоковые итераторы...............................................................................................................111 Буферизованные потоковые итераторы................................................................................ 113 Реализация заголовка .................................................................................................... 114 Тестирование заголовка ..................................................................................................138 Упражнения........................................................................................................................................ 145 . <тетогу> ........................................................................................................................146 Обзор................................................................................................................................................... 146 Распределитель (allocator) ........................................................................................................146 Для чего нужны распределители............................................................................................. 147 Пользовательские распределители.......................................................................................... 148 Ограничения распределителей................................................................................................ 149 Интеллектуальные указатели....................................................................................................150 Сравнение распределителей.....................................................................................................150 Другие механизмы.....................................................................................................................154 Безопасные исключения........................................................................................................... 155 Временные буферы................................................................................................................... 156 Функциональное описание................................................................................................................159 Шаблонный класс allocator.......................................................................................................160 Класс allocator..............................................................................................................164 Шаблонный класс auto_ptr.......................................................................................................165 Функция get temp orary buffer................................................................................................ 168 Оператор operator/= ............................................................................................................... 168 Оператор operator==...............................................................................................................168 Шаблонный класс raw_storage_iterator................................................................................. 169 Функция return_temporary_buffer.................................................... Функция uninitialized_copy......................................................................................................170 Функция uninitializedJill....................................................................................................... 171 Функция uninitializedJilljt.....................................................................................................171 Использование заголовка ................................................................................................171 Реализация заголовка ......................................................................................................173 Файл xmemory............................................................................................................................ 173 Шаблонный класс allocator.......................................................................................................177 Файл memory.............................................................................................................................. 178 Безопасные исключения............................................................................................................184 Тестирование заголовка <тетогу>..................................................................................................186 Упражнения........................................................................................................................................ 189 . А лгоритм ы ....................................................................................................................191 Обзор....................................................................................................................................................191 Итераторы.................................................................................................................................. 191 Контейнеры................................................................................................................................ 192 Функциональные объекты........................................................................................................192 Функциональное описание................................................................................................................ 194 Использование алгоритмов...............................................................................................................196 Упражнения........................................................................................................................................ 197 . ............................................................... Обзор....................................................................................................................................................198 Функциональное описание................................................................................................................ 198 Функция adjacentJind............................................................................................................. 205 Функция binary search............................................................................................................ 205 Функция copy............................................................................................................................206 Функция copy_backward......................................................................................................... 206 Функция count...........................................................................................................................206 Функция count_if..................................................................................................................... 206 Функция equal...........................................................................................................................207 Функция equal_range.............................................................................................................. 207 Функция f i l l ................................................................. Функция fd l_ n ............................................................................................................................208 Функция fin d .............................................................................................................................208 Функция fin d e n d ......................................................................................................................208 Функция findJirst_of............................................................................................................... 209 Функция f i n d j f .........................................................................................................................209 Функция fo rjea ch .....................................................................................................................209 Функция generate......................................................................................................................209 Функция generaten................................................................................................................210 Функция includes....................................................................................................................210 Функция inplace merge..........................................................................................................210 Функция iter swap.................................................................................................................. 211 Функция lexicographical compare........................................................................................ 211 Функция lowerbound.............................................................................................................212 Функция make_heap...............................................................................................................212 Функция m ax............................................................................................................................ 213 Функция max_element.............................................................................................................213 Функция merge........................................................................................................................ 213 Функция min............................................................................................................................ 214 Функция m inelem ent............................................................................................................. 214 Функция mismatch.................................................................................................................. 215 Функция nextjaermutation......................................................................................................215 Функция nthelem ent..............................................................................................................216 Функция partial sort...............................................................................................................216 Функция partial sort copy.................................................................................................... 217 Функция partition....................................................................................................................217 Функция pop heap..................................................................................................................218 Функция prev_permutation.................................................................................................... 218 Функция p u sh h e a p ................................................................................................................219 Функция random shuffle.........................................................................................................219 Функция remove...................................................................................................................... 220 Функция remove copy............................................................................................................220 Функция remove copy i f ........................................................................................................221 Функция remove if..................................................................................................................221 Функция replace...................................................................................................................... 222 Функция replace_copy............................................................................................................ 222 Функция replacejc o p y jf........................................................................................................222 Функция re p la c e if................................................................................................................. 223 Функция reverse...................................................................................................................... 223 Функция reverse_copy............................................................................................................. 223 Функция rotate........................................................................................................................ 223 Функция rotate copy............................................................................................................... 224 Функция search....................................................................................................................... 224 Функция se a rc h n ................................................................................................................... 225 Функция set difference...........................................................................................................225 Функция set intersection........................................................................................................ 226 Функция setsym m etric difference........................................................................................ 227 Функция set union.................................................................................................................. 228 Функция sort........................................................................................................................... 228 Функция sort heap.................................................................................................................. 229 Функция stable_partition........................................................................................................ 229 Функция stable sort................................................................................................................ 230 Функция sw ap......................................................................................................................... 230 Функция swap ranges............................................................................................................. 230 Функция transform.................................................................................................................. 230 Функция unique........................................................................................................................231 Функция unique copy............................................................................................................. 232 Функция upper bound............................................................................................................ 232