How to emulate remove_unless

Question

I have code to remove all elements from a std::vector<int> that are less than some int limit. I've written some functions that partially apply lambdas:

auto less_than_limit = [](int limit) {
  return [=](int elem) {
    return limit > elem;
  };
};

auto less_than_three = less_than_limit(3);

When I test it with std::vector<int> v{1,2,3,4,5};, I get the expected results:

for(auto e: v) {
  std::cout << less_than_three(e) << " ";
}
// 1 1 0 0 0

I can easily remove all the elements less than three:

auto remove_less_than_three = std::remove_if(std::begin(v), std::end(v), less_than_three);

v.erase(remove_less_than_three, v.end());

for(auto e: v) {
  std::cout << e << " ";
}
// 3 4 5

How would I remove elements greater than or equal to 3 using less_than_three?

I tried wrapping less_than_three in std::not1, but got errors:

/usr/local/Cellar/gcc/5.3.0/include/c++/5.3.0/bits/stl_function.h:742:11: error: no type named 'argument_type' in 'struct main()::<lambda(int)>::<lambda(int)>'
     class unary_negate
           ^
/usr/local/Cellar/gcc/5.3.0/include/c++/5.3.0/bits/stl_function.h:755:7: error: no type named 'argument_type' in 'struct main()::<lambda(int)>::<lambda(int)>'
       operator()(const typename _Predicate::argument_type& __x) const

/usr/local/Cellar/gcc/5.3.0/include/c++/5.3.0/bits/predefined_ops.h:234:30: error: no match for call to '(std::unary_negate<main()::<lambda(int)>::<lambda(int)> >) (int&)'
  { return bool(_M_pred(*__it)); }
                              ^

I then tried std::not1(std::ref(less_than_three)), but got these errors:

/usr/local/Cellar/gcc/5.3.0/include/c++/5.3.0/bits/stl_function.h:742:11: error: no type named 'argument_type' in 'class std::reference_wrapper<main()::<lambda(int)>::<lambda(int)> >'
     class unary_negate
           ^
/usr/local/Cellar/gcc/5.3.0/include/c++/5.3.0/bits/stl_function.h:755:7: error: no type named 'argument_type' in 'class std::reference_wrapper<main()::<lambda(int)>::<lambda(int)> >'
       operator()(const typename _Predicate::argument_type& __x) const
       ^
/usr/local/Cellar/gcc/5.3.0/include/c++/5.3.0/bits/predefined_ops.h:234:30: error: no match for call to '(std::unary_negate<std::reference_wrapper<main()::<lambda(int)>::<lambda(int)> > >) (int&)'
  { return bool(_M_pred(*__it)); }
                              ^

How can I negate the function in std::remove_if without changing the logic of my lambdas? In other words, how can I emulate remove_unless?

Naaman

I presume you've ruled out the obvious choice of calling your lambda from another lambda for some reason? – Knob

@BenjaminLindley Yes, I realize this is the clear and reasonable choice. This is for purely for educational purposes. – Naaman

This must have to do something with the lambda type. You should make the type of less_then_three explicit. std::function<bool(int)> less_than_three = less_than_limit(3); – Disclosure

@Gene: It has to do with the fact that his lambda type does not have an internally defined typedef called argument_type, which is something that not1 requires. – Knob

The legacy adaptors are terrible. You want something like std::experimental::not_fn, which isn't that hard to implement (especially if you don't care about member pointers). – Oleary

An alternative solution is to write your own remove_if_not function. – Kulturkampf

@ChristianHackl That's not an alternative - that's basically what I'm asking. ;) – Naaman

@erip: My thinking was more along the lines of taking an existing implementation of remove_if and modifying it, e.g. the one at en.cppreference.com/w/cpp/algorithm/remove with p(*i) instead of !p(*i) and find_if replaced by find_if_not. You'd no longer need a negative predicate and client code would presumably become a bit more readable. – Kulturkampf

Answer 1

std::not1 presumes your function object will derive from std::unary_function, or at least provide the same interface, so it'll have typedefs for result_type and argument_type.

Since a lambda won't define those, you won't be able to use not1 on them.

The obvious choice would be to create something similar to not1 yourself, but using more modern techniques to detect/pass through the argument/result type from whatever it modifies.

If you really want to use not1, then the most sensible approach would be to do the comparison with std::less and std::bind to specify the value to which you're going to compare (i.e., it's basically a C++03 thing, so if you're going to use it, you write everything in the style of C++03).

Protostele

I don't necessarily want to use not1. It just seemed like the best option to negative the result of a function (but evidently not a lambda). – Naaman

Answer 2

not1 is somewhat obsolete (and requires that the functor provides certain member typedefs, which a lambda clearly doesn't).

You'll have to write a negator yourself:

auto negate = [] (auto&& f) {return [f=std::forward<decltype(f)>(f)] 
            (auto&&... args) {return !f(std::forward<decltype(args)>(args)...);};};

Demo.

Gabar

Answer 3

You can also define the return type of the lambda with std::function.

auto remove_gte_three = std::remove_if(std::begin(v), std::end(v), std::not1(std::function<int(int)>(less_than_three)));

Picrite

Using function here is needlessly employing type erasure. – Gabar

@Gabar Please elaborate? This is the simplest proposed solution by far. – Floridafloridia

@BrianRodriguez Simple != Optimal. function must use type erasure, because there is no information about the type of the entity stored outside the constructor template. – Gabar

@Gabar lambdas have no useful information in their type regardless. What do you lose by erasing its type? – Floridafloridia

@Gabar So maybe this doesn't have the optimal run-time performance, but there's a fair chance that the extra time needed by the computer, even if you sum it all together, is still less than the extra time it takes some programmers to fully understand your version. :) (I would've gone with something similar to your version, myself.) – Displease

Answer 4

Old way with not1() negator (C++11):

// You apply the not1() negator adapter 
// to the result of  less_than_three() like this:
std::function<bool(int)> f = less_than_three;
auto it = remove_if(begin(v), end(v), not1(f));

New way with lambda (C++14):

// Or with lambda you can negate an unary predicate.
// Thanks to Stephan T. Lavavej
template <typename T, typename Predicate>
void keep_if(std::vector<T>& v, Predicate pred)
{
    auto notpred = [&pred](const T& t) { return !pred(t); };
    v.erase(remove_if(v.begin(), v.end(), notpred), v.end());
}

Usage:

keep_if(v, less_than_three);

Or more general solution (C++14):

template <ForwardIterator I, Predicate P>
I remove_if_not(I first, I last, P pred)
{
    return std::remove_if(first, last,
            [&](const ValueType(I)& x){ return !pred(x); });
}

Usage:

auto p = remove_if_not(begin(v), end(v), less_than_three);
v.erase(p, v.end());
// Result: 1 2

Obbligato