Что такое функтор c
Функторы, предикаты, функциональные адаптеры, лямбда-функции
Вступление
Статья ориентирована на программистов С++, поверхностно знающих/желающих узнать STL, в особенности, с использованием его алгоритмов. Это краткий обзор по основным понятиям, в конце будет приведен список литературы для более полного ознакомления с материалом.
Функторы
Пример использования функтора:
Данный оператор принимает две const строки по ссылке и возвращает истину если длина первой меньше длины второй. Аналогично можно было бы сделать с использованием класса при указании модификатора доступа public для operator().
Часто, функциональные объекты делают шаблонными для лучшей возможности повторного использования кода.
Заметьте, что т.к. тип T неизвестен, то указываем передачу на всякий случай по ссылке, чтобы не создавать временных объектов. При использовании шаблонного объекта обязательно явно объявлять тип в угловых скобках. Необходимо указывать в качестве аргумента название класса, выступающего объект-функцией с круглыми скобками. Вызов может происходить вот так:
Надо отметить, что в общем случае, идентификатор типа возвращаемого значения operator() у функтора может быть любой. В данной программе вызывается перегруженная версия алгоритма accumulate (определена в ), которая требует возврата того же типа данных, что и при передаче в функциональный объект, но в других алгоритмах может потребоваться и другой тип данных.
Предикаты
Предикаты- подмножество функторов, в которых тип возвращаемого значения operator() bool. Предикаты используются в алгоритмах сортировок, поиска, а также во всех остальных, имеющих на конце _if. Смысл в том, что объект-функция в случае использования предиката возвращает истину или ложь в зависимости от выполнения необходимого условия. Это либо удовлетворение объектом неких свойств, либо результат сравнения двух объектов по определенному признаку.
Пример использования предиката:
Функциональные адаптеры
Основные унарные и бинарные функциональные объекты, необходимые для сравнения, уже включены в STL и используются с добавлением хедера functional. Все они являются шаблонными классами и требуют определения необходимых операторов в типе данных, с которым работают. Примеры: std::greater<>, std::less<>.
Следующий код сортирует элементы по убыванию с применением нашего объекта.
Принцип работы std::greater схож со следующим кодом:
Иногда, нам может потребоваться реализовать, например, подсчет элементов исходя из нескольких условий, т.е. необходимо скомбинировать результаты с определенными значениями или другими функциями. В таких случаях применяют функциональные адаптеры. Необходимо отметить, что и сами адаптеры могут служить частью вычислений других адаптеров, за счет чего достигается гибкость вычислений. Основные адаптеры: bind1st, bind2nd, not1, not2.
Пример: подсчитать количество элементов, больших (>), чем два.
Данный код выведет 2. Все верно, лишь элементы 3 и 5 превосходят 2.
Лямбда-функции
Наверное, самая приятная часть 11 стандарта, которая позволяет создавать очень гибкий код прямо на месте, не расползаясь мыслью по разным специальным классам и структурам, создаваемым для сравнения, а также повышающая читаемость кода в разы, ведь критерий сравнения или необходимая для выполнения функция определяется прямо рядом с местом использования. Тем не менее, это не отменяет использование всего того, что было озвучено выше, функциональные объекты имеют право на существование и должны использоваться там, где это действительно принесет полезный результат. Например, если необходимых инструкций для выполнения в теле функции достаточно много и определение данной функции на месте понизит удобочитаемость, или если у нас есть схожие куски кода и мы хотим вынести общий в одно место. В остальных случаях, данная конструкция будет очень удобна. Она обладает множеством различных тонкостей, мы лишь покажем общее с ней ознакомление, т.к. описание всех возможностей требовало бы отдельной статьи. Я покажу лишь использование конструкций с лямбда-функциями, и вы поймете, почему её так полюбили программисты.
Пример: необходимо подсчитать количество неотрицательных элементов, кратных 7
и есть наша лямбда-функция.
Или же другой: вывести максимальный по модулю элемент
Например, следующий код значение каждого элемента увеличивает значение на единицу и выводит на экран.
Передача аргументов в лямбда-функцию может происходить как по значению, так и по ссылке. Но что делать, если нужно, например, посчитать количество элементов, кратных некоему числу k, которое введет пользователь? Для этого используется список захвата, он передается функции в квадратных скобках, аргументы перечисляются через запятую. Передача может идти также как по значению, так и по ссылке.
Ниже приведен пример, в котором подсчитывается количество элементов, кратных k и больших, чем m.
Все просто и лаконично, а главное, читаемость кода возрастает в разы. Теперь я покажу пример, где используется передача аргумента по ссылке.
Пример: подсчитать количество отрицательных элементов и отдельно количество четных, результат вывести на экран. Для простоты, используем алгоритм for_each.
Подведение итогов
Команда в Ubuntu для обновления gcc:
Литература
Если Вам понравилась статья, проголосуйте за нее
Голосов: 15 Голосовать 
Функторы в языках программирования
Функторы в C++
Функторы в Standart ML
Сложно сформулировать в терминах ООП: функторы в ML являются общими реализациями интерфейсов. В терминах ML функторы являются частью системы модулей ML и они позволяют компоновать структуры.
structure LoudPlugin :> Plugin =
struct
fun perform ( ) = print «ВЫПОЛНЯЕМ ЗАДАНИЕ ГРОМКО!\n»
end ;
structure SilentPlugin :> Plugin =
struct
fun perform ( ) = print «выполняем задание тихо\n»
end ;
structure LoudPerformer = Performer ( LoudPlugin ) ;
structure SilentPerformer = Performer ( SilentPlugin ) ;
Это, скорее всего, самый простейший пример функторов Standard ML.
Функторы в Haskell
Функторы в Haskell является тем, чем и должны быть настоящие функторы. Функторы Haskell очень напоминают математические функторы из теории категорий. В теории категорий функтор F — это отображение между категориями, такое, что структура категории сохраняется или, другими словами, это гомоморфизм между двумя категориями.
В Haskell это определение реализовано в виде простого класса типа,
Чтобы понять, что он делает, думайте о fmap как о функции, которая применяет операцию к каждому элементу в каком-то контейнере.
instance Functor [ ] where
fmap = map
Но заметьте, что определение Functor ничего не говорит о сохранении структуры! Поэтому любой нормальный функтор должен неявно удовлетворять законам функторов, которые являются частью определения математических функторов. Есть два правила fmap :
fmap > fmap (g. h) = fmap g. fmap h
Первое правило гласит, что отображение тождественной функции на каждый элемент в контейнере не имеет никакого эффекта. Второе правило гласит, что композиция двух функций над каждым элементом в контейнере то же самое, что отображение первой функции, а затем отображение второй.
Другой пример функторов, который иллюстрирует их наиболее ярко, — это операции над деревьями. Подумайте о дереве, как контейнере, а затем примените функцию fmap к значениям дерева, сохраняя структуру дерева.
Давайте, для начала, определим дерево,
data Tree a = Node ( Tree a ) ( Tree a )
| Leaf a
deriving Show
В этом определении сказано, что тип Tree (дерево) является либо Node (ветвью) из двух Tree (левой и правой ветви) или Leaf (листом). Выражение deriving Show позволяет нам осматривать дерево через функцию show.
instance Functor Tree where
fmap g ( Leaf v ) = Leaf ( g v )
fmap g ( Node l r ) = Node ( fmap g l ) ( fmap g r )
Теперь давайте проиллюстрируем, как fmap работает с деревьями. Построим дерево со строковыми ( String ) листьями и применим функцию length над ними, чтобы узнать длину каждого листа.
Prelude> let tree = (Node (Node (Leaf «hello») (Leaf «foo»)) (Leaf «baar»))
Prelude> fmap length tree
Node (Node (Leaf 5) (Leaf 3)) (Leaf 4)
Здесь у нас построено следующее дерево,
И отображение length над ним даёт нам,
Еще один способ сказать, что fmap делает — отображает (в оригинале — поднимает) функцию из «нормального мира» в » f мир».
На самом деле функтором является фундаментальным классом типа в Haskell так как Монады, аппликативные функторы и стрелки — это всё функторы. Я бы сказал, что Haskell начинается там, где начинаются функторы.
Если вы хотите узнать больше о классах типа в Haskell, начните с превосходной статьи Typeclassopedia (начинается со стр. 17).
Функторы в Prolog
И, наконец, функторы в Prolog. Функторы в Prolog самые простые из всех. Можно рассмотреть два примера. Первый — это атом в начале структуры. Например, возьмём выражение,
Вот вам и функторы в Prolog.
Заключение
В данной статье показано, как такой простой термин, как «функтор» может относиться к совершенно к разным вещам в разных языках программирования. Поэтому, когда вы слышите термин «функтор», важно знать контекст, в котором оно используется.
И, тут такое дело… мне тут сказали, что, оказывается, человек, чью статью я перевёл, есть на хабре =)
А ещё говорят, что по часть по Prolog в статье ошибочна.
Функторы (глава книги «Теория категорий для программистов»)
Это седьмая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:
Функторы
За понятием функтора стоит очень простая, но мощная идея (как бы заезжено это ни прозвучало). Просто теория категорий полна простых и мощных идей. Функтор есть отображение между категориями. Пусть даны две категории C и D, а функтор F отображает объекты из C в объекты из D — это функция над объектами. Если a — это объект из C, то будем обозначать его образ из D как F a (без скобок). Но ведь категория — это не только объекты, но еще и соединяющие их морфизмы. Функтор также отображает и морфизмы — это функция над морфизмами. Но морфизмы отображаются не как попало, а так, чтобы сохранять связи. А именно, если морфизм f из C связывает объект a с объектом b,
то образ f в D, F f, связывает образ a с образом b:
(Надеемся, что такая смесь математических обозначений и синтаксиса Haskell понятна читателю. Мы не будем писать скобки, применяя функторы к объектам или морфизмам.)
Как видите, функтор сохраняет структуру: что было связано во входной категории, будет связано и в выходной. Но этим структура не исчерпывается: необходимо также поддержать композицию морфизмов. Если h — композиция f и g :
то потребуем, чтобы его образ под действием F был композицией образов f и g:
Наконец, потребуем, чтобы все единичные(тождественные) морфизмы из C отображались в единичные морфизмы из D:
Здесь ida — это единичный морфизм объекта a, а idF a — единичный морфизм объекта F a.
Заметим, что все эти условия существенно ограничивают круг функций, подходящих в качестве морфизмов. Функторы должны сохранять структуру категории. Если представить себе категорию как набор объектов, переплетенных морфизмами, то функтор не имеет права оборвать ни одной нити этого кружева. Он может объединить несколько объектов, он может склеить морфизмы в один, но никогда не разрывает связей. Это ограничение аналогично понятию непрерывности из математического анализа. В этом смысле функторы «непрерывны» (хотя существует еще более ограничивающее определение непрерывности функторов). Как и любая функция, функтор может быть и склеивающими, и вкладывающими. Аспект вложения наиболее ярко проявляется, когда исходная категория намного меньше целевой. В предельном случае исходная категория представляет собой категорию 1, состоящую из одного объекта и одного (единичного) морфизма. Функтор из категории 1 в любую другую категорию просто выбирает определенный объект из этой категории. Имеет место полная аналогия с морфизмами из синглтона, выбирающими элементы из целевых множеств. Аспект склеивания, доведенный до абсурда, наблюдается в константном функторе Δc. Он отображает каждый объект исходной категории в определенный объект c целевой категории, а всякий морфизм — в единичный морфизм idc. Это как черная дыра, засасывающая все в точку сингулярности. Мы вернемся к рассмотрению этого функтора при обсуждении пределов и копределов.
Функторы в программировании
Вернёмся на землю, в мир программирования. Итак, у нас есть категория типов и функций. Рассмотрим функторы, отображающие эту категорию в себя — так называемые эндофункторы. Что представляет собой эндофунктор в категории типов? В первую очередь, он сопоставляет одним типам другие. Подобные отображения на самом деле нам знакомы, это типы, параметризованные другими типами. Рассмотрим несколько примеров.
Функтор Maybe
Определение Maybe есть отображение типа a в тип Maybe a:
Следуя сказанному выше, дадим определение fmap для Maybe :
Чтобы показать, что конструктор типов Maybe вместе с функцией fmap составляют функтор, осталось доказать, что fmap сохраняет единичные морфизмы и композицию. Эти утверждения называются «функториальными законами», но они просто удостоверяют сохранение структуры категории.
Метод эквивалентных преобразований
Докажем функториальные законы методом эквивалентных преобразований, который является типичной техникой доказательств в Haskell. Метод опирается на то, что функции в Haskell определены набором равенств: левая часть равна правой, обе они могут быть подставлены друг вместо друга (возможно, при подстановке потребуется переименовать переменные во избежание конфликтов). Можно как подставить тело функции вместо ее вызова (инлайнинг), так и вызов функции вместо ее тела (рефакторинг). Рассмотрим в качестве примера тождественную функцию:
Теперь покажем, что fmap сохраняет композицию:
Начнём со случая Nothing :
Теперь пришло время Just :
Стоит подчеркнуть, что для функций с побочными эффектами в стиле С++, метод эквивалентных преобразований не работает. Рассмотрим пример:
Метод эквивалентных преобразований позволил бы развернуть square и получить
Определенно, такая трансформация некорректна и меняет результат выражения. Несмотря на это, если определить square как макрос, препроцессор C++ воспользуется методом эквивалентных преобразований с катастрофическим результатом.
Снова Maybe
Это функция высшего порядка, принимающая функцию как аргумент и возвращающая функцию. А вот другой вариант, без каррирования:
Классы типов
Как же абстракция функтора реализована в Haskell? Используется механизм классов типов. Класс типов задаёт семейство типов, поддерживающих единый интерфейс. К примеру, класс объектов, сравнимых на равенство определяется так:
можно определить равенство точек:
Функторы в C++
Но как нам специализировать этот шаблон для разных функторов? К сожалению, частичная специализация шаблонных функций C++ запрещена. Нельзя написать:
Вместо этого приходится вернуться к перегрузке функций, в результате мы возвращаемся к первоначальному определению fmap (без каррирования):
Это определение работает, но для правильной перегрузки требуется второй аргумент. Более общее определение fmap просто игнорируется.
Функтор List
Для лучшего понимания значимости функторов в программировании стоит рассмотреть больше примеров. Любой тип, параметризуемый другим типом — кандидат на роль функтора. К примеру, обобщённые контейнеры параметризуются типом своих элементов, рассмотрим список, очень простой контейнер:
С её помощью мы можем, к примеру, возвести в квадрат ряд чисел:
Функтор Reader
Как и обычные функции, типовые функции нескольких аргументов можно применять частично. И когда мы даём стрелке один аргумент, она всё ещё ждёт другой. То есть,
Сработало! Минималист может ещё сократить запись, воспользовавшись префиксной формой:
теперь аргументы можно опустить, получая отождествление двух функций:
Комбинацию конструктора типов (->) r и такой реализации fmap называют «reader».
Функторы как контейнеры
Мы познакомились с примерами использования функторов в программировании для определения контейнеров общего назначения, или хотя бы объектов, содержащих какие-то значения того типа, которым функтор параметризован. Функтор reader кажется исключением, поскольку мы не думаем о функциях как о данных. Но как мы видели, к функциям применима мемоизация, когда вычисление сводится к поиску в таблице. Таблица это уже данные. С другой стороны, поскольку Haskell ленив, традиционный контейнер вроде списка может на деле реализовываться как функция. Посмотрите, например, на бесконечный список натуральных чисел, который можно описать так:
Поскольку наш функтор игнорирует свой типовый аргумент, будет естественным в реализации fmap игнорировать функциональный аргумент, — функцию не к чему применять:
В C++ это выглядит немного нагляднее (вот уж не думал, что скажу такое!), за счёт более чёткого различия между типовыми аргументами, которые работают на этапе компиляции, и значениями, работающими во время выполнения.
Несмотря на странный вид, функтор Const играет важную роль во многих построениях. В теории категорий это частный случай функтора Δc, упомянутого ранее — эндофункторной разновидности чёрной дыры. В будущем мы познакомимся с ним поближе.
Композиция функторов
Несложно убедиться, что для функторов между категориями композиция работает точно также, как для функций между множествами. Композиция двух функторов, при действии на объекты, есть просто композиция соответствующих отображений объектов, аналогичная ситуация с действием на морфизмы. После прыжка вдоль двух функторов, единичные морфизмы остаются единичными, также как и композиция морфизмов остаётся таковой для образов. Ничего особенного. В частности, легко сочетаются эндофункторы. Помните функцию maybeTail (ПП: из предыдущей главы)? Давайте её перепишем, применительно к стандартным спискам Haskell:
Но вспомните, что о fmap можно думать как о функции единственного аргумента:
и возвращает функцию типа
Затем первый fmap берёт получившуюся функцию и в свою очередь возвращает
Упражнения
Благодарности
Гершом Базерман любезно продолжает рецензирование текста. Автор благодарен ему за терпение и высказанные идеи.
leshabirukov: приблизительно первая половина главы переведена совместно мною и Bodigrim, который также участвовал в редактировании окончательной версии. Несогласованность нашего труда лежит на моей совести.
Контейнеры, итераторы, функторы, алгоритмы
Кувшинов Д.Р.
Контейнеры и итераторы
Пара итераторов задаёт диапазон range — определение последовательности значений, которую можно перечислить, передвигая итератор вперёд, начиная с первого элемента, на который указывает первый итератор в паре, и до тех пор, пока не будет встречен второй итератор в паре, обозначающий конец последовательности и указывающий на фиктивный элемент, как бы стоящий в последовательности сразу за последним элементом.
Последовательность может представлять собой контейнер, часть контейнера, массив, файл или генерироваться “на ходу”.
Пример диапазона с массивом:
В зависимости от внутреннего устройства контейнера не все характерные для указателей операции могут быть выполнены эффективно на его итераторах. Например, при доступе к связному списку обращение по числовому индексу может потребовать значительного числа операций. Итераторы могут не поддерживать неэффективные операции. Чтобы выделить характерные виды итераторов, в Стандарте C++ определены “категории итераторов”. Принадлежность итератора той или иной категории определяется набором поддерживаемых им операций.
Как правило, итератор нельзя использовать для модификации структуры контейнера (кроме специальных итераторов-адаптеров) без вызова функций самого контейнера.
Категории итераторов
Итератор ввода input iterator предназначен только для однократного чтения (ввода) последовательности значений.
Основная конструкция, поддерживаемая итератором ввода выглядит так:
Итератор вывода output iterator предназначен только для однократной записи (вывода) последовательности. В остальном аналогичен итератору ввода.
Основная конструкция, поддерживаемая итератором вывода, выглядит так:
Однонаправленный итератор forward iterator является расширением концепции “итератор ввода”, т.е. предоставляет возможности итератора ввода (и, возможно, но не гарантированно, итератора вывода). Кроме того, однонаправленный итератор допускает многократное чтение и запись линейной последовательности, по которой можно двигаться только в одну сторону (как по односвязному списку — “вперёд” с помощью операции ++ ).
Итератор произвольного доступа random access iterator является расширением концепции “двунаправленный итератор” и наиболее похож по своему поведению на обычный указатель на элемент массива (который является частным случаем итератора произвольного доступа).
Итератор произвольного доступа допускает адресацию по индексу (оператор [] ), сдвиг в обе стороны на некоторое количество позиций (добавление и вычитание целого числа), вычисление расстояния с помощью вычитания и сравнение на “меньше” и “больше” (согласованное с расстоянием, которое имеет знак).
Для упрощения работы с итераторами Стандартная библиотека предоставляет ряд средств (заголовочный файл ). Перечислим их.
Элементы Стандартной библиотеки для работы с итераторами
Класс характеристик iterator_traits
Классом характеристик traits class называют класс-шаблон, предоставляющий для своего параметра набор некоторых базовых определений, как правило типов и констант, которые некоторым образом характеризуют тип, подставленный в класс характеристик в качестве параметра шаблона.
Теговым классом tag class называют класс, не содержащий никаких членов (пустой), служащий только в качестве номинального значения (имя-константа). То, что это тип, а не значение, позволяет использовать его при выборе конкретного варианта перегруженной функции (см. ниже примеры теговых классов в контексте итераторов). Теговые классы могут состоять в отношениях наследования.
В случае iterator_traits это набор вложенных объявлений типов:
Если шаблон предполагает, что его параметр должен быть итератором, то обычно используются определённые сокращённые названия, указывающие минимальный набор операций, обеспечиваемых итератором, соответственно категориям, например:
Класс iterator
Вспомогательные функции distance, advance, next, prev
Функция distance(from, to) вычисляет расстояние между парой переданных ей итераторов from и to (количество применений оператора инкремента к первому итератору до достижения им второго, либо обычная разность для итераторов произвольного доступа).
Данная функция является хорошим примером использования категории итератора для выбора адекватного алгоритма (данная техника называется “статическая диспетчеризация вызова”). Её можно было бы определить следующим образом:
Функция advance(it, n) сдвигает итератор it (принимает по ссылке) на заданное число шагов n (сдвиг назад при отрицательных значениях n определен для двунаправленных итераторов).
Итераторы-адаптеры
Объекты back_inserter и istream_iterator можно использовать вместе, например, для организации считывания последовательности произвольной длины разделённых пробельными символами чисел. В примере чтение производится из потока cin в контейнер xs, который может иметь тип vector (здесь copy — стандартный алгоритм, о которых см. ниже):
Заметим, что запятая будет поставлена и после последнего выведенного числа, что может быть нежелательным. В этом случае последний элемент следует выводить отдельным вызовом.
Стандартные контейнеры
Ассоциативные контейнеры представлены восемью контейнерами, являющимися комбинациями следующих вариантов (в скобках даны части названий соответствующих стандартных классов): множество (* set ) или словарь (* map ), допускающие повторение элементов (* multi *) или не допускающие, упорядоченные или неупорядоченные ( unordered *).
семантически эквивалентна записи
Тип T здесь не обязан совпадать с типом элементов контейнера, а также может быть ссылочным типом или конструкцией на основе auto (чаще всего используются варианты auto& и auto&& ).
Линейные контейнеры (кроме array ) можно заполнить значениями из заданного диапазона вызовом функции assign (старое содержимое будет уничтожено) и изменить их размер функцией resize (при уменьшении размера лишние элементы удаляются с конца, при увеличении размера новые элементы добавляются в конец).
Линейные контейнеры
Имеется дополнительная фиктивная позиция “перед первым элементом”, возвращаемая функциями before_begin и cbefore_begin (вариант, возвращающий const_iterator ). Элементы можно вставлять в начало: вызов fl.push_front(item) эквивалентен
Функция pop_front удаляет первый элемент списка.
Особенностью контейнеров-списков в составе Стандартной библиотеки C++ также является поддержка более высокоуровневых операций, что проистекает из невозможности эффективного использования одних только итераторов для реализации этих операций:
В целом данные функции аналогичны соответствующим стандартным алгоритмам (см. их список в соответствующем разделе ниже), но выполняются как минимум быстрее, а как максимум — просто выполняются, потому что та же стандартная универсальная сортировка std::sort(from, to) требует итераторов произвольного доступа и поэтому вообще не применима к спискам.
Ассоциативные контейнеры
Все ассоциативные контейнеры поддерживают следующие операции:
Упорядоченные контейнеры построены на сбалансированном двоичном дереве и опираются на строгий порядок (операцию “меньше”, по умолчанию вычисляемую как результат оператора ). Два элемента считаются эквивалентными, если ни один из них не меньше другого.
Последний вариант insert возвращает пару (итератор, булевское значение), первый элемент которой указывает место вставленного или найденного значения, второй же позволяет узнать, было значение вставлено ( true ) или уже находилось во множестве на момент вставки ( false ).
Упорядоченный словарь с неуникальными ключами multimap не определяет operator[] и, по сути, напоминает multiset пар, поиск среди которых ведется только по первому полю (ключу). В качестве примера использования multimap рассмотрим задачу об обращении словаря, хранимого в текстовом файле. Для простоты положим, что словарь состоит из пар слов, упорядоченных по первому слову, слова могут повторяться.
Подумайте, как можно переделать пример с обращением словаря, чтобы не пришлось хранить одни и те же слова дважды (предполагая, что прочитанный словарь нам больше не требуется и его можно уничтожить в процессе обращения)?
Два элемента считаются эквивалентными, если их хэши равны и операция “равно” возвращает истину. Неупорядоченные контейнеры предоставляют доступ к элементам через однонаправленные итераторы.
При вставке, поиске и удалении элементов в среднем неупорядоченные контейнеры в среднем затрачивают постоянное время и могут оказаться заметно быстрее упорядоченных. Однако, в худшем случае время может достигать линейного. Поведение зависит от качества реализации хэш-функции, но полностью избежать таких “скачков” временных затрат может быть невозможно. Поэтому в интерактивных приложениях (например, играх) неупорядоченные контейнеры могут “вести” себя хуже упорядоченных — из-за периодического появления задержек.
Алгоритмы и функторы
Стандартная библиотека C++ содержит несколько десятков функций, называемых алгоритмами, оперирующих на наборах элементов, заданных диапазонами итераторов. Таким образом, итераторы выступают в качестве “клея”, соединяющего алгоритмы и контейнеры. Однако функционал алгоритмов был бы весьма ограничен, если бы не возможность задавать произвольные операции с помощью функторов.
Генератором называют функтор, который не принимает аргументов и возвращает некоторую (генерируемую) последовательность значений. В качестве примера можно привести генератор псевдослучайных чисел.
Предикатом называют функтор, возвращающий булевское значение и используемый, например, при фильтрации последовательностей.
Обычно предикаты являются одноместными (унарными), т. е. принимают один параметр.
Двуместные (бинарные) предикаты, принимающие два параметра и отвечающие некоторому отношению между ними, называют компараторами. Компараторы используются, например, в упорядоченных ассоциативных контейнерах и в стандартном алгоритме sort для определения отношения “меньше”.
Неупорядоченные ассоциативные контейнеры (хэш-таблицы) используют два функтора: компаратор, задающий отношение “равно”, и хэш, задающий способ вычисления хэш-функции для элементов контейнера, возвращающий целое число.
Список стандартных алгоритмов
copy_if(from, from_end, to, pred) — отличается от copy тем, что копирует только те элементы, для которых предикат pred возвращает истину (“фильтр”).
В случае, если диапазон, занимаемый копируемой или перемещаемой последовательностью, пересекается с диапазоном-местом назначения копирования или перемещения, то следует выбирать move или copy для сдвига “назад” и move_backward или copy_backward для сдвига “вперёд”.
Дело в том, что второй итератор в паре, возвращаемой minmax_element указывает не на первый максимальный элемент в диапазоне, а на последний максимальный элемент. Кроме того, minmax_element эффективнее, так как проходит по последовательности только один раз, а не два.
Пример сортировки выбором одновременно минимума и максимума:
remove_copy(begin, end, to, val) и remove_copy_if(begin, end, to, pred) — копируют исходные последовательности, пропуская заданные элементы (аналогично replace – replace_copy и replace_if – replace_copy_if ).
Следующий код считывает последовательность слов с потока ввода, сортирует слова, удаляет дубликаты и выводит полученную последовательность. Обратите внимание, что в нем не встречается ни одного ключевого слова C++.
Рекурсивная быстрая сортировка с выбором первого элемента диапазона в качестве опорного. Общий алгоритм выглядит следующим образом:
stable_sort(begin, end, comp) — отличается от sort тем, что гарантирует устойчивость (сохраняет исходный порядок эквивалентных элементов), однако работает несколько медленнее (обычно в 1.5–3 раза).
Рекурсивная нисходящая сортировка слияниями. Общий алгоритм выглядит следующим образом:
Средства конструирования функторов
Заголовочный файл содержит ряд классов-шаблонов, являющихся функторами-обёртками соответствующих операций: компараторы less (операция ‘ greater (операция ‘>’), less_equal (операция ‘ greater_equal (операция ‘>=’), equal_to (операция ‘==’), not_equal_to (операция ‘!=’), двуместные операции plus (операция ‘+’), minus (операция ‘-’), multiplies (операция ’*’) и т.д. Например, отсортировать vector v по убыванию можно так:
Все эти операции являются шаблонами, принимающими тип аргумента. Если его не указывать, он будет выводиться автоматически в месте применения (C++14).
Впрочем, многие подобные применения на деле проигрывают в краткости и понятности записи циклу for(:). Например, удвоение каждого элемента контейнера v1 “на месте”:
На деле возможности mem_fn и bind довольно ограничены. Наиболее сильным средством, появившимся в ISO C++11, являются замыкания — объекты анонимных функторов, создаваемые в месте использования с помощью лямбда-выражений. Структура лямбда-выражения слагается из следующих элементов:
Например, с помощью лямбда-выражений два из предыдущих примеров можно переписать так:
Замыкания можно сохранять в переменные. При этом ключевое слово auto решает проблему неизвестного типа. Данное свойство позволяет создавать локальные функции внутри другой функции с доступом к локальным переменным внешней функции, если это требуется.
Пример — динамический массив
Данный пример является дальнейшим развитием класса Darr с целью приблизить его интерфейс к интерфейсу стандартных контейнеров (ну и задействовать стандартные алгоритмы по возможности).
Версия 4
Добавим итераторы и другие типичные для стандартных контейнеров объявления вложенных типов. В нашем случае итераторы — просто указатели.
Определим операторы сравнения массивов на равенство и неравенство (поэлементное):
Версия 5
В версии 4 у нас не было конструктора, принимающего диапазон, заданный парой итераторов, и создающего массив из элементов, содержащихся в этом диапазоне. Такие конструкторы есть у большинства стандартных контейнеров, поэтому попробуем создать его и мы.
Чтобы разрешить код вида
следует определить конструктор, принимающий initializer_list :