Лекция 26. Введение в STL (часть 3) Красс Александр СПбГУ ИТМО, 2009

Темы Функциональные типы Биндеры vector list deque Адаптеры Queue Stack

Функциональные типы Из предыдущих лекций: Тип с определенным оператором вызова функции называется функциональным типом. Функциональные типы делятся на встроенные и определяемые пользователем –Указатель на функцию – это встроенный тип –Класс с оператором вызова функции – определяемый пользователем

Функциональные типы (2) STL определяет набор функциональных типов для основных операций: template struct equal_to; template struct not_equal_to; template struct greater; template struct less; template struct greater_equal; template struct less_equal; template struct plus; template struct minus; template struct multiplies; template struct divides; template struct modulus; template struct negate; template struct logical_and; template struct logical_or; template struct logical_not; Для каждого класса метод operator() возвращает результат соответствующей операции: plus summ; summ()(x, y); // вернет x+y

Функциональные типы (3) Не вдаваясь в подробности реализации: template class greater { public: bool operator()( T x, T y ) const // inline { return x>y; } }; Использование: greater cmp; if (cmp()(x, y)) { …}

Биндеры Биндеры позволяют получать из функции с двумя аргументами функцию с одним аргументом, зафиксировав второй: g(x)=f(x,c), c – константа В случае функциональных типов из STL (greater) мы фиксируем один параметр и получаем усеченный функциональный тип. В STL для этих целей есть два класс binder2nd и binder1st, а также две функции bind2nd и bind1st.

Биндеры (2) binder2nd определяется так: template class binder2nd; Используется так: binder2nd > positive(greater (),0); if ( positive()(x)) { … } Функция bind2nd определяется так: template binder2nd bind2nd ( const FuncType& fob, const T& c ); Используется так: if ( bind2nd(greater (),0)() ) { … }

Биндеры (3) Зачем нужны бендеры? Вспомним про функцию find3 из 13 лекции: template T* find3 ( T* pool, int n, Comparator comp ) { T* p = pool; for ( int i = 0; i<n; i++ ) { if ( comp(*p) ) return p; // success p++; } return 0; // fail } Допустим мы хотим найти первый элемент массива, строго больший 3. Это делается так: int a[] = {1, 2, 3, 4, 5}; int *r = find3(a, 5, std::bind2nd(std::greater (), 3)); Не нужно писать свой функтор, реализующий проверку!!!

vector Класс vector это объектный вариант обычного динамического массива. vector хранит набор элементов ОДНОГО типа Страуструп пишет: dont use C++ arrays; use vectors instead vector безопаснее, чем обычный массив: –Отладочная версия STL может проверять выход за границы массива –Уже реализованы алгоритмы перераспределения памяти при увеличении количества элементов. Накладные расходы при использовании vector минимальны. Большая часть функций встраивается

vector Класс vector находится в пространстве имен std как и вся STL: namespace std { template > class vector { }; } T – тип элементов Allocator позволяет реализовывать свои способы управления памятью

Свойства vector Последовательный контейнер с изменяемым размером Предоставляет доступ к произвольным элементам Реализует эффективные операции добавления и удаления в конце массива Операции добавления и удаления в произвольном месте не эффективны

Вложенные типы vector vector определяет несколько вложенных типов: template class vector { // Для получения доступа к элементам вектора typedef... value_type; // T typedef... reference; // T& typedef... const_reference; // const T& typedef... pointer; // T* typedef... const_pointer; // const T* // Для использования в алгоритмах typedef... iterator; typedef... const_iterator; typedef... reverse_iterator; typedef... const_reverse_iterator; // Для вычисления расстояния между элементами typedef... difference_type; // Для получения размеров вектора typedef... size_type; }

Создание экземпляров вектора Для использование класса vector надо подключить заголовочный файл vector. vector предоставляет 4 конструктора и не виртуальный деструктор –vector() – конструктор по умолчанию создает пустой вектор –vector ( size_type n, const T& e = T()) - создает вектор из n элементов, каждый из элементов равен e. –vector ( const vector & v ) – конструктор копирования –vector ( const_iterator f, const_iterator l); - создает вектор размером l-f и кладет туда элементы из интервала [f;l). f и l могут быть итераторами из любого контейнера (vector, list) –деструктор не виртуальный, значит наследоваться от vector не стоит.

Создание экземпляров класса (2) typedef vector IntVector; IntVector v1; // пустой вектор IntVector v2(5,-3); // вектор из 5 элементов, каждый из которых равен -3 IntVector v3(5); // вектор из 5 нулей IntVector v4(v2); // копия вектора v2 IntVector v5(v2.begin()+1,v2.begin()+5); // вектор из 4 элементов v2 начиная со второго.

Оператор индексирования Класс vector содержит две версии оператора индексирования: reference operator[] ( size_type n ); const_reference operator[] ( size_type n )const; Пример: vector v1, v2; int i; v1[0] = v2[3]*2+7.0; fun(v2[i+1]); float f = v1[i]+v2[i+3]; Синтаксис такой же как и при работе с динамическим массивом.

Оператор присваивания Класс vector поддерживает присваивание: vector & operator= ( const vector & v ); Пример: vector v1(7,2.8), v2; v2 = v1;

Доступ к первому и последнему элементам Вектор реализует 4 метода: reference front(); reference back(); const_reference front() const; const_reference back() const; Пример: vector v(5); v.front() = 3; v.back() = 7; int x = v.front(); // 3

Поддержка итераторов Вектор реализует 4 метода, позволяющие получить итераторы для первого элемента и элемента, следующего за последним: iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; Пример: typedef vector Vector; typedef Vector::iterator Iterator; Vector v(10,5); int n = 0; for ( Iterator i = v.begin(); i != v.end(); i++,n++ ) { *i = n; } При добавлении или удалении элементов в/из вектора ВСЕ итераторы становятся невалидными!!!

Добавление в конец и удаление с конца Вектор предоставляет два метода: void push_back (const T& x) - добавляет элемент в конец void pop_back (void) - удаляет элемент с конца Добавление в произвольное место не так эффективно как добавление в конец. Пример:

Добавление в произвольное место Класс vector предоставляет три метода для добавления в произвольное место: 1. iterator insert ( iterator position,const T& x) – вставляет элемент x в указанную позицию, возвращает итератор для этой позиции 2. void insert ( iterator position, size_type n, const T& x ) – вставляет n копий элемента x в указанную позицию 3. void insert ( iterator position, iterator f, iterator l ) – вставляет элементы из интервала [f;l) в указанную позицию Добавление в произвольное место не так эффективно как добавление в конец. При добавлении элемента в массив итераторы могут стать невалидными!

Добавление элемента в произвольное место (2) Примеры:

Удаление элемента из произвольного места Класс vector предоставляет два метода для удаления элемента из произвольного места: iterator erase ( iterator position ) – удаление одного элемента из указанной позиции iterator erase ( iterator first, iterator last ) – удаление нескольких элементов из интервала [first;last) Метод clear эквивалентен erase(begin(), end()); Удаления из произвольного места не так эффективно как удаление последнего При удалении элемента из массив итераторы могут стать невалидными! Включая удаляемый итератор!!!

Удаление элемента из произвольного места (2) Примеры:

Размеры вектора Класс vector предоставляет 6 методов для получения различных размеров массива и для управления этим размером: size_type size ( void ) const – возвращает текущее количество элементов массива size_type max_size ( void ) const – возвращает максимальное количество элементов массива (1 миллиард) bool empty ( void ) const – возвращает true если массив пустой size_type capacity ( void ) const – возвращает емкость массива void reserve ( size_type n ) – изменяет емкость массива void resize(size_type n) – изменяет размер массива Разница между размером и емкостью:

Специализация vector Использование vector для хранения флагов было бы не так эффективно, если бы не специализация, хранящая каждый флаг в одном бите. Поведение специализации такое же, как и у обычного вектора. Интересный вопрос, что должен вернуть operator[] для этой специализации. Ведь ссылку на бит вернуть нельзя!

Специализация vector (2) На самом деле, эта специализация определяет свою версию классов reference, iterator и пр. Для примера рассмотрим класс reference: class reference : … { public: reference& operator=(bool _Val) { // установили нужный бит } operator bool() const { // получили нужный бит } }; Класс reference хранит ссылку на класс vector плюс индекс байта и бита с которым он должен работать. Эта информация используется в operator= и operator bool. reference в данном случае это proxy-класс.

Класс list Класс list это стандартная реализация двунаправленного списка Последовательный контейнер с изменяемым размером Реализует эффективные операции добавления и удаления в произвольное место Не предоставляет доступ к произвольным элементам. Только последовательный, через итераторы

Класс list (2) Находится в пространстве имен std Начальное определение list аналогично вектору: namespace std { template > class list { }; } –T – тип элементов –Allocator позволяет реализовывать свои способы управления памятью С точки зрения использования list почти эквивалентен vector

Те же типы … list определяет несколько вложенных типов: template class list { // Для получения доступа к элементам списка typedef... value_type; // T typedef... reference; // T& typedef... const_reference; // const T& typedef... pointer; // T* typedef... const_pointer; // const T* // Для использования в алгоритмах typedef... iterator; typedef... const_iterator; typedef... reverse_iterator; typedef... const_reverse_iterator; // Для вычисления расстояния между элементами typedef... difference_type; // Для получения размеров списка typedef... size_type; }

Те же конструкторы … Для использование класса list надо подключить заголовочный файл list. lst предоставляет 4 конструктора и не виртуальный деструктор –list() – конструктор по умолчанию создает пустой список –list ( size_type n, const T& e = T()) - создает список из n элементов, каждый из элементов равен e. –lst( const list & v ) – конструктор копирования –list( const_iterator f, const_iterator l); - создает вектор размером l-f и кладет туда элементы из интервала [f;l) f и l могут быть итераторами из любого контейнера (vector, list) –деструктор не виртуальный, значит наследоваться от list не стоит.

Тот же пример использования … typedef list IntList; IntList v1; // пустой список IntList v2(5,-3); // список из 5 элементов, каждый из которых равен -3 IntList v3(5); // список из 5 нулей IntList v4(v2); // копия списка v2 IntList v5(v2.begin()+1,v2.begin()+5); // список из 4 элементов v2 начиная со второго.

Операторы индексирования и присваивания Оператор индексирования не поддерживается!!! Класс list поддерживает присваивание: list & operator= ( const list & v ); Пример: list v1(7,2.8), v2; v2 = v1;

Общие операции list как и vector поддерживают следующие операции: –front() и back() – для доступа к первому и последнем элементам –begin() и end() – для доступа к элементам через итераторы –push_back() и pop_back() – для вставки/удаления элемента в конец –insert(), erase() и clear() - для вставки/удаления элемента в произвольное место или очистки всего списка –size(), max_size(), empty() – для получения размера списка

Вставка/удаление в начало Список поддерживает эффективные операции вставки элемента в начало и удаления элемента с начала: –void push_front (const T& x) – вставка элемента в начало списка –void pop_front (void) – удаление элемента из начала списка

Вставка/удаление в начало (2) Пример:

splicing list поддерживает splicing т.е. перемещение элементов из одного списка в другой: 1. void splice (iterator position,list & x); - перемещает элементы из списка x в позицию position и очищает x. 2. void splice (iterator position,list & x, iterator i ) – перемещает указанный элемент из списка x в позицию position и удаляет его из x. 3. void splice (iterator position, list & x, iterator first, iterator last) – перемещает множество элементов [first, last) из списка x в позицию position, после чего удаляет их из x.

splicing (2) Пример:

Удаление элементов Список поддерживает эффективное удаление элементов: 1. void remove ( const T& value) – удаляет все копии указанного элемента 2. void remove_if ( Predicate pred) – удаляет все элементы для которых pred(*i) равен true 3. void unique() – удаляет элемент, если он равен своему предшественнику 4. void unique(Predicate pred) – удаляет элемент i, если Pred(*I, *(i-1)) равен true

Удаление примеров (2) Пример:

Слияние двух списков list поддерживает эффективную реализацию слияния: 1. void merge ( list & x) – перемещает все элементы из списка x в свой. x становится пустым. Оба списка должны быть отсортированы по возрастанию с использованием стандартного опетора <. 2. void merge ( list & x, Compare comp) – то же самое, но критерий сортировки задается компаратором comp

Слияние двух списков (2) Пример:

Сортировка Список реализует операцию слияния, более эффективную чем std::sort (для списка) 1. void sort ( void) – сортирует список по возрастанию, используя стандартный оператор < 2. void sort ( Predicate pred ) – тоже самое, но используя заданный компаратор. Список поддерживает эффективную версию алгоритма std::reverse 1. void reverse() – меняет порядок элементов на обратный

Сортировка (2) Пример:

Класс deque Класс deque реализует последовательный контейнер в произвольным доступом Поддерживается операция эффективная вставка и удаление элементов в начало и конец Вставка и удаление элементов в середину контейнера занимает в среднем линейное время Находится в пространстве имен std Для использования необходимо подключить заголовочный файл deque В целом, аналогичен vector

Адаптеры STL содержит классы stack, queue и priority_queue. Эти классы реализованы как адаптеры для vector, list, deque (каждый по своему) Имеем класс Primary, реализующий некую общую структуру данных: template class Primary { public: typedef... T1; typedef... T2; void f1 ( T ); T f2 ( void ); };

Адаптеры (2) На базе этого класса можно построить более специализированную структуру данных: template class Adaptor { protected: Container c; public: typedef typename Container::T1 T1; T f2 ( void ) { return c.f2(); } void f3 ( void ); }; И использовать ее вот так: typedef Adaptor > PrimaryAdaptor;

Класс queue Находится в пространстве имен std Для его использования достаточно подключить файл queue Реализует структуру данных очередь, поддерживающую операции: –push(const T&) – добавление в конец –void pop() – удаление из начала Помимо этого, поддерживает операции size, empty, front, back и конструктор по умолчанию. Строится на базе deque или list. (Deque по умолчанию)

Класс stack Находится в пространстве имен std Для его использования достаточно подключить файл stack Реализует структуру данных очередь, поддерживающую операции: –push(const T&) – добавление в конец –void pop() – удаление из конца –T& top() – возвращает элемент с вершины стека Помимо этого, поддерживает операции size, empty, и конструктор по умолчанию. Строится на базе vector, deque или list. (Deque по умолчанию)

49 Спасибо за внимание Вопросы?