Граница Парето в 2D: STL-версия
Почти пять лет назад я описал алгоритм вычисления границы Парето множества точек на плоскости.
С тех пор я использовал данную задачу как задачу по программированию на первом курсе (на алгоритмы STL). Всё дело в том, что этот алгоритм очень просто записывается с помощью STL. Требуется применить два алгоритма (sort и unique) и адаптер компаратора (not_fn или самописный, например, переставляющий аргументы местами). Бывают простенькие задачи, к которым невозможно адекватно применить STL без написания своих компонент, а бывает и наоборот. Итак, код.
#include <algorithm> #include <functional> template < class RanIt, class Comp1, class Comp2 > RanIt remove_dominated ( RanIt from, RanIt to, Comp1 compare1, Comp2 compare2 ) { std::sort(from, to, std::not_fn(compare1)); return std::unique(from, to, std::not_fn(compare2)); } //////////////////////////// #include <string> #include <vector> #include <iostream> using namespace std; bool test_remove_dominated() { vector<string> input { "look", "after", "the", "raven", "star" }; input.erase( remove_dominated( input.begin(), input.end(), std::less<>{}, [](auto & a, auto & b) { return a.size() < b.size(); }), input.end() ); sort(input.begin(), input.end()); return input == vector<string> { "raven", "star", "the" }; } int main() { cout << test_remove_dominated() << '\n'; return 0; }
В примере два критерия сравнения строк: лексикографический и по длине. Так «raven» доминирует «look» (и лексикографически, и по длине), но не «star».
Обобщённая функция удаления элементов из контейнера
Введение
Стандартная библиотека C++ не предлагает общего интерфейса для удаления элементов из произвольного контейнера. Тем не менее, средства метапрограммирования и принцип SFINAE позволяют реализовать такой интерфейс (например, в виде функции-шаблона) поверх стандартных компонент и выполнять выбор подходящего для переданного контейнера метода на этапе компиляции. Наша функция будет удалять элементы контейнера, удовлетворяющие произвольному предикату, переданному в виде функтора. Обычно это линейная по числу элементов контейнера операция, в случае же ассоциативных контейнеров, реализованных в виде деревьев, она может быть линеарифмической.
Далее предполагаем следующую «шапку».
#include <algorithm> #include <iterator> #include <type_traits> #include <utility> using namespace std;
Реализации свободной функции для разных видов контейнеров
Контейнеры-списки реализуют желаемую функцию в виде функции-члена, которой и следует переадресовать вызов.
/// Удаляет элементы, для которых pred возвращает истину, /// из связных списков (std::list, std::forward_list). template <class List, class Pred> inline void list_remove_if(List &l, Pred pred) { l.remove_if(pred); }
Прочие линейные контейнеры с изменяемым размером (вектор, дек) предполагают перемещение элементов в начало (затирая удаляемые) с сохранением относительного порядка и «отрезание хвоста» контейнера.
/// Удаляет элементы, для которых pred возвращает истину, /// из линейных контейнеров (std::vector, std::deque). template <class Vector, class Pred> inline void vector_remove_if(Vector &v, Pred pred) { v.erase(remove_if(begin(v), end(v), pred), end(v)); }
Ассоциативные контейнеры требуют прямого обхода с удалением конкретных элементов.
/// Удаляет элементы, для которых pred возвращает истину, /// из ассоциативных контейнеров (разные варианты set и map). /// В случае map предикат вычисляется для пары ключ-значение. template <class Assoc, class Pred> void assoc_remove_if(Assoc &a, Pred pred) { for (auto it = begin(a), it_end = end(a); it != it_end; ) if (pred(*it)) it = a.erase(it); else ++it; }
Автоматический выбор правильного варианта по виду контейнера
Автоматический выбор между представленными тремя вариантами можно организовать через банальную лобовую перегрузку функции remove_if для std::list, std::vector, std::set и т.д. Но мне не нравится этот вариант, так как он не способен автоматически «принять» нестандартные контейнеры, удовлетворяющие интерфейсу того или иного STL-контейнера — для каждого вида контейнера надо будет написать явную перегрузку.
Вместо этого мы можем заставить компилятор автоматически выбирать тот или иной вариант в зависимости от того, какие операции доступны для контейнера (сделать это позволяет SFINAE).
Вариант list_remove_if годится тогда, когда контейнер предоставляет метод remove_if (сам контейнер лучше знает как эффективно удалять из него элементы). Вариант vector_remove_if годится для контейнеров с методом удаления диапазона erase(iterator, iterator) и итератором произвольного доступа (формально достаточно итератора однонаправленного последовательного доступа («forward»), но тогда будут подходить и ассоциативные контейнеры). Наконец, вариант assoc_remove_if годится для всех контейнеров с методом iterator erase(iterator).
Далее приводится код метафункций, проверяющих наличие тех или иных операций и таким образом определяющих вид контейнера.
namespace impl { /// Категория итератора для условного типа "не-итератора". struct Not_an_iterator_tag {}; /// Специальный тип, означающий отсутствие типа, /// но позволяющий создавать объекты (в отличие от void). struct No_type_tag {}; /// Условный тип "не-итератор", имитирует итератор с /// определёнными вложенными типами std::iterator_traits. struct False_iterator : iterator<Not_an_iterator_tag, No_type_tag> {}; /// Метафункция. Извлекает тип итератора коллекции X /// (использует для этого [std::]begin). /// Если begin(X) не определена, возвращает False_iterator. template <class X> class Collection_iterator { template <class Y> static False_iterator check(unsigned long, Y&&); template <class Y> static auto check(int, Y &&y) -> decltype(begin(y)); public: using type = decltype(check(1, declval<X>())); }; /// Проверяет, является ли X "коллекцией". /// Коллекция -- объект, для которого свободные функции /// begin и end возвращают итераторы с категорией, /// приводимой к forward_iterator_tag. /// Проверяется только [std::]begin. /// В качестве коллекции может выступать любой STL контейнер, /// объект std::basic_string или статический массив. template <class X> struct Is_collection : is_convertible<typename iterator_traits<typename Collection_iterator<X>::type>::iterator_category, forward_iterator_tag> {}; ///////////////////////////////////////////////////////////////////////////// /// Проверка, возможен ли вызов assoc_remove_if для объекта Cont. template <class Cont> class Assoc_remove_if_possible { template <class C> static false_type check(unsigned long, C&&); template <class C> static auto check(int, C &&c) -> is_convertible< decltype(c.erase(begin(c))), decltype(begin(c))>; static const bool erase_defined = decltype(check(1, declval<Cont>()))::value, is_collection = Is_collection<Cont>::value; public: using type = integral_constant<bool, erase_defined && is_collection>; static const bool value = type::value; }; /// Проверка, возможен ли вызов vector_remove_if для объекта Cont. template <class Cont> class Vector_remove_if_possible { template <class C> static false_type check(unsigned long, C&&); template <class C> static auto check(int, C &&c) -> integral_constant<bool, is_convertible<typename iterator_traits<typename Collection_iterator<C>::type>::iterator_category, random_access_iterator_tag>::value && is_convertible< decltype(c.erase(begin(c), end(c))), decltype(begin(c))>::value>; public: using type = decltype(check(1, declval<Cont>())); static const bool value = type::value; }; /// Проверка, возможен ли вызов list_remove_if. template <class Cont> class List_remove_if_possible { template <class C> static false_type check(unsigned long, C&&); // Универсальный предикат. struct Unipred { template <class T> bool operator()(const T&) { return false; } }; template <class C> static auto check(int, C &&c) -> decltype((void)c.remove_if(Unipred{}), true_type{}); public: using type = decltype(check(1, declval<Cont>())); static const bool value = type::value; }; ///////////////////////////////////////////////////////////////////////////// // Статическая диспетчеризация вызова // Теги для статического выбора соответствующего варианта remove_if. struct Assoc_remove_if_tag {}; struct Vector_remove_if_tag {}; struct List_remove_if_tag {}; /// Выбор подходящего тега remove_if для контейнера. template <class Cont> class Remove_if_tag { static const bool assoc_possible = Assoc_remove_if_possible<Cont>::value, vector_possible = Vector_remove_if_possible<Cont>::value, list_possible = List_remove_if_possible<Cont>::value; static_assert(assoc_possible || vector_possible || list_possible, "remove_if can not be called for this type"); public: using type = conditional_t<list_possible, List_remove_if_tag, conditional_t<vector_possible, Vector_remove_if_tag, conditional_t<assoc_possible, Assoc_remove_if_tag, void>>>; }; // Перенаправление вызова remove_if на варианты для различных типов контейнеров. template <class Cont, class Pred> inline void remove_if(Cont &c, Pred pred, Assoc_remove_if_tag) { assoc_remove_if(c, pred); } template <class Cont, class Pred> inline void remove_if(Cont &c, Pred pred, Vector_remove_if_tag) { vector_remove_if(c, pred); } template <class Cont, class Pred> inline void remove_if(Cont &c, Pred pred, List_remove_if_tag) { list_remove_if(c, pred); } } /// Вызов разрешается статически в подходящий вариант в зависимости от типа контейнера. template <class Cont, class Pred> inline void remove_if(Cont &container, Pred pred) { impl::remove_if(container, pred, typename impl::Remove_if_tag<Cont>::type{}); }
Итак, remove_if(контейнер, предикат) выбирает один из трёх способов удаления элементов, удовлетворяющих предикату, в зависимости от операций, предоставляемых контейнером. Приведённый код целиком и небольшой проверочный код: ideone, Bitbucket.
UPD. Увидел, что нечто подобное предлагалось для добавления в стандартную библиотеку. Пока оно представлено в виде расширения в пространстве имён experimental.