使用functor作为谓词的C++ STL程序

Question

在下面的C++ STL程序中,我定义了一个算子Nth,如果它在第n次撤销,它返回true.我将它转换为通用算法remove_if,我得到一些奇怪的东西.

代码:

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

我在Microsoft Visual Studio 2008中运行它,我得到了结果: 它删除了我不想要的元素3和6.我认为只会删除3个.有人可以为我解释吗？非常感谢.

Answer 1

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

发生这种情况是因为算法的通常实现在算法期间在内部复制谓词:

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

该算法使用find_if()来查找应该删除的第一个元素.但是,它然后使用传递的谓词op的副本来处理剩余的元素(如果有的话).这里,再次使用处于其原始状态的Nth,并且还移除剩余元素的第三个元素,其实际上是第六个元素.

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

Answer 2

不要用std::remove_if在std::list.相反,使用列表的成员函数:

col.remove_if(Nth(3));

通用算法重新排列元素的值,以便您可以安全地从末尾擦除,但对于列表,成员算法直接删除不需要的节点而不触及任何其他元素.

更新.正如所指出的,这实际上并不能保证解决您的问题,因为您的谓词不允许具有内部按值状态.试试这个:

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

这个新谓词是可复制的,并作为围绕(外部)计数器变量的参考包装器.