В этой части — обзоры книг о стандартной библиотеке шаблонов C++ (STL, Standard Template Library). Эта библиотека ведёт свою историю с начала 1990-х, когда её разрабатывал Александр Степанов в компании HP.
Что-то в книгах со временем устаревает, например, встречается умный указатель auto_ptr. Тем временем в последних стандартах появилось очень много нововведений: в C++11 — многопоточность, работа с точным временем, новые генераторы случайных чисел, std::array, std::forward_list, std::unordered_map и пр., в C++17 — std::string_view, математические функции, работа с файловой системой, вариативный тип std::any, параллельные версии для алгоритмов и множество мелких улучшений, в C++20 — невладеющие указатели на массив std::span, библиотека для работы с битами, ranges, chrono, расширенная библиотека потоков и пр.
240 страниц. ДМК, 1999
Leen Ammeraal. STL for C++ Programmers. John Wiley, 1997
Книга начинается с короткого введения в шаблоны, экскурса в историю (как разработка HP вошла в стандарт).
Содержание: для начинающих (основы, некоторые алгоритмы, устаревший auto_ptr), другие алгоритмы и контейнеры, последовательные контейнеры, ассоциативные контейнеры, адаптеры контейнеров (стеки, очереди, очереди с приоритетом), функциональные объекты и адаптеры, обобщённые алгоритмы (обширный раздел); прикладные программы.
В основном примеры синтетические, но встречаются и интересные: решето Эратосфена, метод наименьших квадратов; отдельные разделы занимают реализация длинной арифметики и вычисление \(\pi\).
432 страницы. Питер, 2018
Jacek Galowicz. C++17 STL Cookbook. Packt, 2017
Содержание: новые возможности C++17, контейнеры, итераторы, лямбда-выражения, основы алгоритмов, сложные случаи использования алгоритмов; строки, классы потоков и регулярные выражения; вспомогательные классы, параллелизм и конкурентность, файловая система.
Книга хорошая, но явно не должна быть первой. Есть небольшие практические примеры и интересные задачи (множество Мандельброта в ASCII).
1136 страниц. Вильямс, 2014
Nicolai M. Josuttis. The C++ Standard Library. A Tutorial and Reference. Addison-Wesley, 2012
Оригинальное название оправдывает себя: это и учебник, и справочник. В разделе с благодарностями и далее в тексте автор упоминает, что его консультировали эксперты из комитета по стандартизации и другие специалисты.
Автор очень подробно рассматривает нововведения C++11 (многие из которых значительно повлияли на язык в целом), только затем приступает к STL.
Содержание: общие принципы, вспомогательные средства (пары, кортежи, умные указатели, числовые пределы, свойства и утилиты типов, минимум, максимум, обмен значений, вспомогательные операторы сравнения, арифметика рациональных чисел на этапе компиляции, часы и таймер, заголовочные файлы cstddef, cstdlib, cstring), стандартная библиотека шаблонов (контейнеры, итераторы, алгоритмы, адаптеры итераторов, пользовательские обобщённые функции, модифицирующие алгоритмы, функции в качестве аргументов, лямбда-функции, функциональные объекты и пр.), контейнеры (две главы), итераторы, функциональные объекты и лямбда-функции (подробнее), алгоритмы, специальные контейнеры, строки, регулярные выражения, ввод-вывод, i18n, работа с числами (случайные числа, комплексные числа и пр.), параллельное программирование, аллокаторы.
Смущает только попытка разбирать код на языке XML с помощью регулярных выражений. Если использовать регулярные выражения вместо полноценного парсера, эта задача выполнима только для ограниченного подмножества языка.
Приложения: битовые множества, массивы значений, аллокаторы и функции для работы с памятью.
224 страницы. Питер, 2002
Scott Meyers. Effective STL. Addison-Wesley, 2001
Учитель в школе рутинно отрабатывает с вами орфографию и пунктуацию, а эта книга научит писать красиво. 50 советов, многие — по минимизации затрат памяти и других ресурсов.
Содержание: контейнеры (в целом), контейнеры vector и string, ассоциативные контейнеры, итераторы, алгоритмы; функции, функторы и классы функций; программирование в STL (в основном — детали работы алгоритмов).
Книга написана хорошим языком, местами почти с юмором.
Совет 18. Избегайте vector<bool>
vector<bool> как контейнер STL обладает лишь двумя недостатками. Во-первых, это вообще не контейнер STL. Во-вторых, он не содержит bool.
К сожалению, есть устаревшие советы: «Совет 8. Никогда не создавайте контейнеры, содержащие auto_ptr», «Совет 25. Изучите нестандартные хешированные контейнеры» (появились в C++11).
В последнем совете автор рекомендует изучать сайты, посвящённые STL и библиотеке Boost.
Приложения: локальные контексты, STL от Microsoft.
432 страницы. Вильямс, 2010
David R. Musser, Gillmer J. Derge, Atul Saini. STL Tutorial and Reference Guide—C++ Programming with the Standard Template Library. Addison-Wesley, 2001
В книге два предисловия Александра Степанова (создателя HP STL, которая в изменённом виде вошла в стандарт): к первому изданию (1995) и второму (2001). Предисловие ко второму изданию интересно само по себе. Можете почитать его как отдельное произведение.
«Некоторые из вас могли слышать, что обобщённое программирование — это стиль программирования с применением шаблонов C++. Это не так. [...] Обобщённое программирование — это предмет, изучающий систематическую организацию полезных программных компонентов».
template <typename T> T gcd(T m, T n) {
while (n != 0) {
T t = m % n;
m = n;
n = t;
}
}
«Когда известный учёный-кибернетик увидел мою реализацию алгоритма Евклида для поиска наибольшего общего делителя двух величин, он возразил, что данный алгоритм некорректен, так как возвращает –1 при передаче ему аргументов 1 и –1, так что наибольший общий делитель не оказывается наибольшим. Он предложил исправить ситуацию, заменив последнюю строку на return m < 0 ? -m : m;.
К сожалению, в этом случае алгоритм не будет работать для многих важных расширений, таких как полиномы, комплексные целые числа и т. д. Проблема исчезает, если мы используем более абстрактное (и алгоритмически более осмысленное) определение наибольшего общего делителя: это делитель, который делится на любой другой общий делитель. Такое определение допускает неоднозначные решения: в случае целых чисел 24 и 30 наибольшими общими делителями будут 6 и –6. Это соответствует тому, что математики делали несколько последних столетий».
В предисловии говорится, что ещё в 1971 году Дэвид Мюссер занимался обобщённым программированием, хотя и в ограниченной области. Эндрю Кёниг предложил представить Александру Степанову свои наработки комитету стандартизации C++ в ноябре 1993. В марте 1994 Александр Степанов и Менг Ли предоставили формальное предложение, и его одобрили. Но были предложения об изменениях и расширениях библиотеки. Наиболее значительное расширение (ассоциативные контейнеры) выполнил Дэвид Мюссер, а Александр Степанов и Менг Ли подготовили окончательное предложение, утверждённое в июле 1994 года.
Второй соавтор (Жилмер Дердж) — просто опытный разработчик. Третий соавтор, считается, первым увидел коммерческий потенциал STL и успел воспользоваться этим в своей компании.
Основная часть книги начинается с шаблонов и нотации \(O\)-большое. Содержание: вводный курс (итераторы, алгоритмы, контейнеры, отсортированные ассоциативные контейнеры, функциональные объекты, адаптеры контейнеров, адаптеры итераторов, функциональные адаптеры), примеры программ (поиск в словаре, поиск всех групп анаграмм, улучшенная его версия, ускорение той же программы с использованием «мультиотображений», определение класса итератора, STL и ООП, вывод дерева учёных в области теории вычислительных машин и систем, класс для хронометража обобщённых алгоритмов), справочное руководство по STL (итераторы, контейнеры, обобщённые алгоритмы, функциональные объекты, аллокаторы, утилиты).
Приложения: заголовочные файлы STL, строки, заголовочные файлы, используемые в примерах программ, ресурсы.
544 страницы. Невский Диалект, 2004
Matther H. Austern. Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley, 1999
Автор начал работать в SGI в 1996 году, а Александр Степанов перешёл туда из HP немного раньше. «В то время компилятор фирмы SGI не содержал реализации стандартной библиотеки шаблонов. Используя в качестве базы исходную реализацию HP, мы с Алекс[андр]ом и Гансом Боэмом написали реализацию STL».
Содержание: введение в обобщённое программирование (обзор, алгоритмы и диапазоны, итераторы, функциональные объекты, контейнеры), справочник по концепциям STL (базовые концепции, итераторы, функциональные объекты, контейнеры), справочник по алгоритмам и классам (основные компоненты, неизменяющие алгоритмы, основные изменяющие алгоритмы, сортировка и поиск, итераторы, функциональные объекты, контейнеры).
Приложение: переносимость и стандартизация.
608 страниц. ДМК, БХВ, 2008
Matthew Wilson. Extended STL, Volume 1. Collections and Iterators. Addison-Wesley, 2008
Книга основана на опыте автора при работе над библиотеками STLSoft.
Содержание (сейчас не пугайтесь): пролог, основы (стандартная библиотека шаблонов, концепции расширения STL, категории ссылок на элементы, «забавная безвременная ссылка», принцип DRY SPOT, закон дырявых абстракций, программирование по контракту, ограничения, прокладки, «утка и гусь» — основы частичного структурного соответствия, идиома RAII, инструменты для работы с шаблонами, выводимая адаптация интерфейса, гипотеза Хенни, «независимые автономии друзей equal()», важнейшие компоненты), наборы (адаптация API glob, конфликты в конструкторах, адаптация API opendir/readdir, FindFirstFile/FindNextFile, компромисс между эффективностью и удобством использования на примере обхода каталогов FTP-сервера, перебор процессов и модулей, числа Фибоначчи, адаптация семейства MFC-контейнеров CArray, «карта окружающей местности», «путешествие по \(Z\)-плоскости», разбиение строки, адаптация энумераторов и наборов COM, ввод/вывод с разнесением и сбором, изменение типа возвращаемого значения в зависимости от аргументов, «порча итераторов извне»), итераторы (усовершенствованный ostream_iterator, паттерн Dereference Proxy, выбор имён, итератор селекции членов, конкатенация C-строк, характеристики адаптированных адаптеров, фильтрующая итерация, составные адаптеры итераторов).
Эта книга давно ждёт на полке своей очереди.
336 страниц. Вильямс, 2001
Pablo Halpern. The C++ Standard Library from Scratch. Macmillan Computer Publishing, 2000
Содержание: знакомство с TynyPIM, класс для работы с текстовыми строками, адресная книга с помощью контейнеров vector, list, редактирование записей адресов с помощью функций класса String и операторов ввода-вывода, усовершенствование адресной книги с помощью алгоритмов и сортированных контейнеров, прокручивание экранных списков с помощью двусторонних очередей и потоков ввода-вывода, простая система меню, класс даты и времени, сборка блоков программы, профессиональная работа со стандартной библиотекой.
Задачник. Кому-то, может, будет интересно.