fork download
copy 
  1. // Tested in Visual C++ 2013 and g++ 4.9.2.
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <type_traits>
  5. #include <utility>
  6. using namespace std;
  7. // Задача: удалить из произвольного контейнера элементы,
  8. // удовлетворяющие произвольному предикату эффективным способом.
  9.  
  10. /// Удаляет элементы, для которых pred возвращает истину,
  11. /// из связных списков (std::list, std::forward_list).
  12. template <class List, class Pred> inline
  13. void list_remove_if(List &l, Pred pred)
  14. {
  15.   // Списки из стандартной библиотеки сами "умеют" удалять элементы по предикату.
  16.   l.remove_if(pred);
  17. }
  18.  
  19. /// Удаляет элементы, для которых pred возвращает истину,
  20. /// из линейных контейнеров (std::vector, std::deque).
  21. template <class Vector, class Pred> inline
  22. void vector_remove_if(Vector &v, Pred pred)
  23. {
  24.   v.erase(remove_if(begin(v), end(v), pred), end(v));
  25. }
  26.  
  27. /// Удаляет элементы, для которых pred возвращает истину,
  28. /// из ассоциативных контейнеров (разные варианты set и map).
  29. /// В случае map предикат вычисляется для пары ключ-значение.
  30. template <class Assoc, class Pred>
  31. void assoc_remove_if(Assoc &a, Pred pred)
  32. {
  33.   for (auto it = begin(a), it_end = end(a); it != it_end; )
  34.     if (pred(*it))
  35.       it = a.erase(it);
  36.     else
  37.       ++it;
  38. }
  39.  
  40. // Автоматический выбор между представленными тремя вариантами можно организовать
  41. // через банальную лобовую перегрузку функции remove_if для std::list, std::vector, std::set и т.д.
  42. // Но мне не нравится этот вариант. Мы можем заставить компилятор автоматически
  43. // выбирать тот или иной вариант в зависимости от того, какие операции доступны для контейнера.
  44. // Вариант list_remove_if годится всегда, если контейнер предоставляет метод remove_if.
  45. // Вариант vector_remove_if годится для контейнеров с итератором произвольного доступа
  46. // и методом удаления диапазона erase(iterator, iterator).
  47. // Наконец, вариант assoc_remove_if годится для всех контейнеров с методом iterator erase(iterator).
  48. namespace impl
  49. {
  50.   /// Категория итератора для условного типа "не-итератора".
  51.   struct Not_an_iterator_tag {};
  52.   /// Специальный тип, означающий отсутствие типа, но позволяющий создавать объекты (в отличие от void).
  53.   struct No_type_tag {};
  54.   /// Условный тип "не-итератор", имитирует итератор с определёнными вложенными типами std::iterator_traits.
  55.   struct False_iterator
  56.     : iterator<Not_an_iterator_tag, No_type_tag> {};
  57.  
  58.   /// Метафункция. Извлекает тип итератора коллекции X (использует для этого [std::]begin).
  59.   /// Если begin(X) не определена, возвращает False_iterator.
  60.   template <class X>
  61.   class Collection_iterator
  62.   {
  63.     template <class Y>
  64.     static False_iterator check(unsigned long, Y&&);
  65.  
  66.     template <class Y>
  67.     static auto check(int, Y &&y) -> decltype(begin(y));
  68.  
  69.   public:
  70.     using type = decltype(check(1, declval<X>()));
  71.   };
  72.  
  73.   /// Проверяет, является ли X "коллекцией".
  74.   /// Коллекция -- объект, для которого свободные функции begin и end возвращают итераторы
  75.   /// с категорией, приводимой к forward_iterator_tag.
  76.   /// Проверяется только [std::]begin.
  77.   /// В качестве коллекции может выступать любой STL контейнер, объект std::basic_string или статический массив.
  78.   template <class X>
  79.   struct Is_collection
  80.     : is_convertible<typename
  81.         iterator_traits<typename Collection_iterator<X>::type>::iterator_category,
  82.         forward_iterator_tag> {};
  83.  
  84.  
  85.   /////////////////////////////////////////////////////////////////////////////
  86.   /// Проверка, возможен ли вызов assoc_remove_if для объекта Cont.
  87.   template <class Cont>
  88.   class Assoc_remove_if_possible
  89.   {
  90.     template <class C>
  91.     static false_type check(unsigned long, C&&);
  92.  
  93.     template <class C>
  94.     static auto check(int, C &&c) ->
  95.       is_convertible<decltype(c.erase(begin(c))), decltype(begin(c))>;
  96.  
  97.     static const bool
  98.       erase_defined = decltype(check(1, declval<Cont>()))::value,
  99.       is_collection = Is_collection<Cont>::value;
  100.  
  101.   public:
  102.     using type = integral_constant<bool, erase_defined && is_collection>;
  103.     static const bool value = type::value;
  104.   };
  105.  
  106.   /// Проверка, возможен ли вызов vector_remove_if для объекта Cont.
  107.   template <class Cont>
  108.   class Vector_remove_if_possible
  109.   {
  110.     template <class C>
  111.     static false_type check(unsigned long, C&&);
  112.  
  113.     template <class C>
  114.     static auto check(int, C &&c) -> integral_constant<bool,
  115.          is_convertible<typename
  116.             iterator_traits<typename Collection_iterator<C>::type>::iterator_category,
  117.             random_access_iterator_tag>::value
  118.       && is_convertible<decltype(c.erase(begin(c), end(c))), decltype(begin(c))>::value>;
  119.  
  120.   public:
  121.     using type = decltype(check(1, declval<Cont>()));
  122.     static const bool value = type::value;
  123.   };
  124.  
  125.   /// Проверка, возможен ли вызов list_remove_if.
  126.   template <class Cont>
  127.   class List_remove_if_possible
  128.   {
  129.     template <class C>
  130.     static false_type check(unsigned long, C&&);
  131.  
  132.     // Универсальный предикат.
  133.     struct Unipred { template <class T> bool operator()(const T&) { return false; } };
  134.  
  135.     template <class C>
  136.     static auto check(int, C &&c) ->
  137.       decltype((void)c.remove_if(Unipred{}), true_type{});
  138.  
  139.   public:
  140.     using type = decltype(check(1, declval<Cont>()));
  141.     static const bool value = type::value;
  142.   };
  143.  
  144.  
  145.   /////////////////////////////////////////////////////////////////////////////
  146.   // Теги для статического выбора соответствующего варианта remove_if.
  147.   struct Assoc_remove_if_tag {};
  148.   struct Vector_remove_if_tag {};
  149.   struct List_remove_if_tag {};
  150.  
  151.   /// Выбор подходящего тега remove_if для контейнера.
  152.   template <class Cont>
  153.   class Remove_if_tag
  154.   {
  155.     static const bool
  156.       assoc_possible  = Assoc_remove_if_possible<Cont>::value,
  157.       vector_possible = Vector_remove_if_possible<Cont>::value,
  158.       list_possible   = List_remove_if_possible<Cont>::value;
  159.  
  160.     static_assert(assoc_possible || vector_possible || list_possible,
  161.         "remove_if can not be called for this type");
  162.  
  163.   public:
  164.     using type = conditional_t<list_possible, List_remove_if_tag,
  165.                  conditional_t<vector_possible, Vector_remove_if_tag,
  166.                  conditional_t<assoc_possible, Assoc_remove_if_tag,
  167.                                void>>>;
  168.   };
  169.  
  170.   // Перенаправление вызова remove_if на варианты для различных типов контейнеров.
  171.   template <class Cont, class Pred> inline
  172.   void remove_if(Cont &c, Pred pred, Assoc_remove_if_tag) { assoc_remove_if(c, pred); }
  173.  
  174.   template <class Cont, class Pred> inline
  175.   void remove_if(Cont &c, Pred pred, Vector_remove_if_tag) { vector_remove_if(c, pred); }
  176.  
  177.   template <class Cont, class Pred> inline
  178.   void remove_if(Cont &c, Pred pred, List_remove_if_tag) { list_remove_if(c, pred); }
  179. }
  180.  
  181. /// Вызов разрешается статически в подходящий вариант в зависимости от типа контейнера.
  182. template <class Cont, class Pred> inline
  183. void remove_if(Cont &container, Pred pred)
  184. {
  185.   impl::remove_if(container, pred, typename impl::Remove_if_tag<Cont>::type{});
  186. }
  187.  
  188.  
  189. // Тестовый код.
  190. #include <iostream>
  191. #include <vector>
  192. #include <set>
  193. #include <list>
  194. #include <string>
  195.  
  196. // Свободная функция-шаблон, переадресующая вызов функции-члену empty.
  197. template <class T> inline
  198. bool empty(const T &t)
  199. {
  200.   return t.empty();
  201. }
  202.  
  203. // Удобный в применении класс-предикат (не надо явно указывать тип).
  204. // При необходимости переопределить его поведение достаточно определить
  205. // свою версию функции empty, определённой выше.
  206. struct Empty
  207. {
  208.   template <class T>
  209.   bool operator()(const T &t) const
  210.   {
  211.     return empty(t);
  212.   }
  213. };
  214.  
  215. template <class Cont> inline
  216. void remove_empty(Cont &container)
  217. {
  218.   remove_if(container, Empty{});
  219. }
  220.  
  221. // Вывести std::pair произвольных значений.
  222. template <class A, class B> inline
  223. ostream& operator<<(ostream &os, const pair<A, B> &p)
  224. {
  225.   return os << p.first << " : " << p.second;
  226. }
  227.  
  228. // Вывести произвольный контейнер, все элементы в {} и через запятую.
  229. template <class Container>
  230. void print(ostream &os, const Container &cont)
  231. {
  232.   os << " { ";
  233.   auto it = begin(cont);
  234.   const auto it_end = end(cont);
  235.   if (it != it_end)
  236.   {
  237.     os << *it;
  238.     while (++it != it_end)
  239.       os << ", " << *it;
  240.   }
  241.   os << " }\n";
  242. }
  243.  
  244. // Чтобы не повторять cout.
  245. template <class Container> inline
  246. void print(const Container &cont)
  247. {
  248.   print(cout, cont);
  249. }
  250.  
  251.  
  252. int main()
  253. {
  254.   string master_copy[] = { "alpha", "", "beta", "", "", "gamma", "" };
  255.   cout << "Master copy: ";
  256.   print(master_copy);
  257.   //remove_empty(master_copy); // ошибка компиляции: remove_if can not be called for this type
  258.  
  259.   cout << "\nVector: ";
  260.   vector<string> v(begin(master_copy), end(master_copy));
  261.   print(v);
  262.   remove_empty(v);
  263.   cout << "remove_empty: ";
  264.   print(v);
  265.  
  266.   cout << "\nMultiset: ";
  267.   multiset<string> s(begin(master_copy), end(master_copy));
  268.   print(s);
  269.   remove_empty(s);
  270.   cout << "remove_empty: ";
  271.   print(s);
  272.  
  273.   cout << "\nList: ";
  274.   list<string> l(begin(master_copy), end(master_copy));
  275.   print(l);
  276.   remove_empty(l);
  277.   cout << "remove_empty: ";
  278.   print(l);
  279.  
  280.   cin.ignore();
  281.   return 0;
  282. }
  283.  
Success #stdin #stdout 0s 3240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Master copy:  { alpha, , beta, , , gamma,  }

Vector:  { alpha, , beta, , , gamma,  }
remove_empty:  { alpha, beta, gamma }

Multiset:  { , , , , alpha, beta, gamma }
remove_empty:  { alpha, beta, gamma }

List:  { alpha, , beta, , , gamma,  }
remove_empty:  { alpha, beta, gamma }
https://ideone.com/2Xz1CC
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!