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?

I presume you've ruled out the obvious choice of calling your lambda from another lambda for some reason? — Benjamin Lindley, Jan 12 '16 at 17:59
@BenjaminLindley Yes, I realize this is the clear and reasonable choice. This is for purely for educational purposes. — erip, Jan 12 '16 at 18:00
This must have to do something with the lambda type. You should make the type of `less_then_three` explicit. `std::function less_than_three = less_than_limit(3);` — Gene, Jan 12 '16 at 18:01
@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. — Benjamin Lindley, Jan 12 '16 at 18:03
The legacy adaptors are terrible. You want something like [`std::experimental::not_fn`](http://en.cppreference.com/w/cpp/experimental/not_fn), which isn't that hard to implement (especially if you don't care about member pointers). — T.C., Jan 12 '16 at 18:04
An alternative solution is to write your own `remove_if_not` function. — Christian Hackl, Jan 12 '16 at 18:07
@ChristianHackl That's not an alternative - that's basically what I'm asking. ;) — erip, Jan 12 '16 at 18:16
@erip: My thinking was more along the lines of taking an existing implementation of `remove_if` and modifying it, e.g. the one at http://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. — Christian Hackl, Jan 12 '16 at 18:53

score 11 · Answer 1 · answered Jan 12 '16 at 18:04

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.

score 7 · Accepted Answer · answered Jan 12 '16 at 18:04

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).

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). — erip, Jan 12 '16 at 18:09

score 4 · Answer 3 · edited Jan 12 '16 at 18:09

4

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)));

edited Jan 12 '16 at 18:09

erip

16,374
11
66
121

answered Jan 12 '16 at 18:07

George Houpis

1,729
1
9
5

4

Using function here is needlessly employing type erasure. – Columbo Jan 12 '16 at 18:15
@Columbo Please elaborate? This is the simplest proposed solution by far. – Brian Rodriguez Jan 12 '16 at 18:16
2

@BrianRodriguez Simple != Optimal. `function` must use type erasure, because there is no information about the type of the entity stored outside the constructor template. – Columbo Jan 12 '16 at 18:18
@Columbo lambdas have no useful information in their type regardless. What do you lose by erasing its type? – Brian Rodriguez Jan 12 '16 at 18:19
1

@Columbo 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.) – Jan 12 '16 at 18:22

Marko Tunjic · Answer 4 · 2016-05-05T17:31:39.697

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

How to emulate remove_unless

4 Answers4