using STL to find all elements in a vector

Question

I have a collection of elements that I need to operate over, calling member functions on the collection:

std::vector<MyType> v;
... // vector is populated

For calling functions with no arguments it's pretty straight-forward:

std::for_each(v.begin(), v.end(), std::mem_fun(&MyType::myfunc));

A similar thing can be done if there's one argument to the function I wish to call.

My problem is that I want to call a function on elements in the vector if it meets some condition. std::find_if returns an iterator to the first element meeting the conditions of the predicate.

std::vector<MyType>::iterator it  = 
      std::find_if(v.begin(), v.end(), MyPred());

I wish to find all elements meeting the predicate and operate over them.

I've been looking at the STL algorithms for a "find_all" or "do_if" equivalent, or a way I can do this with the existing STL (such that I only need to iterate once), rather than rolling my own or simply do a standard iteration using a for loop and comparisons.

Answer 1

Is it ok to change the vector? You may want to look at the partition algorithm.
Partition algorithm

Another option would be to change your MyType::myfunc to either check the element, or to take a predicate as a parameter and use it to test the element it's operating on.

Answer 2

I wrote a for_each_if() and a for_each_equal() which do what I think you're looking for.

for_each_if() takes a predicate functor to evaluate equality, and for_each_equal() takes a value of any type and does a direct comparison using operator ==. In both cases, the function you pass in is called on each element that passes the equality test.

/* ---

    For each
    25.1.1

     template< class InputIterator, class Function, class T>
      Function for_each_equal(InputIterator first, InputIterator last, const T& value, Function f)

     template< class InputIterator, class Function, class Predicate >
      Function for_each_if(InputIterator first, InputIterator last, Predicate pred, Function f)

    Requires: 

     T is of type EqualityComparable (20.1.1) 

    Effects: 

      Applies f to each dereferenced iterator i in the range [first, last) where one of the following conditions hold:

      1: *i == value
      2: pred(*i) != false

    Returns: 

     f

    Complexity: 

     At most last - first applications of f

    --- */

    template< class InputIterator, class Function, class Predicate >
    Function for_each_if(InputIterator first, 
          InputIterator last, 
          Predicate pred, 
          Function f)
    {
     for( ; first != last; ++first)
     {
      if( pred(*first) )
       f(*first);
     }
     return f;
    };

    template< class InputIterator, class Function, class T>
    Function for_each_equal(InputIterator first, 
          InputIterator last, 
          const T& value, 
          Function f)
    {
     for( ; first != last; ++first)
     {
      if( *first == value )
       f(*first);
     }
     return f;
    };

Answer 3

For what its worth for_each_if is being considered as an eventual addition to boost. It isn't hard to implement your own.

Answer 4

Boost Lambda makes this easy.

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/if.hpp>

std::for_each( v.begin(), v.end(), 
               if_( MyPred() )[ std::mem_fun(&MyType::myfunc) ] 
             );

You could even do away with defining MyPred(), if it is simple. This is where lambda really shines. E.g., if MyPred meant "is divisible by 2":

std::for_each( v.begin(), v.end(), 
               if_( _1 % 2 == 0 )[ std::mem_fun( &MyType::myfunc ) ]
             );

---

Update: Doing this with the C++0x lambda syntax is also very nice (continuing with the predicate as modulo 2):

std::for_each( v.begin(), v.end(),
               [](MyType& mt ) mutable
               {
                 if( mt % 2 == 0)
                 { 
                   mt.myfunc(); 
                 }
               } );

At first glance this looks like a step backwards from boost::lambda syntax, however, it is better because more complex functor logic is trivial to implement with c++0x syntax... where anything very complicated in boost::lambda gets tricky quickly. Microsoft Visual Studio 2010 beta 2 currently implements this functionality.

Answer 5

Lamda functions - the idea is to do something like this

for_each(v.begin(), v.end(), [](MyType& x){ if (Check(x) DoSuff(x); })

Origial post here.

Answer 6

You can use Boost.Foreach:

BOOST_FOREACH (vector<...>& x, v)
{
    if (Check(x)
        DoStuff(x);
}

Answer 7

std::vector<int> v, matches;
std::vector<int>::iterator i = v.begin();
MyPred my_pred;
while(true) {
    i = std::find_if(i, v.end(), my_pred);
    if (i == v.end())
        break;
    matches.push_back(*i);
}

For the record, while I have seen an implementation where calling end() on a list was O(n), I haven't seen any STL implementations where calling end() on a vector was anything other than O(1) -- mainly because vectors are guaranteed to have random-access iterators.

Even so, if you are worried about an inefficient end(), you can use this code:

std::vector<int> v, matches;
std::vector<int>::iterator i = v.begin(), end = v.end();
MyPred my_pred;
while(true) {
    i = std::find_if(i, v.end(), my_pred);
    if (i == end)
        break;
    matches.push_back(*i);
}