Лекции (12) (Презентации лекций (PDF))

Стандартная библиотека шаблоновSTLSTL (Standard Template Library) являетсячастью стандарта C++.Ядро STL состоит из четырех основныхкомпонентов:контейнеры,итераторы,алгоритмы,распределители памяти.1КонтейнерыКонтейнер –это класс, который предназначен дляхранения объектов какого-либо типа.Примеры известных ранее контейнеров:- таблица идентификаторов,- массив,- дерево,- список,- ассоциативный список, например, список, хранящийфамилии людей и номера их телефонов, ключом которого2является фамилия, если она уникальна(!).Стандартные контейнеры STLVector < T >- динамический массивList < T >- линейный списокStack < T >- стекQueue < T >- очередьDeque < T >- двусторонняя очередьPriority_queue < T > - очередь с приоритетамиSet < T >- множествоBitset < N >- множество битов (массив из N бит)Multiset < T >- набор элементов, возможно, одинаковыхMap < key, val > - ассоциативный списокMultimap < key, val > - ассоциативный список для храненияпар ключ/значение, где с каждымключом может быть связано болееодного значения.3Состав контейнеровВ каждом классе-контейнере определен набор методов для работыс контейнером, причем все контейнеры поддерживают стандартныйнабор базовых операций.Базовая операция контейнера (базовый метод) – метод класса,имеющий во всех контейнерах одинаковое имя, одинаковый прототипи семантику (их примерно 15-20).Например,функция push_back () помещает элемент в конец контейнера,функция size () выдает текущий размер контейнера.Базовыми методами можно пользоваться одинаково независимо оттого, в каком конкретно контейнере находятся элементы, можно такжеменять контейнеры, не меняя тела функций, работающих с ними.Операции, которые не могут быть эффективно реализованы длявсех контейнеров, не включаются в набор общих операций.Например, обращение по индексу введено для контейнера vector ,но не для list.4Типы, используемые в контейнерахКаждый контейнер в своей public части содержит серию typedef,где введены стандартные имена типов, например:value_typeallocator_typesize_typeiteratorconst_iteratorreverse_iteratorconst_reverse_iteratorpointerconst_pointerreferenceconst_reference- тип элемента,- тип распределителя памяти,- тип, используемый для индексации,- итератор,- константный итератор,- обратный итератор,- обратный константный итератор,- указатель на элемент,- указатель на константный элемент,- ссылка на элемент,- ссылка на константный элемент.Эти имена определяются внутри каждого контейнера так, как этонеобходимо, т.е.

скрывают реальные типы, что, например, позволяетписать программы с использованием контейнеров, ничего не зная ореальных типах.В частности, можно составить код, который будет работать с любым5контейнером.Распределители памятиКаждый контейнер имеет распределитель памяти (allocator),который используется при выделении памяти под элементы контейнераи предназначен для того, чтобы освободить пользователей контейнеров,от подробностей физической организации памяти.Стандартная библиотека обеспечивает стандартный распределительпамяти, заданный стандартным шаблоном allocator из заголовочногофайла <memory>, который выделяет память при помощи операции new( ) и по умолчанию используется всеми стандартными контейнерами.Класс allocator обеспечивает стандартные способы выделения иперераспределения памяти, а также стандартные имена типов дляуказателей и ссылок.Пользователь может задать свои распределители памяти,предоставляющие альтернативный доступ к памяти.Стандартные контейнеры и алгоритмы получают память иобращаются к ней через средства, обеспечиваемые распределителемпамяти.6Класс allocatortemplate <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 );// инициализирует *р значением valvoid destroy ( pointer p );// вызывает деструктор для *p,// память при этом не освобождается.……};7ИтераторыИтератор – это класс, объекты которого выполняют такую же роль поотношению к контейнеру, как указатели по отношению к массиву.Указатель может использоваться в качестве средства доступа кэлементам массива, а итератор - в качестве средства доступа кэлементам контейнера.Итераторы «склеивают» ядро STL в одну библиотеку.Итераторы поддерживают абстрактную модель данных какпоследовательности объектов.Понятия «нулевой итератор» не существует, а при организации цикловпроисходит сравнение с концом последовательности.Каждый контейнер обеспечивает свои итераторы, поддерживающиестандартный набор итерационных операций со стандартнымиименами и смыслом.Итераторные классы и функции находятся в заголовочном файле< iterator >.8Методы контейнеров для нахождения значенийитераторов концов последовательности элементов• 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;9Прямые итераторыbegin()ВAСDend()Обратные итераторыrbegin()DCBArend()10Операции над итераторамиПусть р - объект типа итератор.К каждому итератору можно применить, как минимум, три ключевыеоперации:•••*р – элемент, на который указывает итератор,р++ - переход к следующему элементу последовательности,== - операция сравнения.Пример:iterator p = v.begin(); – такое присваивание верно независимо от того,какой контейнер v .Теперь *p – первый элемент контейнера v.Замечание:при проходе последовательности как прямым, так и обратнымитератором переход к следующему элементу будет р++ (а не р-- !).Не все виды итераторов поддерживают один и тот же наборопераций.11Категории итераторовВ библиотеке STL введено 5 категорий итераторов:•1.

Вывода (output - запись в контейнер)( *р = , ++ )•2. Ввода (input - считывание из контейнера)( = *р, , ++, ==, !=)•3. Однонаправленный (forward)( *р =, =*р, , ++ , ==, != )•4. Двунаправленный (bidirectional)( *р=, =*р, , ++,--, ==, != ) - list, map, set•5. C произвольным доступом (random_access)(*р=, =*р, , ++,--, ==, !=, [ ], +, -, +=, -=, <, >, <=, >= ) - vector,dequeКаждая последующая категория является более мощной, чемпредыдущая.12АлгоритмыАлгоритмы STL (их всего 60) - реализуют некоторыераспространенные операции с контейнерами, которые непредставлены функциями-членами каждого из контейнеров(например, просмотр, сортировка, поиск, удаление элементов…).Каждый алгоритм выражается шаблоном функции или наборомшаблонов функций.Операции, реализуемые алгоритмами, являются универсальными длялюбого из контейнеров и поэтому определены вне этихконтейнеров.Реализация алгоритмов не использует имен никаких конкретныхконтейнеров, а все действия над контейнером производятся черезуниверсальные имена итераторов.Зная, как устроены алгоритмы, можно писать свои собственныеалгоритмы обработки, которые не будут зависеть от контейнера.Все стандартные алгоритмы находятся в пространстве имен std, а ихобъявления - в заголовочном файле < algorithm > .13Группы алгоритмов1.

Немодифицирующие алгоритмы - извлекают информацию из контейнера, ноне модифицируют сам контейнер (ни элементы, ни порядок их расположения ).Примеры :Find () – находит первое вхождение элемента с заданным значениемCount () – количество вхождений элемента с заданным значениемFor_each () – применяется некоторая операция к каждому элементу(не связано с изменением )2. Модифицирующие алгоритмы - изменяют содержимое контейнера. Либосами элементы меняются, либо их порядок, либо их количество.Примеры :Transform () – применяется некоторая операция к каждому элементу( каждый элемент изменяется)Reverse () – переставляет элементы в последовательностиCopy () – создает новый контейнер3.

Сортировка.Примеры :Sort () – простая сортировка .Stable_sort () – сохраняет порядок следования одинаковых элементов(например, это бывает существенно при сортировке по нескольким ключам).Merge () – склеивает две отсортированные последовательности.14Категории итераторов и алгоритмыПо соглашению, при описании алгоритмов, входящих в STL,используются стандартные имена формальных параметров-итераторов.В зависимости от названия итератора в прототипе алгоритма, должениспользоваться итератор уровня «не ниже чем». То есть по названиюпараметров шаблона можно понять, какого рода итератор нам нужен, тоесть к какому контейнеру применим этот алгоритм.Пример: шаблонная функция find() с тремя параметрами ( итератор, скакого начинается поиск, каким заканчивается и искомый элемент).Для реализации целей функции достаточно итератора ввода (изконтейнера).Template < class InputInterator, class T >InputIterator find ( InputIterator first, InputIterator last, const T& value ) {while ( first != last && * first != value )first ++;return first;}Однако категория итераторов не принимает участия в вычислениях.Этот механизм относится исключительно к компиляции.15typename1.

Ключевое слово typename используется при описаниипараметра-типа шаблона (наряду с ключевым словом class).Например,template <typename T>void f (T a) {...}2. Если используемое в шаблоне имя типа зависит отпараметров шаблона, необходимо использовать ключевоеслово typename. Например,template <class T>void f (vector <T> & v){vector <T> :: iterator i = begin ();// Err!typename vector <T> :: iterator i = begin(); //O.K....}16Пример шаблонной функции, использующей тип,вложенный в класс–параметр шаблонаstruct X {enum { e1, e2, e3 } g;struct inner {int i, j;void g ( ) { cout << “ggg\n”; }};inner c;};template < class T >void f ( typename T::inner t ) { t.g ( ); }int main ( ) {X x;x.g = X::e1;x.c.g ( );X::inner iii;iii.i = 7;f <X> ( iii );return 0;}17Пример шаблонной функции дляконтейнеров STLПоиск заданного элемента в контейнере, начиная споследнего (просмотр контейнера от конца к началу)обычно производится так:template < class C >typename C :: const_iterator find_last( const C & c, typename C :: value_type v ){typename C :: const_iterator p = c.end ( );while (p != c.begin ( ) )if ( * -- p == v )return p;return c.end ( );}18Контейнер vectortemplate < class T , class A = allocator < T > > сlass vector {.......public:// Типы – typedef …...

- см. выше// Итераторы …….. - см. выше//// Доступ к элементам//reference operator [ ] (size_type n); // доступ без проверки диапазонаconst_reference operator [ ] (size_type n) const;reference at (size_type n); // доступ с проверкой диапазона (если индекс// выходит за пределы диапазона, возбуждается исключение out_of_range)const_reference at (size_type n) const;reference front ( ); // первый элемент вектораconst_reference front ( ) const;reference back (); // последний элемент вектораconst_reference back ( ) const;19Контейнер vector// Конструкторы, деструктор, operator=//explicit vector (const A&=A()); //создается вектор нулевой длиныexplicit vector (size_type n; const T& value = T(); const A& = A());// создается вектор из n элементов со значением value// (или с "нулями" типа T, если второй параметр отсутствует;// в этом случае конструктор умолчания в классе Т обязателен)template <class I> vector (I first, I last, const A& = A());// инициализация вектора копированием элементов из [first, last),// I - итератор для чтенияvector (const vector < T, A > & obj ); // конструктор копированияvector& operator = (const vector < T, A > & obj );~vector();20Контейнер vector//Некоторые функции-члены класса vector//iterator erase (iterator i ); // удаляет элемент, на который указывает данный// итератор.