使用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());

我希望找到满足谓词的所有元素并对其进行操作。

我一直在研究“find_all”或“do_if”等价物的STL算法，或者我可以用现有的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()。 这就是 lambda 真正发挥作用的地方。 例如，如果 MyPred 的意思是“可被 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(); 
                 }
               } );

乍一看，这看起来像是从 boost::lambda 语法倒退了一步，但是，它更好，因为使用 c++0x 语法实现更复杂的函子逻辑是微不足道的……在 boost::lambda 中任何非常复杂的东西都会变得棘手迅速地。 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);
}

郑重声明，虽然我见过在 list 上调用 end() 的实现时间复杂度为 O(n)，但我还没有看到任何调用 end() 的 STL 实现vector 上的 >end() 不是 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);
}

Answer 5

对于其价值 for_each_if 被视为最终增加提升。 实现你自己的并不难。

Answer 6

Lamda 函数 - 想法是做这样的事情

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

这里 。

Answer 7

您可以使用 Boost.Foreach：

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