И.А. Волкова, А.В. Иванов, Л.Е. Карпов - Основы объектно-ориентированного программирования. Язык программирования С++ (1114893), страница 17
Текст из файла (страница 17)
При организации цикла для последовательного обращения к элементам контейнера окончание цикла фиксируетсяна основе применения специальной функции для сравнения с концом последовательности элементов контейнера.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) реализуют некоторые распространенныеоперации с контейнерами, которые не реализуются методами каждого изконтейнеров (например, просмотр, сортировка, поиск, удаление элементови прочие). Такие операции являются универсальными для любого из контейнеров и поэтому находятся вне этих контейнеров.
Зная, как устроены алгоритмы, можно писать необходимые дополнительные алгоритмы обработки,которые не будут зависеть от контейнера.Каждый алгоритм представлен шаблоном функции или набором шаблонов функций. Все стандартные алгоритмы находятся в пространстве именstd, а их объявления — в библиотечном файле ‹algorithm›.Можно выделить три основные группы алгоритмов:1) Немодифицирующие алгоритмы, те, которые извлекают информацию из контейнера (о его устройстве, об элементах, которые таместь и т.
д.), но никак не модифицируют сам контейнер (ни элементы, ни порядок их расположения).Примеры:— find() — поиск первого вхождения элемента с заданным значением;— count() — количество вхождений элемента с заданным значением;— for_each() — для применения некоторой операции к каждому элементу, не изменяющей элементы контейнера.2) Модифицирующие алгоритмы, которые каким-либо образом изменяют содержимое контейнера.
Либо сами элементы меняются,либо их порядок, либо их количество.Примеры:— transform() — для применения некоторой операции к каждому элементу, изменяющей элементы контейнера в отличие от алгоритмаfor_each;— reverse() — переставляет элементы в последовательности;117Стандартная Библиотека шаблонов STL—copy() — создает новый контейнер.3) Сортировка.Примеры:sort() — простая сортировка;— stable_sort() — сохраняет порядок следования одинаковых элементов;— merge() — объединяет две отсортированные последовательности.—16.5.
Достоинства и недостаткиSTL-подходаДостоинстваНедостаткиКаждый контейнер обеспечиваетстандартный интерфейс в виде набора операций, так что один контейнерможет использоваться вместо другого, причем это не влечет существенного изменения кодаКонтейнеры не имеют фиксированного стандартного представления.Они не являются производными отнекоторого базового класса. Это жеверно и для итераторов. Использование стандартных контейнеровДополнительная общность исполь- и итераторов не подразумевает низования обеспечивается через стан- какой явной или неявной проверкитипов во время выполнения.дартные итераторы.Каждыйконтейнерсвязанс распределителем памяти (аллокатором), который можно переопределить с тем, чтобы реализовать собственный механизм распределения памяти.Для каждого контейнера можно определить дополнительные итераторыи интерфейсы, что позволит оптимальным образом настроить его длярешения конкретной задачи.Контейнеры по определению однородны, т.е.
должны содержать элементы одного типа, но возможносоздание разнородных контейнеровкак контейнеров, содержащих указатели на общий базовый класс.Алгоритмы, входящие в состав STL,предназначеныдляработыс содержимым контейнеров. Все алгоритмы представляют собой шаблонные функции, следовательно, ихможно использовать для работы118Каждый доступ к итератору приводит к вызову виртуальной функции.Эти затраты по сравнению с вызовомобычной функции могут быть значительными.Предотвращение выхода за пределыконтейнера по-прежнему возлагаетсяна программиста, при этом каких-тоспециальных средств для такогоконтроля не предлагается.Стандартная Библиотека шаблонов STLс любым контейнером.16.6.
Контейнер векторtemplate <class T , class A = allocator <T> > сlass vector{// vector — имя контейнера,// T — тип элементов контейнера (value_type),// A — распределитель памяти (allocator_type) —необязательный параметр........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;//////////////////Конструкторы:Конструкторы, которые могут вызываться с однимпараметром, для предотвращения случайногопреобразования объявлены explicit.Это означает, что конструктор может вызыватьсятолько явно:vector<int>v=10 - ошибка, попытка неявногопреобразования числа 10 в vector<int>explicit vector ( const A&=A() );// конструктор умолчания — создается вектор нулевой// длиныexplicit vector ( size_type n, const T& value = T(),const A& = A() );// создается вектор из n элементов со значением value// (или со значениями типа Т, создаваемыми поумолчанию,// если второй параметр отсутствует.
в этом случае// конструктор умолчания в классе Т — обязателен)119Стандартная Библиотека шаблонов STLtemplate <class I> vector ( I first, I last,const A& = A() );// I - итератор. Инициализация вектора копированием// элемента, на который указывает итератор first, вовсе// элементы из диапазона [first, last) (уже было// отмечено, что функция end() возвращает итератор,// который указывает на элемент, следующий запоследним// элементом).vector ( const vector < T, A > & obj );// конструктор копирования~vector(); // деструктор// . . .// Некоторые методы класса vector//vector& operator = ( const vector < T, A > & obj );bool empty () const{...}//истина, если контейнер пустsize_type size () const{...} //выдача текущего размераiterator insert ( iterator i, const T& value ){...}// вставка перед элементомiterator insert ( iterator i, size_type number,const T & value ){...}// вставка нескольких одинаковых элементов передэлементомvoid push_back ( const T&value ){insert ( end(),value );}//вставка в конец контейнера120Стандартная Библиотека шаблонов STLvoid clear (){erase ( begin(), end() );}// уничтожение всех элементов, при этом память не// освобождается, так как деструктор самого вектора не// вызываетсяiterator erase ( iterator i ){...return ( i );}// уничтожение заданного элемента и выдача// итератора элемента, следующего за удалённымiterator erase ( iterator start, iterator finish )// уничтожение диапазона [start,finish) и выдача// итератора элемента, следующего за последним// удалённым{...return ( finish );}// уничтожение последнего элементаvoid pop_back (){erase (end() - 1);}// содержимое первого элементаreference front (){return * begin ();}// содержимое последнего элементаreference back (){return *(end () — 1);}reference operator [](size_type i){121Стандартная Библиотека шаблонов STLreturn * (begin () + i); // индексация вектора}/* (аналог индексации) выдает содержимое элемента i.Метод at() может возбудить исключение out_of_range.
*/reference at (size_t i){ ... }}Для организации поиска в контейнере в обратном порядке (от конца кначалу) обычно пишутся такие циклы: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 ();}Применив обратный итератор, можно воспользоваться библиотечнойфункцией поиска со всеми её преимуществами и без потери эффективности:template <class C> typename C::const_iterator find_last (const C& c, typename C::value_type v){typename C::const_reverse_iterator ri = find (c.rbegin (), c.rend (), v);if ( i == c.rend ()return c.end ();typename C::iterator i = ri.base ();return --i;}Для обратного итератора выполнение операции ri.base() выдаёт значение типа iterator, указывающее на один элемент вперёд позиции, на которуюуказывает сам обратный итератор ri.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
