![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)Содержание книги
Поиск на нашем сайте
{ while (first!= last) *result++ = *first++; return result; } У алгоритма copy есть модификация copy_backward, которая копирует элементы в обратном порядке (в отличие от copy, где необходимы входные итераторы, здесь требуются двунаправленные итераторы). Алгоритм преобразования transform также по существу является модификацией алгоритма copy, но он осуществляет копирование после применения к каждому элементу исходного контейнера некоторой операции. Определение для этого алгоритма приведено ниже. template <class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform (InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op) { while (first!= last) *result++ = op(*first++); return result; } К числу других алгоритмов рассматриваемого класса относятся replace (замена каждого появления в диапазоне контейнера некоторого значения old_value на новое значение new_value), replace_if (замена при выполнении некоторого условия-предиката), fill (заполнение диапазона контейнера заданным значением), swap (обмен местами двух значений или итераторов), remove_copy (копирование содержимого контейнера в другой, исключая заданное значение), __reverse (инвертирование порядка элементов контейнера) и т.д. Третья категория включает сортирующие алгоритмы. К их числу относятся быстрая сортировка и ее модификации, сортировка вставками и модификации, линейная вставка, сортировка слиянием, устойчивая сортировка, частичная сортировка, нахождение медианы и т.д. Наиболее распространенный алгоритм сортировки – алгоритм sort, который сортирует элементы контейнера в нужном порядке. Для обеспечения максимальной эффективности алгоритм работает в два этапа. На первом выполняется быстрая сортировка, на втором – сортировка вставками. Порядок сортировки элементов передается через функтор comp. Определение шаблона sort имеет вид template <class RandomAccessIterator, class Compare> Void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp) { if (!(first == last)) { __quick_sort_loop(first, last, comp); __final_insertion_sort(first, last, comp); } } Здесь функция __quick_sort_loop реализует основной цикл быстрой сортировки путем вызова явно рекурсивной функции __quick_sort_loop_aux. Условием завершения этого цикла является разбиение сортируемого контейнера на достаточно «короткие» сегменты, к которым можно эффективно применить сортировку вставками. Сортировку вставками выполняет функция __final_insertion_sort; сама процедура вставок в ней осуществляется через функцию линейной вставки __linear_insert.
Вместо шаблона sort для сортировки специфическим методом можно явно использовать другие шаблоны, например, __insertion_sort (сортировка вставками). Четвертая группа алгоритмов содержит обобщенные численные алгоритмы. К их числу относится, к примеру, алгоритм for_each. Этот алгоритм применяет заданный функтор к разыменованному итератору в указанном диапазоне значений итератора. Определение данного алгоритма очень простое и выглядит так: template <class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f) { while (first!= last) f(*first++); return f; } Пример использования алгоритма for_each: // функтор для суммирования значений template <class T> class sum_up { public: void operator() (const T & value) { sum += value; } const T & read_sum() { return sum; } private: static T sum; }; int sum_up<int>::sum; ... void main(void) { deque<int> d(3,2); // очередь вида 2 2 2 sum_up<int> s; // создание функтора для суммирования for_each (d.begin(), d.end(), s); // суммирование cout << s.read_sum(); // вывод суммы } Еще одним полезным алгоритмом рассматриваемой категории является accumulate. Фактически он делает то же самое, что и for_each в приведенном примере. С помощью алгоритма accumulate можно организовать, например, накапливающее суммирование или умножение с учетом начального значения. Заголовок этого алгоритма определен в виде: template <class InputIterator, class T, Function F> T accumulate(InputIterator first, InputIterator last, T init, Function F); Здесь first и last задают диапазон значений итератора, а init устанавливает начальное значение (для аддитивных операций это 0, а для мультипликативных – 1), F – функтор, определяющий вид операции. Пример vector<int> v; v.push_back(2); v.push_back(5); cout << accumulate(v.begin(), v.end(), 10, divides<int>()); Кроме рассмотренных алгоритмов, четвертая группа включает также алгоритмы inner_product, partial_sum и adjacent_difference. Функторы Функтором в STL называют объект, класс которого инкапсулирует операцию функционального вызова operator(). Функторы удобно использовать для представления предикатов и других функций, передаваемых алгоритмам (выше в примерах мы уже несколько раз использовали функторы). Простейшими стандартными функторами являются функтор отрицания и функтор суммирования. Их определения даны ниже. template <class T> // функтор отрицания
struct negate: unary_function<T, T> { T operator()(const T & x) const { return -x; } }; template <class T> // функтор суммирования struct plus: binary_function<T, T, T> { T operator()(const T & x, const T & y) const { return x + y; } }; Шаблон negate, представляющий функтор отрицания, открыто наследует от шаблона unary_function, а шаблон plus, соответствующий функтору суммирования, – от шаблона binary_function. Сами эти шаблоны, по сути, не представляют классы, поскольку не определяют никакого поведения, а лишь вводят типы данных для аргументов и результата. Их определения имеют вид: template <class Arg, class Result> struct unary_function { typedef Arg argument_type; typedef Result result_type; }; template <class Arg1, class Arg2, class Result> struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; }; Как шаблоны unary_function, binary_function, так и рассмотренные выше (и многие другие) функторы определены в заголовочном файле function.h. В этом файле имеется много разнообразных функторов, в частности, представляющие базовые логические операции, арифметические операции, операции сравнения. Кроме стандартных функторов, любая программа может содержать определенные пользователем функторы. Примеры таких определений имеются выше. Ниже приведен еще один подобный пример. В нем определяется функтор prod_odd, который возвращает логическое значение. Оно индицирует, является ли произведение аргументов функтора нечетным числом. Сам функтор используется для поиска в списке первых двух смежных значений, произведение которых нечетно. Пример template <class T> class prod_odd { public: int operator() (const T & v1, const T & v2) { return v1%2!= 0 && v2%2!= 0; } }; ... list<int> l; // заполняем список значениями ... list<int>::iterator i = // поиск стандартным алгоритмом adjacent_find adjacent_find(l.begin(), l.end(), prod_odd<int>()); if (i!= l.end()) cout << *i++ << " " *i++; else cout << "таких значений в списке нет";
Ассоциативные контейнеры Ассоциативные контейнеры – это особый вид контейнеров, которые позволяют быстро получать доступ к хранимым в них данным за счет использования механизма ключей. В STL определены следующие виды таких контейнеров: набор (set), мультинабор (multiset), отображение (map), мультиотображение (multimap). Все указанные контейнеры хранят данные сортированными, причем для обеспечения максимальной скорости получения данных в качестве «внутреннего» контейнера они используют дерево специального вида. Отличие между контейнерами set (map) и multiset (multimap) состоит в том, что set и map используют уникальные ключи для идентификации данных, а multiset и multimap нет. Для того чтобы включить поддержку рассматриваемых контейнеров, нужно подключить заголовочные файлы set.h и map.h соответственно. Шаблон set инкапсулирует свойства и операции над упорядоченным набором объектов. Ключевые данные для упорядочения – сами хранимые объекты (т.е. хранимый объект – это и данные, и ключ). Параметрами шаблона являются: тип хранимых объектов (он же – тип ключа), функтор Compare, задающий способ упорядочения объектов (по умолчанию упорядочением управляет стандартный функтор less<T>), а также аллокатор, инкапсулирующий модель памяти программы. Число, порядок и назначение параметров шаблона multiset аналогичны (ключи в multiset, напомним, необязательно уникальны, т.е. multiset может содержать один и тот же объект многократно). Примеры определения набора и мультинабора даны ниже (создать контейнер рассматриваемых классов можно также из другого ассоциативного контейнера, или из последовательности элементов с указанием диапазона значений итератора).
Примеры set < MyClass, greater<MyClass> > MyClassSet; // порядок сортировки данных задается классом greater<MyClass> multiset <MyClass> MyClassMultiSet; // а здесь порядок задается классом less<MyClass> по умолчанию
Контейнеры set и multiset включают «типичные» для всех контейнеров компонентные функции begin, end, rbegin, rend, empty, size, max_size, swap и ряд других. Действие этих функций не отличается от действия их аналогов в последовательных контейнерах. Для перебора компонент set и multiset используют двунаправленные итераторы. Присваивание выполняется операцией operator =, а сравнение операцией operator ==. Добавление объектов производится функцией insert, удаление – функцией erase. К контейнерам set и multiset применимы теоретико-множественные операции, такие как пересечение, включение элемента, разность и т.д. Пример
|
|||||||
Последнее изменение этой страницы: 2016-08-14; просмотров: 134; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.117.11.119 (0.009 с.) |