книга (И.А. Волкова, А.В. Иванов, Л.Е. Карпов - Основы объектно-ориентированного программирования. Язык программирования С++), страница 17

. . */ };int main(){vect <uint,16> v1;vect <unsigned int,16> v2;. . .}Объекты v1 и v2 имеют один и тот же тип.Кроме того, эквивалентность типов определяется с точностью до вычисления константных выражений на этапе компиляции. Поэтому объекты v1и v3vect <uint,16> v1;vect <unsigned int,10+6> v3;имеют одинаковый тип.111Стандартная Библиотека шаблонов STLГлава 16.Стандартная Библиотекашаблонов STLSTL (Standard Template Library) является частью стандарта C++. Основныекомпоненты этой библиотеки — иерархии шаблонов классов и функций.Библиотека STL является важной составной частью стандартной библиотеки.Ядро STL состоит из четырех основных компонентов:— контейнеры,— итераторы,— алгоритмы,— распределители памяти (аллокаторы).16.1. КонтейнерыКонтейнер — тип данных (класс), предназначенный для хранения объектовкакого-либо типа (возможна реализация контейнера, который хранит объекты разных типов: в этом случае в нем хранятся указатели на базовый типдля всех желаемых типов, то есть формально хранятся объекты одного типа, афактически указатели ссылаются на элементы разных типов из одной иерархии классов).Примерами контейнеров являются массив, дерево, список.Стандартные контейнеры библиотеки STL— Vector ‹ T ›— динамический массив— List ‹ T ›— линейный список— Stack ‹ T ›— стек— Queue ‹ T ›— очередь— Deque ‹ T ›— двусторонняя очередь— Priority_queue ‹ T › — очередь с приоритетами— Set ‹ T ›— множество— Bitset ‹ N ›— множество битов (массив из N бит)— Multiset ‹ T ›— набор элементов, возможно, одинаковых— Map ‹ key, val ›— ассоциативный массив112Стандартная Библиотека шаблонов STL—Multimap ‹ key, val › — ассоциативный массив для хранения пар«ключ–значение», где с каждым ключом может быть связано болееодного значения.ПримечаниеСтрого говоря, стек, очередь, очередь с приоритетами не считаются стандартными контейнерами.

Они построены с ограничениями функциональностина базе других контейнеров. Тем не менее, они включены в библиотеку STLнаряду с другими стандартными контейнерами.В каждом классе-контейнере определен набор функций для работыс этим контейнером, причем все контейнеры поддерживают стандартныйнабор базовых операций (функции, одинаково называющиеся, имеющиеодинаковый профиль и семантику, их примерно 15–20). Например, функцияpush_back() помещает элемент в конец контейнера, функция size() выдаеттекущий размер контейнера. Основные операции включаются в следующиегруппы:— доступ к элементу,— вставка элемента,— удаление элемента,— итераторы.Операции, которые не могут быть эффективно реализованы для всехконтейнеров, не включаются в набор общих операций.

Например, обращениепо индексу введено для контейнера vector, но не для list.Каждый контейнер в своей открытой области содержит набор определений стандартных имен типов. Среди них есть следующие имена:— value_type — тип элемента,— allocator_type — тип распределителя памяти,— size_type — тип, используемый для индексации,— iterator, const_iterator — итератор,— reverse_iterator, const_reverse_iterator — обратный итератор,— pointer, const_pointer — указатель на элемент,— reference, const_reference — ссылка на элемент.Эти имена определяются внутри каждого контейнера так, как это необходимо для соответствующего контейнера. При этом реальные типы инкапсулированы. Это позволяет писать программы с использованием контейнеров, не зависящие от типов данных, реально используемыхв контейнерах.16.2.

Распределители памятиКаждый контейнер имеет аргумент, называемый распределителем памяти(allocator), который используется при выделении памяти под элементы контейнера и предназначен для того, чтобы освободить разработчиков контейнеров, а также алгоритмов, от подробностей физической организации памяти.Распределитель памяти обеспечивает стандартные способы выделенияи перераспределения памяти, а также стандартные имена типов для указате113Стандартная Библиотека шаблонов STLлей и ссылок. Стандартная библиотека обеспечивает стандартный распределитель памяти.

Кроме того, можно задать свои распределители памяти,предоставляющие альтернативный доступ к памяти (можно использоватьразделяемую память, память со сборкой мусора, память из заранее выделенного пула и прочее).Стандартные контейнеры и алгоритмы получают память и обращаютсяк ней через средства, обеспечиваемые распределителем памяти.Стандартный распределитель памяти, задаваемый стандартным шаблонным классом allocator из заголовочного файла ‹memory›, выделяет памятьпри помощи операции new и по умолчанию используется всеми стандартными контейнерами.template <class T> class allocator{public:typedef T* pointer;typedef T& reference;// . .

.allocator() throw();// . . .pointer allocate (size_type n);// выделение памяти для// n объектов типа Tvoid deallocate (pointer p, size_type n);// освобождает память для n объектов типа Т// без вызова деструкторов Тvoid construct (pointer p, const T& val);// инициализация памяти, на которую указывает р,// значением val}void destroy (pointer p);// вызывает деструктор для *р, не освобождая память,// на которую указывает р// . . .16.3. ИтераторыКаждый контейнер содержит итераторы, поддерживающие стандартный набор итерационных операций со стандартными именами и смыслом.Итератор — это класс, объекты, которого по отношению к контейнерам играют роль указателей.

Итераторы поддерживают абстрактную модельсовокупности данных как последовательности объектов (что и представляетсобой любой контейнер). Обычно, основное действие с последовательностьюэлементов — перебор. Он организуется с помощью итераторов. Итератор —это класс, чьи объекты выполняют ту же роль по отношению к контейнеру,которую выполняют указатели по отношению к массиву. Указатель можетиспользоваться в качестве средства доступа к элементам массива, а итератор — в качестве средства доступа к элементам контейнера. Но, понятия«нулевой итератор» не существует.

При организации цикла для последовательного обращения к элементам контейнера окончание цикла фиксируетсяна основе применения специальной функции для сравнения с концом последовательности элементов контейнера.114Стандартная Библиотека шаблонов STLКлассы итераторов и функции, предназначенные для работы с ними,находятся в библиотечном файле ‹iterator›.Каждый контейнер содержит ряд ключевых методов, позволяющихнайти концы последовательности элементов в виде соответствующих значений итераторов.

Это:— iterator begin() — возвращает итератор, который указывает на первый элемент последовательности.const_iterator begin()— const iterator end() — возвращает итератор, который указывает наэлемент, следующий за последним элементом последовательности(используется при оформлении циклов).const_iterator end () const— reverse_iterator rbegin() — возвращает итератор, указывающий напервый элемент в обратной последовательности (используется дляработы с элементами последовательности в обратном порядке).const_reverse_iterator rbegin() const— reverse_iterator rend() — возвращает итератор, указывающий наэлемент, следующий за последним в обратной последовательности.const_reverse_iterator rend () const«Прямые» итераторы:«Обратные» итераторы:Пусть р — объект-итератор. К каждому итератору можно применить,как минимум, три ключевые операции:— *р— элемент, на который указывает итератор («разыменование»итератора),— р++ — переход к следующему элементу последовательности,— == — операция сравнения.Пример:iterator p = v.begin();Такое присваивание верно независимо от типа контейнера v.

Теперь*p — содержимое первого элемента контейнера v.ЗамечаниеПри проходе последовательности как прямым, так и обратным итераторомпереход к следующему элементу будет р++ (а не р−− !).Не все виды итераторов поддерживают один и тот же набор операций.В библиотеке STL введено 5 категорий итераторов:1. Ввода (input)115Стандартная Библиотека шаблонов STL2. Вывода (output)3. Однонаправленный (forward)4. Двунаправленный (bidirectional), контейнеры list, map, set5. C произвольным доступом (random_access), контейнеры vectorи dequeИтераторыЧтениеДоступВыводаВводаx = *pp−>fОднонаправленныеx = *pp−>fДвунаправленныеx = *pПроизвольныйдоступx = *pЗаписьИзменение*p = ep++++pСравнениеp++++pp == qp != q*p = ep++++pp == qp != qp−>f*p = ep++++pp−−−−pp == qp != qp−>fp[n]*p = ep++++pp−−−−pp+n n+pp–n p−qp += n p −= np == qp != qp<qp>qp >= qp <= qКаждая последующая категория, начиная с третьей, является болеемощной, чем предыдущие категории.Принято такое соглашение, что при описании алгоритмов, входящихв STL используют стандартные имена формальных параметров.в зависимости от названия итератора в профиле алгоритма, должен использоваться итератор уровня «не ниже чем».

То есть по названию параметровшаблона можно понять, какого рода итератор требуется, а, следовательно, и ккакому контейнеру применим алгоритм.Пример:Шаблонная функция find().116Стандартная Библиотека шаблонов STLДля этой функции нужны: итератор, указывающий на элемент контейнера, с которого начинается поиск, итератор, содержащий элемент, на котором поиск заканчивается, и элемент, поиск значения которого осуществляется. Для целей функции достаточно итератора ввода (из контейнера).template < class InputInterator, class T >InputIterator find ( InputIterator first,InputIterator last,const T& value ){while ( first != last && *first != value )first ++;return first;}16.4. АлгоритмыАлгоритмы STL (их около 60) реализуют некоторые распространенныеоперации с контейнерами, которые не реализуются методами каждого изконтейнеров (например, просмотр, сортировка, поиск, удаление элементови прочие).