// Tested in Visual C++ 2013 and g++ 4.9.2.
#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 и т.д.
// Но мне не нравится этот вариант. Мы можем заставить компилятор автоматически
// выбирать тот или иной вариант в зависимости от того, какие операции доступны для контейнера.
// Вариант list_remove_if годится всегда, если контейнер предоставляет метод remove_if.
// Вариант vector_remove_if годится для контейнеров с итератором произвольного доступа
// и методом удаления диапазона erase(iterator, iterator).
// Наконец, вариант 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{});
}
// Тестовый код.
#include <iostream>
#include <vector>
#include <set>
#include <list>
#include <string>
// Свободная функция-шаблон, переадресующая вызов функции-члену empty.
template <class T> inline
bool empty(const T &t)
{
return t.empty();
}
// Удобный в применении класс-предикат (не надо явно указывать тип).
// При необходимости переопределить его поведение достаточно определить
// свою версию функции empty, определённой выше.
struct Empty
{
template <class T>
bool operator()(const T &t) const
{
return empty(t);
}
};
template <class Cont> inline
void remove_empty(Cont &container)
{
remove_if(container, Empty{});
}
// Вывести std::pair произвольных значений.
template <class A, class B> inline
ostream& operator<<(ostream &os, const pair<A, B> &p)
{
return os << p.first << " : " << p.second;
}
// Вывести произвольный контейнер, все элементы в {} и через запятую.
template <class Container>
void print(ostream &os, const Container &cont)
{
os << " { ";
auto it = begin(cont);
const auto it_end = end(cont);
if (it != it_end)
{
os << *it;
while (++it != it_end)
os << ", " << *it;
}
os << " }\n";
}
// Чтобы не повторять cout.
template <class Container> inline
void print(const Container &cont)
{
print(cout, cont);
}
int main()
{
string master_copy[] = { "alpha", "", "beta", "", "", "gamma", "" };
cout << "Master copy: ";
print(master_copy);
//remove_empty(master_copy); // ошибка компиляции: remove_if can not be called for this type
cout << "\nVector: ";
vector<string> v(begin(master_copy), end(master_copy));
print(v);
remove_empty(v);
cout << "remove_empty: ";
print(v);
cout << "\nMultiset: ";
multiset<string> s(begin(master_copy), end(master_copy));
print(s);
remove_empty(s);
cout << "remove_empty: ";
print(s);
cout << "\nList: ";
list<string> l(begin(master_copy), end(master_copy));
print(l);
remove_empty(l);
cout << "remove_empty: ";
print(l);
cin.ignore();
return 0;
}