Обобщенное программирование. 
Методы и технологии программирования

Обобщённое программирование (англ. generic programming) — парадигма программирования, заключающаяся в таком описании данных и алгоритмов, которое можно применять к различным типам данных, не меняя само это описание.

Непосредственную поддержку парадигмы обобщенного программирования в языке в языке программирования обеспечивают шаблоны. Шаблон — это одно из самых сложных и мощных средств в С++. Он не вошел в исходную спецификацию С++, и лишь несколько лет назад стал неотьемлемой частью программирования на С++. Шаблоны позволяют достичь одну из самых трудных целей в программировании — создать многократно используемый код.

Используя шаблоны, можно создавать обобщенные функции и классы. В обобщенной функции (или классе) обрабатываемый ею (им) тип данных задается как параметр. Таким образом, одну функцию или класс можно использовать для разных типов данных, не предоставляя явным образом конкретные версии для каждого типа данных.

Стандартная библиотека шаблоновSTL.

Стандартная библиотека шаблонов (STL) (англ. StandardTemplateLibrary) — набор согласованных обобщенных алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций.

Структура библиотеки:

В библиотеке выделяют пять основных компонентов:

• · Контейнер (container) — хранение набора объектов в памяти.
• · Итератор (iterator) — обеспечение средств доступа к содержимому контейнера.
• · Алгоритм (algorithm) — определение вычислительной процедуры.
• · Адаптер (adaptor) — адаптация компонентов для обеспечения различного интерфейса.
• · Функциональный объект (functor) — сокрытие функции в объекте для использования другими компонентами.

Разделение позволяет уменьшить количество компонентов. Например, вместо написания отдельной функции поиска элемента для каждого типа контейнера обеспечивается единственная версия, которая работает с каждым из них, пока соблюдаются основные требования.

Остановимся подробнее на Контейнерах. Контейнеры — это объекты, содержащие другие объекты. Существует несколько различных типов контейнеров.

· Последовательные

Vector C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Добавление-удаление элемента в конец vector занимает амортизированное O (1) время, та же операция в начале или середине vector — O (n). Существует специализация шаблона vector для типа bool, которая требует меньше памяти за счёт хранения bool в виде битов.

List — Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Медленный поиск и доступ за O (n), в любом месте быстрая вставка и удаление за O (1).

Deque — Похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах.

· Ассоциативные

Set — Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска.

Multiset — То же что и set, но позволяет хранить повторяющиеся элементы.

Map — Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор.

Multimap — То же что и map, но позволяет хранить повторяющиеся ключи.

· Контейнеры-адаптеры

Stack — Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца.

Queue — Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать.

Priority_Queue — Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте.

Псевдоконтейнеры.

Bitset — Служит для хранения битовых масок. Похож на vector фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти.

basic_string — Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет быстрый доступ ко всей последовательности.

Valarray — Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций. Однако, в нём реализованы операции, которые можно эффективно реализовать как на векторных процессорах, так и на скалярных процессорах с блоками SIMD.