How can I negate a functor in C++ (STL)?

Question

I have some function to find a value:

struct FindPredicate
{

    FindPredicate(const SomeType& t) : _t(t) {
    }
    bool operator()(SomeType& t) {
      return t == _t;
    }

private:
    const SomeType& _t;
};

bool ContainsValue(std::vector<SomeType>& v, SomeType& valueToFind) {
    return find_if(v.begin(), v.end(), FindPredicate(valueToFind)) != v.end();
}

Now I would like to write a function that checks if all members of a vector satisfy that predicate:

bool AllSatisfy(std::vector<SomeType>& v) {
    /* ... */
}

One solution is to use the std::count_if algorithm.

Does anyone know a solution that involves negating the predicate?

Answer 1

The best solution is to use the STL functional library. By deriving your predicate from unary_function<SomeType, bool> , you'll then be able to use the not1 function, which does precisely what you need (i.e. negating a unary predicate).

Here is how you could do that :

struct FindPredicate : public unary_function<SomeType, bool>
{
    FindPredicate(const SomeType& t) : _t(t) {}

    bool operator()(const SomeType& t) const {
      return t == _t;
    }

private:
    const SomeType& _t;
};

bool AllSatisfy(std::vector<SomeType>& v, SomeType& valueToFind)
{
    return find_if(v.begin(), 
                   v.end(), 
                   not1(FindPredicate(valueToFind))) == v.end();
}

---

If you want to roll your own solution (which is, IMHO, not the best option...), well, you could write another predicate that is the negation of the first one :

struct NotFindPredicate
{

    NotFindPredicate(const SomeType& t) : _t(t) {
    }
    bool operator()(SomeType& t) {
      return t != _t;
    }

private:
    const SomeType& _t;
};

bool AllSatisfy(std::vector<SomeType>& v) {
    return find_if(v.begin(), 
                   v.end(), 
                   NotFindPredicate(valueToFind)) == v.end();
}

Or you could do better and write a template functor negator, like :

template <class Functor>
struct Not
{
    Not(Functor & f) : func(f) {}

    template <typename ArgType>
    bool operator()(ArgType & arg) { return ! func(arg); }

  private:
    Functor & func;
};

that you could use as follow :

bool AllSatisfy(std::vector<SomeType>& v, SomeType& valueToFind)
{
    FindPredicate f(valueToFind);
    return find_if(v.begin(), v.end(), Not<FindPredicate>(f)) == v.end();
}

Of course, the latter solution is better because you can reuse the Not struct with every functor you want.

Answer 2

See the std library functor not1, it returns a functor that is the logical not of whatever the functor you give it would return.

You should be able to do something like:

bool AllSatisfy(std::vector<SomeType>& v, SomeType& valueToFind) {
    return find_if(v.begin(), v.end(), not1(FindPredicate(valueToFind))) != v.end();
}

Answer 3

The first time I used not1 I wondered why it wasn't simply called not.

The answer surprised me a bit (see comment).

Answer 4

As you are using it, you don't need the FindPredicate functor, since in the example you are only testing equality.

bool all_equal(std::vector<SomeType>& v, SomeType& valueToFind)
{
   return v.end() == find_if(v.begin(), v.end(), std::bind1st (equal_to (), valueToFind) );
}

bool all_not_equal( std::vector<SomeType>& v, SomeType &valueToFind ) {
{
   return v.end() == find_if(v.begin(), v.end(), std::bind1st (not_equal_to (), valueToFind) );
}

And you could just make this a template by itself.

template< typename InputIterator , typename Predicate >
bool test_all( InputIterator first, InputIterator last, Predicate pred )
{
  return last == find_if( first, last, pred );
}

test_all( v.begin(), v.end(), std::bind1st( not_equals_to_( value )) );