Используя STL для поиска всех элементов в векторе

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

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 и сравнения.

Ответ 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 ) ]
             );

<ч/" > Update: Выполнение этого с синтаксисом лямбда С++ 0x также очень приятно (продолжение с предикатом по модулю 2):

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

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

Ответ 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;
    };

Ответ 3

Можно ли изменить вектор? Вы можете посмотреть на алгоритм разбиения.
Алгоритм разделения

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

Ответ 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 гарантированно имеют итераторы с произвольным доступом.

Тем не менее, если вас беспокоит неэффективное 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);
}

Ответ 5

Для чего его ценность for_each_if рассматривается как возможное дополнение к boost. Нетрудно реализовать свои собственные.

Ответ 6

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

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

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

Ответ 7

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

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