7

在下面的 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 : ");
}

打印.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 会被删除。有人可以为我翻译吗？非常感谢。

4

3 回答 3

11

来自 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 的副本来处理剩余的元素（如果有）。在这里，再次使用原始状态的第 N 个元素，它还删除了剩余元素中的第三个元素，实际上是第六个元素。

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

于 2012-04-22T12:44:50.797 回答
5

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

这个新谓词是可复制的，并充当（外部）计数器变量的引用包装器。

于 2012-04-22T12:42:06.900 回答
0

我阅读了《The Standard C++ Library》，找到了另一种解决方案。那就是：重新实现函数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);
    }
}

它确实有效。

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

我是学习 STL 的新手。我会感谢您耐心的回答。

非常感谢。

于 2012-04-22T13:17:13.203 回答