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

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

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

Немодифицирующие операции надпоследовательностями данных (поиск и подсчётчисла элементов): find () – первое вхождение элемента с заданнымзначением find_if () – первое вхождение элемента,удовлетворяющего заданному условию count () – количество вхождений элемента сзаданным значением for_each () – операция-параметр применяется ккаждому элементу, не меняя его262Алгоритмы STL• Обобщённые алгоритмы библиотеки:2. Модифицирующие операции надпоследовательностями данных (копирование,перестановки, преобразования, …), которыеменяют либо сами элементы контейнера, либо ихпорядок, либо их количество: transform () – операция-параметр применяется ккаждому элементу так, что содержимое контейнераменяется reverse () – переставляет элементы впоследовательности copy () – создаёт новый контейнер263Алгоритмы STL• Обобщённые алгоритмы библиотеки:3.

Операции сортировки, поиска минимума имаксимума, ускоренного поиска и т. д. sort () – простая сортировка, имеется такжесортировка по возрастанию (в данном контейнередля типа элемента должна быть определенаоперация сравнения на меньше, то есть ‘<’) stable_sort () – сортирует, но сохраняет порядокследования одинаковых элементов merge () – объединяет отсортированныепоследовательности264Алгоритмы STL• Обобщённые алгоритмы библиотеки:4. Обобщённые численные алгоритмы(суммирование, смежные разности, слияние,обобщённое скалярное произведение, …)265Алгоритмы STL• В языке Си++ критерий сравнения для функциисортировки sort () реализуется с помощью параметрашаблонной функции:template<class Iterator, class Predicate>inline void sort (Iterator First, Iterator Last, Predicate Pr){ _Sort_0 (First, Last, Pr, Val_type (First)); }/* ...

*/{ for (;; ++ First) { for (; Pr (* First, Piv); ++ First);for (; Pr (Piv, * -- Last););if (Last <= First) return First;iter_swap (First, Last);}}266Алгоритмы STL• Обобщённая функция сортировки sort () может бытьинстанциирована так, что её специализация будетупорядочивать элементы контейнера по убыванию:class IntGreater{ public: bool operator()(int x, int y) const {return x > y;} };int main (){ int x [1024]; /* ............ */ // Инициализацияsort (&x [0], &x [1024]);// По возрастаниюsort (&x [0], &x [1024], IntGreater ());// По убыванию}267Функциональные объекты STL• Функциональные объекты управляют инкапсуляциейфункций в объекте для их использования другимиобъектами• Функциональные объекты – объекты, для которыхопределена операция группирования фактическихпараметров, то есть операция operator ()• Использование функциональных объектов позволяетшаблонам алгоритмов работать не только суказателями на функции, но также и с любымиобъектами, для которых возможна операцияoperator ()268Функциональные объекты STL• Для проведения поэлементного суммирования двух векторов aи b, содержащих вещественные числа, и передачи результата ввектор a с помощью алгоритма transform () и бинарногофункционального объекта plus () можно выполнить следующее:template < class InputIterator1, class InputIterator2, class OutputIterator,class BinaryOperation>OutputIterator transform (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, OutputIterator result,BinaryOperation binary_op);template <class T> struct plus : binary_function<T, T, T>{ T operator () (const T& x, const T& y) const {return x + y;} };transform (a.begin(), a.end(), b.begin(), a.begin(), plus<double>());// res = op1 + op2 – для каждого элемента a и b269Функциональные объекты STL• Для изменения знака элементов вектора можно использоватьвариант алгоритма transform(), пригодный для унарныхопераций, и унарный функциональный объект negate(),выполняющий изменение знака без обращений к функциям:template < class InputIterator, class OutputIterator,class UnaryOperation>OutputIterator transform (InputIterator first, InputIterator last,OutputIterator result, UnaryOperation op);template <class T> struct negate : unary_function<T, T>{ T operator () (const T& x) const {return -x;} };transform (a.begin(), a.end(), a.begin(), negate<double>());// res = - op – для каждого элемента a270Адаптеры STL• Адаптеры используются для преобразованияинтерфейсов• В библиотеку включены Адаптеры контейнеров Адаптеры итераторов Адаптеры функциональных объектов• Применение адаптеров позволяет на основе базовыхклассов строить производные классы,обеспечивающие удобное и эффективноепредставление данных и операций над ними271Адаптеры контейнеров STL• Адаптеры контейнеров позволяют строить ограниченныеинтерфейсы (из базовых интерфейсов удаляются лишние операции): для векторов (vector) => priority_queue, stack для списков (list) => queue, stack для двусторонних очередей (deque) => queue, priority_queue, stack• Адаптеры контейнеров не имеют своих итераторов, предполагаяиспользование базовых итераторов, в каждом конкретном случаедля доступа к данным стека используются итераторы векторов,списков или двусторонних очередей:stack<vector<int> > // стек целых чисел на базе вектораqueue<list<char> >// очередь символов на базе списка• Адаптеры контейнеров – простые интерфейсы, создаваемые длятех контейнеров, типы которых передаются адаптерам в качествефактических параметров272Адаптеры итераторов STL• Адаптеры итераторов выполняют функции, аналогичныеадаптерам контейнеров, но преобразования интерфейсовпроизводятся в отношении классов итераторов• Двунаправленные итераторы и итераторы с произвольным доступомимеют соответствующие адаптеры обратных итераторов, которыемогут продвигаться по структурам данных в обратном направлении• Контейнеры, допускающие работу с двунаправленными итераторамии итераторами произвольного доступа, содержат методы: reverse_iterator rbegin (), const_reverse_iterator rbegin () –возвращают итератор, указывающий на первый элемент вобратной последовательности reverse_iterator rend (), const_reverse_iterator rend () – возвращаютитератор, указывающий на элемент, следующий за последним вобратной последовательности273Адаптеры итераторов STLпосле последнегоперед первымArend ()ВСbegin ()Drbegin ()end ()• С помощью обратных итераторов последовательный доступ кэлементам данных контейнерных типов осуществляется отпоследнего элемента к первому:перед первымDrbegin ()CBArend ()274Адаптеры итераторов STL• При проходе последовательности как прямым итератором p, так иобратным итератором rp переход к следующему элементузаписывается с помощью операции увеличения ++ rp (но не -- rp):template<class C> typename C::value_type sum_twice (const C& c){ typename C::value_type s1, s2;typename C::const_iterator p_p = c.begin ();s1 = 0; while (p_p != c.end ()) s1 += * (p_p ++);typename C::const_reverse_iterator p_r = c.rbegin ();s2 = 0; while (p_r != c.rend ()) s2 += * (p_r ++); return (s1 + s2) / 2; }• Примечание: Шаблонные конструкции вида “Т::х”, в которыхиспользуется имя типа T, введённое в параметрах шаблона,независимо от контекста интерпретируются как “член-данное хиз класса Т”.

В таких случаях для использования типа х из275класса Т пишут “typename T::x”.Адаптеры итераторов 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 ();}276Адаптеры итераторов STL• Применив обратный итератор, можно воспользоватьсябиблиотечной функцией поиска со всеми её преимуществами и безпотери эффективности• Операция i = ri.base () выдаёт значение i типа iterator, указывающеена один элемент вперёд позиции обратного итератора ri.&*(reverse_iterator (iterator)) == &*(iterator – 1)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 (ri == c.rend ()) return c.end ();typename C::const_iterator i = ri.base (); return -- i;} // Известно, что функция find () пользуется операцией ‘++’!Адаптеры итераторов STL• В библиотеку STL включён адаптер вставки, который заменяетобычную операцию изменения значения элементов контейнера наоперацию вставки элементов в контейнер• Для обычных классов итераторов фрагмент программыwhile (first != last) *result ++ = *first ++;означает копирование элементов диапазона [first, last) в диапазон,начинающийся с итератора result, однако, если итератор resultявляется итератором вставки, тот же самый фрагмент будетпроизводить вставку дополнительных элементов в контейнер.• Адаптеры итераторов неинициализированной памяти применяютдля записи результатов операций в неинициализированную память,то есть в память, не содержащую никаких объектов данных, прокоторую известно лишь, что её размер достаточен для хранениясоответствующего результата278Контейнер векторов (vector)• Векторы, строящиеся на основе контейнеров класса vector, посвоим свойствам напоминают обычные одномерные массивы:#include <vector>using namespace std;template<class T, class A = allocator<T> > class vector;vector& operator = (const vector <T, A> & obj);• Конструктор vector<int> v (10) задаёт вектор из 10 целых чисел,имеются и другие виды конструкторов:vector (const vector <T, A> & obj); // конструктор копированияvector (iterator first, iterator last, const A& = A ());explicit vector (const A& = A ());// требуется явный вызов:// vector<int> x (10);explicit vector(size_type size, const T&value = T(), const A& a = A());Контейнер векторов (vector)• Как и массив, вектор представляет собой непрерывнуюпоследовательность элементов, но, в отличие от обычныхмассивов, размер вектора не известен статическиbool empty () const { /* ...

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

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