一个c++ STL程序，使用函数作为谓词

In the following C++ STL program,I define a functor Nth and it returns true if it is revoke in the nth time.And I transform it to generic algorithm remove_if,I get something strange.

在下面的c++ STL程序中，我定义了一个第n个函数，如果在第n次中被撤销，它将返回true。然后我把它转换成通用算法remove_if，我得到了一些奇怪的东西。

The code:

代码:

#include <iostream>
#include <list>
#include <algorithm>
#include "print.hpp"

using namespace std;

class Nth{
private:
    int nth,ncount;
public:
    Nth(int n):nth(n),ncount(0){}

    bool operator()(int)
    {
        return ++ncount == nth;
    }
};

int main()
{
    list<int> col;
    for (int i = 1;i <=9 ;++i)
    {
        col.push_back(i);
    }

    PRINT_ELEMENTS(col,"col : ");

    list<int>::iterator pos;
    pos = remove_if(col.begin(),col.end(),
        Nth(3));

    col.erase(pos,col.end());

    PRINT_ELEMENTS(col,"nth removed : ");
}

print.hpp:

#include <iostream>

template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
    typename T::const_iterator pos;

    std::cout << optcstr;
    for (pos=coll.begin(); pos!=coll.end(); ++pos) {
        std::cout << *pos << ' ';
    }
    std::cout << std::endl;
}

I run it in Microsoft Visual Studio 2008 and I get the result: 一个c++ STL程序，使用函数作为谓词 It deletes the elements 3 and 6 that is not I want.I thought only 3 would be deleted. Could someone interpret for me?Thanks a lot.

我在Microsoft Visual Studio 2008中运行它，得到的结果是:它删除了我不想要的元素3和6。我以为只有3个会被删除。有人能帮我翻译一下吗?非常感谢。

3 个解决方案

#1

From The C++ Standard Library: A Tutorial and Reference By Nicolai M. Josuttis

来自c++标准库:Nicolai M. Josuttis的教程和参考资料

This happens because the usual implementation of the algorithm copies the predicate internally during the algorithm:

之所以会出现这种情况，是因为通常算法的实现会在算法过程中内部复制谓词:

template <class ForwIter, class Predicate>
   ForwIter std::remove_if(ForwIter beg, ForwIter end,
                           Predicate op)
   {
       beg = find_if(beg, end, op);
       if (beg == end) {
           return beg;
       }
       else {
       ForwIter next = beg;
           return remove_copy_if(++next, end, beg, op);
       }
   }

The algorithm uses find_if() to find the first element that should be removed. However, it then uses a copy of the passed predicate op to process the remaining elements if any. Here, Nth in its original state is used again and it also removes the third element of the remaining elements, which is in fact the sixth element.

该算法使用find_if()查找应该删除的第一个元素。但是，它然后使用传递的谓词op的副本来处理剩余的元素(如果有的话)。在这里，再次使用原始状态的第n个元素，它还删除了剩余元素的第三个元素，实际上是第6个元素。

This behavior is not a bug. The standard does not specify how often a predicate might be copied internally by an algorithm. Thus, to get the guaranteed behavior of the C++ standard library you should not pass a function object for which the behavior depends on how often it is copied or called. Thus, if you call a unary predicate for two arguments and both arguments are equal, then the predicate should always yield the same result. That is, a predicate should not change its state due to a call, and a copy of a predicate should have the same state as the original. To ensure that you can't change the state of a predicate due to a function call, you should declare operator () as constant member function.

这种行为不是bug。该标准没有规定一个谓词在算法内部被复制的频率。因此，要获得c++标准库的保证行为，您不应该传递一个函数对象，该对象的行为取决于它被复制或调用的频率。因此，如果您为两个参数调用一个一元谓词，并且两个参数都是相等的，那么谓词应该总是产生相同的结果。也就是说，谓词不应该由于调用而改变其状态，谓词的副本应该具有与原谓词相同的状态。为了确保不能由于函数调用而更改谓词的状态，应该将操作符()声明为常量成员函数。

#2

Don't use std::remove_if on a std::list. Instead, use the list's member function:

不要在std::列表中使用std::remove_if。相反，使用列表的成员函数:

col.remove_if(Nth(3));

The generic algorithm rearranges the values of elements so that you can safely erase from the end, but for a list, the member algorithm removes the unwanted nodes directly without touching any other elements.

泛型算法重新排列元素的值，以便您可以安全地从末尾删除，但是对于列表，成员算法直接删除不需要的节点，而不涉及任何其他元素。

Update. As was pointed out, this isn't actually guaranteed to solve your problem, since your predicate is not allowed to have an internal by-value state. Try this instead:

更新。如前所述，这实际上并不能保证解决问题，因为您的谓词不允许有一个内部的副值状态。试试这个:

struct Nth
{
    const int n;
    int & counter;
    Nth(int N, int & c) : n(N), counter(c) { }
    bool operator()(int) const { return ++counter == N; }
};

{
    int counter = 0;
    cols.remove_if(Nth(3, counter));
}

This new predicate is copyable and acts as a reference wrapper around your (external) counter variable.

这个新谓词是可复制的，并作为(外部)计数器变量的引用包装器。

#3

I read the 《The Standard C++ Library》,and I find another solution.That is :re-implement the function remove_if:

我读了《标准c++库》,我发现另一个解决方案。即:重新实现remove_if函数:

template <class ForwIter,class Predicate>
ForwIter remove_if_re(ForwIter begin,ForwIter end,Predicate op)
{
    while(begin != end && !op(*begin))
        ++begin;
    if(begin == end)
        return begin;
    else{
        ForwIter next = begin;
        return remove_copy_if(++next,end,begin,op);
    }
}

It does work.

它的工作。

But I am a little curious.Does this implement not use a copy of the passed predicate op to process the remaining elements???

但我有点好奇。这个实现不使用传递的谓词op的副本来处理剩余的元素吗??

I am new to learn STL.I willappreciate for your patient answers.

我是学STL的新手。我将感激你耐心的回答。

Thanks a lot.

非常感谢。

#1