используя STL, чтобы найти все элементы в векторе

Question

У меня есть коллекция элементов, с которыми мне нужно работать, вызывая функции-члены для коллекции:

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

Для вызова функций без аргументов это довольно просто:

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

Подобное можно сделать, если у функции есть один аргумент, который я хочу вызвать.

Моя проблема в том, что я хочу вызвать функцию для элементов в векторе, если она удовлетворяет некоторому условию. std::find_if возвращает итератор для первого элемента, удовлетворяющего условиям предиката.

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

Я хочу найти всех элементов, соответствующих предикату, и оперировать ими.

Я искал алгоритмы STL для эквивалента "find_all" или "do_if", или как я могу сделать это с существующим STL (так что мне нужно только выполнить итерацию один раз), скорее чем катиться самостоятельно или просто сделать стандартную итерацию, используя цикл for и сравнения.

Answer 1

Boost Lambda делает это легко.

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

Вы можете даже покончить с определением MyPred (), если это просто. Это где лямбда действительно сияет. Например, если MyPred означает «делится на 2»:

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

<ч /> Обновление: Делать это с помощью синтаксиса C ++ 0x лямбда также очень приятно (продолжая с предикатом по модулю 2):

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

На первый взгляд это выглядит как шаг назад от синтаксиса boost :: lambda, однако, это лучше, потому что более сложная логика функторов тривиальна для реализации с синтаксисом c ++ 0x ... где что-то очень сложное в boost :: Лямбда быстро становится хитрой. Microsoft Visual Studio 2010 beta 2 в настоящее время реализует эту функцию.

Answer 2

Я написал for_each_if() и for_each_equal(), которые делают то, что, я думаю, вы ищете.

for_each_if() принимает функтор предиката для оценки равенства, а for_each_equal() принимает значение любого типа и выполняет прямое сравнение с использованием operator ==. В обоих случаях передаваемая функция вызывается для каждого элемента, который проходит тест на равенство.

/* ---

    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

Можно ли менять вектор? Возможно, вы захотите взглянуть на алгоритм разбиения.
Алгоритм разбиения

Другой вариант - изменить MyType::myfunc, чтобы либо проверить элемент, либо взять предикат в качестве параметра и использовать его для проверки элемента, на котором он работает.

Answer 4

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

Кстати, хотя я видел реализацию, в которой вызов end() на list был O (n), я не видел ни одной реализации STL, где вызов end() на vector был чем-то другим чем O (1) - в основном потому, что vector s гарантированно имеют итераторы с произвольным доступом.

Несмотря на это, если вас беспокоит неэффективность end(), вы можете использовать этот код:

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

Answer 5

Вы можете использовать Boost.Foreach :

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

Answer 6

Функции Lamda - идея состоит в том, чтобы сделать что-то подобное

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

Оригинальный пост здесь .

Answer 7

За то, что стоит for_each_if , рассматривается как возможное дополнение к бусту. Это не сложно реализовать свой собственный.