Язык программирования Си++ (1119468), страница 12

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

Текст из файла (страница 12)

Итераторы ввода (InputIterator)2. Итераторы вывода (OutputIterator)3. Однонаправленные итераторы (ForwardIterator)4. Двунаправленные итераторы (BidirectionalIterator)5. Итераторы произвольного доступа (RandomAccessIterator)• Различные итераторы иерархически вложены друг в друга: Однонаправленные итераторы объемлют итераторыввода и вывода Двунаправленные итераторы объемлютоднонаправленные итераторы Итераторы произвольного доступа объемлютдвунаправленные итераторы246Итераторы STL• Итераторы различныхвидов иерархическивложены друг в друга• Иерархическиобъемлющиеитераторыудовлетворяют всемтребованиямвложенных в нихитераторов и могутиспользоваться вместонихИтератор произвольного доступаДвунаправленный итераторОднонаправленный итераторИтераторвводаИтераторвывода247Операции в иерархии итераторовИтераторыЧтение Доступ Запись Изменение СравнениеВывода*p=eВводаx=*pp->fОднонаправленныеx=*pp->fДвунаправленныеx=*pp->fПроизвольныйдоступx=*pp->fp[n]p++ ++pp++ ++pp==q p!=q*p=ep++ ++pp==q p!=q*p=ep++ ++pp-- --pp==q p!=q*p=ep++p-p+np–np+=n++p--p p==q p!=qn+pp<q p>qp-q p>=q p<=qp-=nИтераторы STL• При описании алгоритмов, входящих в STL, принятосоглашение об использовании стандартных имёнформальных параметров, в зависимости от названияитератора в профиле алгоритма, должениспользоваться итератор уровня “не ниже, чем”• По именам параметров шаблона можно понять,какого рода итератор нужен, к какому контейнеруприменим этот алгоритм:template <class InputIterator, class T>size_type count (InputIterator start,InputIterator finish, const T& value);249Итераторы STL••Для продвижения итераторов на заданное расстояние (прибавление целогочисла к итератору) и определения расстояния между элементамиконтейнеров (вычисление разности итераторов) в библиотеке имеютсяшаблоны функций: advance () и distance ()Операция advance (i, n) может иметь отрицательное значение параметра nтолько для двунаправленных итераторов и итераторов произвольногодоступа, эта функция продвигает итератор i на n позиций вперёд или назадtemplate <class InputIterator, class Distance>inline void advance (InputIterator & i, Distance n);InputIterator p; int n; /* … */ advance (p, n); // эквивалентно: p += n;•Операция distance (first, last, n) прибавляет к n число, равное количествупродвижений первого итератора (first) ко второму (last):template <class InputIterator, class Distance>inline void distance (InputIterator first, InputIterator last, Distance& n);InputIterator p, q; int n; /* … */ distance (p, q, n); // эквивалентно: n += q – p;Итераторы вывода STL• Присваивание, проводимое с помощью одного и того жезначения итератора вывода, можно сделать для данного объектатолько один раз, причём пропускать присваивание и переходитьсразу к следующему значению итератора нельзя:i, i ++; i ++;// ОШИБКА• Итератор вывода в каждый момент времени может иметь толькоодну активную копию:i = j; * ++ i = a; *j = b;// ОШИБКА• Единственным правильным использованием операцииразыменования с итераторами вывода является использованиеэтой операции в левой части операции присваиванияwhile (first != last) * result ++ = * first ++; // нет ошибки251Итераторы STL• Итераторы могут указывать на элемент, который гипотетическирасположен за последним элементом контейнера, доступ к этомугипотетическому элементу никогда не осуществляется• Итераторы могут иметь значение, не указывающее ни на какойэлемент контейнера, для таких значений результаты большинстваопераций не определены• Диапазон есть пара итераторов, задающая начало и конецвычислений• Диапазон [i, j) относится к элементам структуры данных,начинающейся с элемента, на который указывает i, и кончающейся(но не включающей) элементом j, диапазон [i, i) есть пустой диапазон• Все алгоритмы должны применяться только к правильнымдиапазонам, в которых второй итератор достижим из первого законечное число выполнения операций operator ++252Итераторы STL• Суть использования итераторов вместо обычныхуказателей состоит в том, что итераторыобладают гораздо большей общностью• Свойства итераторов описаны значительно болееточно, чем свойства простых указателей• Те свойства итераторов, которые зависят отконкретных реализаций, скрыты в реализациибиблиотеки, что повышает переносимость программ,написанных с использованием итераторов, но неснижает эффективности этих программ253Итераторы STL•Каждый контейнер содержит ряд ключевых методов, позволяющих найтиконцы последовательности элементов в виде значений итераторов:iterator begin(), const_iterator begin() const// возвращают итератор, который указывает// на первый элемент последовательностиiterator end(), const_iterator end() const// возвращают итератор, который указывает на элемент,// следующий за последним элементом последовательности••Константные итераторы позволяют контролировать модификациюэлементов контейнеров и запрещать её там, где это нужноС помощью итераторов последовательный доступ к элементам данныхконтейнерных типов осуществляется от первого элемента к последнему:после последнегоbegin ()AВСDend ()254Итераторы STL• Запись iterator p = v.begin () верна независимо от того, к какомуконтейнеру v она применяется, после такого определения *p естьпервый элемент контейнера v• Шаблонная функция find () ищет итератор заданного элемента взаданном диапазоне итераторов и выдаёт в результате значениеитератора, которым поиск заканчивается• Для достижения целей функции find () достаточно использоватьитератор ввода из контейнера, поскольку изменения значений иповторного чтения элементов не потребуется:template <class InputIterator, class T>InputIterator find (InputIterator first, InputIterator last, const T& value){ while ( first != last && * first != value ) ++ first;return first;} // Ответ: если first != last, то искомый элемент доступен, как * firstРаспределители памяти STL• Распределители памяти (аллокаторы) управляютпереносимыми средствами упрятывания информациио моделях памяти, типах указателей, типах разностиуказателей, типе размеров объектов в данной моделипамяти, а также примитивами для размещения иосвобождения памяти для данной модели• Распределители памяти позволяют свести задачураспределения памяти для сложных, составныхобъектов к совокупности более простых задачраспределения памяти для более простых(составляющих) объектов256Распределители памяти STL• Распределители памяти представляют собой классыобъектов, которые можно включать в качествепараметров в описания шаблонов других классов:template<class T, class A = allocator<T> > class vector {public:typedef typename A::pointer iterator; /* ........

*/private: A alloc;/* ........ */public:/* ........ */void reserve (size_type n){ if (n <= Nmax) return;iterator p = alloc.allocate (n); /* ........ */}257};Распределители памяти STL• В классы распределителей памяти включаютсяопределения типов, используемых для индексациисоответствующих объектов (например, тип size_type)• Эти типы могут представить самый большой объектисходного типа, соответствующий модели памяти• В распределителях памяти описывается тип,соответствующий типу результата вычитания двухитераторов (тип difference_type)• Обычно эти типы соответствуют типам size_t и ptrdiff_t,но они могут быть и иными, что зависит от природыобъектов и от выбранной модели памяти258Распределители памяти STL• Для распределителей памяти в библиотеке STLвыработаны требования, сформулированные в видеперечня операций, которые можно выполнять надобъектами классов распределителей для каждойотдельной модели памяти, к таким операциямотносятся: операции захвата памяти allocate () операции перераспределения памяти deallocate () операции конструирования указателей на объектыaddress () и т.

д.259Алгоритмы STL• Алгоритмы определяют вычислительные процедуры(просмотр, сортировка, поиск, удаление элементов, …),не реализованные методами контейнеров, но пригодныедля работы с разными составными структурами данных, втом числе с разными контейнерами• Алгоритмы являются универсальными для любого изконтейнеров и поэтому они реализованы безиспользования методов, входящих в контейнеры• Алгоритмы выражаются шаблонами функции илинаборами таких шаблонов• Стандартные алгоритмы находятся в пространстве имёнstd, а их объявления – в заголовочном файле <algorithm>260Алгоритмы STL• Алгоритмы библиотеки STL отделены от конкретныхструктур данных, над которыми они выполняются:алгоритм поиска данных не зависит от того,выполняется поиск в линейном массиве или списке• Доступ к данным осуществляется только с помощьюитераторов: о каждом алгоритме из библиотекиизвестно, с помощью какого вида итератора доступныиспользуемые в алгоритме данные• Благодаря параметризации итераторами, алгоритмыработают и со встроенными структурами данных, и соструктурами данных, определёнными пользователями261Алгоритмы STL• Обобщённые алгоритмы библиотеки:1.

Характеристики

Список файлов лекций