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

Темы Введение в обобщенное программирование Краткий обзор STL Итераторы Категории итераторов

Обобщенное программирование Def: Обобщённое программирование это парадигма программирования, заключающаяся в написании алгоритмов, которые можно применять к различным типам данных. Обобщенное программирование реализуется в C++ посредством шаблонов. В других языках для этого есть свои механизмы Самый известный пример использования ОП это Standard Template Library или STL. Автор ОП: Alex Stepanov

Краткий обзор STL STL это не коллекция неких функций, классов но коллекция паттернов. Основные паттерны: –Контейнеры обобщенные структуры данных, хранящие данных любых типов –Алгоритмы Коллекция наиболее часто встречающихся алгоритмов, оперирующих над структурами данных Для каждого алгоритма приведены оценки его сложности. –Итераторы Механизм, позволяющий в обобщенной форме обращаться к элементам контейнеров. Позволяют применять любые алгоритмы к любым контейнерам.

Краткий обзор STL (2) Дополнительные сущности: –Функциональные объекты Все что угодно, поддерживающее оператор вызова функции operator(). –Адаптеры Преобразуют одни классы в других. Например, класс stack построен на базе deque. –Распределители памяти Позволяют настроить стратегию выделения памяти в контейнерах –Трейтсы Предоставляет унифицированный доступ к различным характеристикам.

Краткий обзор STL (3) Контейнеры – коллекция шаблонных классов, реализующих часто- употребимые структуры данных: –вектора (динамические массивы) –Списки –Множества –Словари А также: –Деки (списки в которых можно вставлять и удалять данных с обоих концов) –Очереди –мульти-множества и мульти-словари в которых элементы могут встречаться несколько раз

Краткий обзор STL (3) Алгоритмы - Коллекция наиболее часто встречающихся алгоритмов, оперирующих над структурами данных. –Реализованы в виде шаблонных функций. –В библиотеке представлены следующие алгоритмы: сортировка поиск сравнение добавление, удаление, замена элементов контейнера … В STL алгоритмы это не часть контейнеров а отдельные сущности!

Краткий обзор STL (4) Итераторы – нечто, позволяющее обращаться к элементам контейнерам в общем виде. –Итератор это тип, и любой тип является итератором, если он реализует определенный набор операций –Можно считать, что итераторы это обобщенные указатели –С другой стороны, итераторы это интерфейс между контейнерами и алгоритмами. Итераторы бывают нескольких типов: –Input iterators – аналог const указателей –Output iterators – аналог обычных указатели –Forward iterators – итератор может двигаться только в одну сторону по структуре данных –Bidirectional iterators – итератор может двигаться в обе стороны –Random access iterators – итератор предоставляет доступ к произвольным элементам последовательности. –Variations: reverse iterators etc.

Итераторы Давайте опять рассмотрим нашу функцию find: const int* find0 ( const int* array, int n, int x ) { const int* p = array; for ( int i = 0; i<n; i++ ) { if ( *p == x ) return p; // success p++; } return 0; // fail } Функция имеет следующие ограничения: –Ищет только целые значения –Ищет только в массиве –Требует указания адреса первого элемента массива –Требует указания размера массива

Итераторы (2) Вторая версия функции find: template T* find1 ( T* array, int n, const T& x ) { T* p = array; for ( int i = 0; i<n; i++ ) { if ( *p == x ) return p; // success p++; } return 0; // fail } Недостатки этой версии –Мы все равно работаем только с массивами –Нам нужен адрес первого элемента массива –Нам нужен размер массива –Мы используем оператор ++ для перехода между элементами массива

Итераторы (3) Третья версия find: template T* find2 ( T* array, T* beyond, const T& x ) { T* p = array; while ( p != beyond ) { if ( *p == x ) return p; // success p++; } return 0; // fail } Теперь мы не указываем размер массива, вместо этого мы указываем адрес элемента, следующего за последним:

Итераторы (4) Четвертая версия find: template T* find3 ( T* array, T* beyond, const T& x ) { T* p = array; while ( p != beyond ) { if ( *p == x ) return p; // success p++; } return beyond; // instead of 0 } Использование 0 как индикатора проблемы было удобно для массивов, но в общем случае это не правильно. beyond это элемент следующий за последним, т.ч. это такой же левый элемент как и 0.

Итераторы (5) Пятая версия find: template T* find4 ( T* first, T* beyond, const T& x ) { T* p = first; while ( p != beyond && *p != x ) p++; return p; // the result } Код упростился: –Остался только один оператор return –Теперь у нас есть одна проверка вместо двух. Это работает быстрее. Мы переименовали array в first, т.к. мы хотим уйти от массивов Однако здесь мы требуем, что бы результатом операции ++ к типу T* был следующий элемент из контейнера. Как мы этого добьемся?

Итераторы (6) Заключательная версия find: template P find5 ( P first, P beyond, const T& x ) { P p = first; while ( p != beyond && *p == x ) p++; return p; } Функция find5 ищет указанный элемент в структуре данных, хранящей элементы типа T. –T должен поддерживать оператор != –T будем называть типом значения. Доступ к элементам структуры осуществляется через объект типа P. –P должен поддерживать оператор *, позволяющий получить значение типа T. –P должен поддерживать оператор ++, возвращающий следующий элемент контейнера –P должен поддерживать оператор != –P будем называть итератором.

Итераторы (7) Пример использования: int A[100]; // Initializing A... int* p1 = find1(A,100,7); int* p2 = find5(A,&A[100],7);

Для дотошных Почему операция &A[100] корректна. Мы ведь выходим за границы массива? Цитата из стандарта C++ (раздел 5.7):

Алгоритмы Давайте теперь попробуем применить find5 не к массиву, а например к списку. Массив Список Типint A[100];SingleList l; ИтераторInt *??? Рассмотрим типичную реализацию списка: class SingleList { public: class Node { … private: int value; Node *pNext; }; private: Node *pFirst; Node *pLast; };

Алгоритмы (2) Для того, чтобы класс SingleList можно было использовать с find5 мы должны сделать следующее: 1. Node должен быть value-типом 2. На базе Node должен быть реализован класс, предоставляющий интерфейс итераторов 3. Делаем поддержку итераторов в SingleList 1. Делаем Node value-типом: class Node { public: bool operator!=(const Node& rhs) const { return value != rhs.value; } operator int() const { return value; } private: int value; Node *pNext; };

Алгоритмы (3) 2. Делаем итератор class iterNode { public: iterNode(Node *node) : p(node) {} bool operator!=(const Node& rhs) const { return p != rhs.p; } int operator*() const { return p->value; } operator Node*() { return p; } iterNode& operator++() {p = p->next; return *this; } iterNode operator++(int) { iterNode temp(p); p = p->next; return temp; } private: Node *p; };

Алгоритмы (4) 3. Делаем поддержку в SingleList: class SingleList { public: iterNode begin() { return iterNode(pFirst); } iterNode end() {return iterNode(0); } private: Node *pFirst, *pLast; }; 4. Пример использования: SingleList l; find5(l.begin(), l.end(), 1); // Тоже самое, что и для массивов с точностью до способа получения начала и конца последовательности.

Алгоритмы (5) Итого: 1. Мы реализовали обобщенный алгоритм поиска 2. Мы применили алгоритм к двум разным структурам данных 3. Мы увидели, что после определенных изменений в коде алгоритм стал применяться к этим структурам одинаково. Теперь попробуем применить другой алгоритм, например reverse

Алгоритмы (6) Алгоритм reverse меняет местами элементы последовательности: template void reverse1 ( P start, P beyond ) { while ( start < beyond ) { --beyond; swap(*start,*beyond); ++start; } В этом алгоритме часть требований к итераторам осталась прежней, а часть изменилась: 1. Операторы ++, !=, * еще нужны 2. Теперь нам нужны операторы < и – 3. Оператор * должен возвращать ссылку, а не значение

Алгоритмы (7) Можем ли мы применить reverse1 к массиву чисел? int A[100]; reverse1(A,&A[100]); Итераторы для массивов поддерживают все необходимые нам операторы и результат оператора int * может быть использован в левой части выражения. Можем ли мы применить reverse1 к списку? SingleList l; reverse1(l.begin(),l.end()); не можем. Итераторы списка не поддерживают --, < и результат оператора * не может быть использован в левой части.

Алгоритмы (8) Окончательная версия reverse: template void reverse2 ( P start, P beyond ) { while ( start != beyond ) { --beyond; if ( start != beyond ) { T t = *start; *start = *beyond; *beyond = t; ++start; } Мы избавились от двух дополнительных требований: 1. Оператор < нам не нужен. 2. Результат оператора * не обязан быть ссылкой. Однако это послабление привело к усложнению кода алгоритма. Т.ч., наверное лучше оставить swap и требование про ссылку. Нам осталось только реализовать оператор --. Это делается по аналогии с ++. (плюс переработать оператор *, чтобы он возвращал ссылку)

Категории итераторов Таким образом, разные алгоритмы требуют итераторов с разными возможностями. Классификация итераторов, введенная ранее позволяет указать для каждого алгоритма, итератор какого типа ей нужен: –find5 требует input iterator –reverse2 требует bidirectional iterator

Категории итераторов (2) Теперь мы вполне можем дать нормальные определения для типов итераторов: 1. Все итераторы поддерживают операции ==, =, != 2. Input итератор поддерживает операцию ++ в обоих вариантах, а также получение значения. 3. Output итератор поддерживает операцию ++ в обоих вариантах, а также установку значения. 4. Forward итератор обладает свойствами как input так и output итераторов. 5. Bidirectional итератор обладает свойствами forware iterator, плюс поддерживает операцию – в обоих вариантах. 6. Random access итератор обладает свойствами bidirectional iterator плюс поддерживает операции +, -, +=, -=,, =. Обычные указатели это и есть random access итераторы. Кроме того, итераторы могут быть простыми и неизменяемыми. (const) 1. В простом итераторе операция *I вернет обычную ссылку 2. В const итераторе она вернет const-ссылку. 3. const итераторы могут обладать всеми свойствами random access итератора кроме свойств output итератора.

Категории итераторов (3) Для каждого типа итераторов в STL существуют классы тэги: namespace std { struct input_iterator_tag { }; struct output_iterator_tag { }; struct forward_iterator_tag : public input_iterator_tag { }; struct bidirectional_iterator_tag : public forward_iterator_tag { }; struct random_access_iterator_tag : public bidirectional_iterator_tag { }; }; STL использует тэги для выбора эффективного алгоритма в зависимости от типа итератора. (подробнее, см. далее)

Категории итераторов (4) Зачем нужны итераторы? В стандарте C++ (24.3.3) по этому поводу написано: It is often desirable for a template function to find out what is the most specific category of its iterator argument, so that the function can select the most efficient algorithm at compile time. Другими словами, некий алгоритм может иметь одну версию для random-access итераторов, и другую версию для input итераторов. Скорее всего, первая версия будет эффективнее. Подробный пример будет ниже

Категории итераторов (5) Рассмотрим алгоритм size, возвращающий размер контейнера: template DIFF size ( Iterator first, Iterator beyond ) { return // The difference between first & beyond iterators } Что мы поставим вместо DIFF? В чем выражается difference между итераторами? Будем считать, что difference это атрибут итератора. И перепишем наш алгоритм вот так: template Iterator::diff_type size ( Iterator first, Iterator beyond ) { return // The difference betweenfirst & beyond iterators } Самое время вспомнить про трейтсы.

Категории итераторов (6) В STL каждый итератор обязан определять набор типов, описывающих его поведение: class MyIterator { public: typedef ptrdiff_t difference_type; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; }; Таким образом, в STL алгоритм size имел бы вид: template Iterator::difference_type size ( Iterator first, Iterator beyond ) { return // The difference betweenfirst & beyond iterators }

Категории итераторов (7) При реализации своего итератора есть три опции: 1. Определить его вручную как мы делали на прошлом слайде. 2. Унаследовать его от класса iterator 3. Сделать специализацию класса iterator_traits. STL содержит стандартный класс iterator, реализующий большую часть нужных нам функций: template struct iterator { typedef T value_type; typedef Distance difference_type; typedef Category iterator_category; … }; Наш итератор теперь можно реализовать следующим образом: class MyIterator : public iterator { … };

Категории итераторов (8) В STL существует класс iterator_traits определяющий атрибуты итераторов: template struct iterator_traits { typedef typename It::difference_type difference_type; typedef typename It::value_type value_type; typedef typename It::iterator_category iterator_category;... }; Мы можем специализировать этот класс для нашего итератора следующим образом: template struct iterator_traits > { typedef ptrdiff_t difference_type; typedef T value_type; typedef bidirectional_iterator_tag iterator_category; }; Использование: typedef MyContainer container; typedef iterator_traits iterator; container c; iterator i1, i2; i1 = c.begin(); i2 = --c.end(); find(i1,i2,1.234);

Категории итераторов (9) Давайте вернемся к нашему алгоритму traverse: template inline void traverse ( Iterator first, Iterator last ) { typedef iterator_traits attrs; typedef typename attrs::iterator_category category; traverse(first, last, category() ); // вызов перегруженной функции в зависимости от категории итератора } Или так: template void traverse ( Iterator first, Iterator last, bidirectional_iterator_tag ) { // More generic, but less efficient algorithm: Assume Iterator is only bidirectional } Или так: template void traverse ( Iterator first, Iterator last, random_access_iterator_tag ) { // More efficient, but less generic algorithm: Assume Iterator is random access }

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