CODEWITHSUNDEEP
c++c++14template-meta-programming
Sebastian Stern
Sebastian Stern

Reputation: 642

Generic `erase_if` method for container types

I'm trying to write a generic erase_if method that can be used on any container type to remove elements given a predicate. It should either use the erase-remove-idiom if the container allows it, or loop through the container and call the erase method. I also just want to provide the container itself, not the begin and end iterator separatly. That shall be handled by the method.

However I can't get the meta-template to work to distinguish between the two cases through SFINAE. I'm trying to check whether the method std::remove_if (or std::remove) would be well defined for a given type, but the value is either true for both vector and map (in which case the code won't compile) or false for both of them. I'm quite new to template meta-programming, so is there something I'm missing? Or maybe there's another, better solution?

Below is my example code:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <type_traits>
#include <vector>


namespace my_std
{
    using std::begin;
    using std::end;

    namespace detail
    {
        template <typename T>
        // this is false for both vector and map
        auto is_remove_compatible(int) -> decltype(std::remove_if(begin(std::declval<T&>()), end(std::declval<T&>()),
                                                                  [](auto&&) { return false; }),
                                                   std::true_type{});

        // this is true for both vector and map
        // auto is_remove_compatible(int)
        //  -> decltype(std::remove(begin(std::declval<T&>()), end(std::declval<T&>()), std::declval<T::value_type&>()),
        //              std::true_type{});

        template <typename T>
        auto is_remove_compatible(...) -> std::false_type;
    }

    template <typename T>
    using is_remove_compatible = decltype(detail::is_remove_compatible<T>(0));

    template <typename T>
    constexpr bool is_remove_compatible_v = is_remove_compatible<T>::value;

    template <typename Cont, typename Pred>
    std::enable_if_t<is_remove_compatible_v<Cont>> erase_if(Cont& container, Pred pred)
    {
        std::cout << "Using erase-remove\n";
        container.erase(std::remove_if(begin(container), end(container), pred), end(container));
    }

    template <typename Cont, typename Pred>
    std::enable_if_t<!is_remove_compatible_v<Cont>> erase_if(Cont& container, Pred pred)
    {
        std::cout << "Using loop\n";
        for (auto it = begin(container); it != end(container);)
        {
            if (pred(*it))
                it = container.erase(it);
            else
                ++it;
        }
    }
}

template <typename T>
std::ostream& operator<<(std::ostream& out, std::vector<T> const& v)
{
    if (!v.empty())
    {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}

template <typename K, typename V>
std::ostream& operator<<(std::ostream& out, std::map<K, V> const& v)
{
    out << '[';
    for (auto const& p : v)
        out << '{' << p.first << ", " << p.second << "}, ";
    out << "\b\b]";
    return out;
}

int main(int argc, int argv[])
{
    auto vp = my_std::is_remove_compatible_v<std::vector<int>>;
    auto mp = my_std::is_remove_compatible_v<std::map<int, int>>;

    std::cout << vp << ' ' << mp << '\n';

    std::vector<int> v = {1, 2, 3, 4, 5};
    auto v2 = v;
    my_std::erase_if(v2, [](auto&& x) { return x % 2 == 0; });

    std::map<int, int> m{{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}};
    auto m2 = m;
    my_std::erase_if(m2, [](auto&& x) { return x.first % 2 == 0; });

    std::cout << v << " || " << v2 << '\n';
    std::cout << m << " || " << m2 << '\n';

    std::cin.ignore();
}

Upvotes: 1

Views: 505

Answers (1)

Barry
Barry

Reputation: 302852

This idea is wrong for two reasons:

auto is_remove_compatible(int) -> decltype(std::remove_if(begin(std::declval<T&>()), end(std::declval<T&>()),
                                                          [](auto&&) { return false; }),
                                           std::true_type{});

First, you can't have a lambda in an unevaluated context, so the code is ill-formed. Second, even if it wasn't ill-formed (which is easy to fix), remove_if() isn't SFINAE-friendly on anything. If you pass in something that isn't a predicate to remove_if, or a non-modifiable iterator, that's not required by the standard to be anything but a hard error.

The way I would do it right now is via the chooser idiom. Basically, have conditional sfinae based on a rank ordering:

template <std::size_t I> struct chooser : chooser<I-1> { };
template <> struct chooser<0> { };

template <class Cont, class Predicate>
void erase_if(Cont& container, Predicate&& predicate) {
    return erase_if_impl(container, std::forward<Predicate>(predicate), chooser<10>{});
}

And then we just have our various erase_if_impl conditions, in order:

// for std::list/std::forward_list
template <class Cont, class Predicate>
auto erase_if_impl(Cont& c, Predicate&& predicate, chooser<3> )
    -> decltype(void(c.remove_if(std::forward<Predicate>(predicate))))
{
    c.remove_if(std::forward<Predicate>(predicate));
}

// for the associative containers (set, map, ... )
template <class Cont, class Predicate>
auto erase_if_impl(Cont& c, Predicate&& predicate, chooser<2> )
    -> decltype(void(c.find(std::declval<typename Cont::key_type const&>())))
{
    using std::begin; using std::end;
    for (auto it = begin(c); it != end(c); )
    {
        if (predicate(*it)) {
            it = c.erase(it);
        } else {
            ++it;
        }
    }
}

// for everything else, there's MasterCard
template <class Cont, class Predicate>
void erase_if_impl(Cont& c, Predicate&& predicate, chooser<1> )
{
    using std::begin; using std::end;
    c.erase(std::remove_if(begin(c), end(c), std::forward<Predicate>(predicate)), end(c));
}

Upvotes: 7

Related Questions