3

假设我们想从ints 的向量中删除重复值。通常的解决方案是使用erase-remove idiom对向量进行排序并擦除重复项。但是我们需要维护不会被删除的元素的顺序，所以我们不能排序。所以有人可能会想出一个这样的谓词并使用 withremove_if算法：

struct comp {
    std::set<int> s;
    comp() : s() {}
    bool operator()(int i)
    {
        return !(s.insert(i)).second;
    }
};

但是如果谓词对象由于某种原因被复制，这将中断，因为我们将获得set成员的两个副本。事实上，gcc 的实现remove_if正是这样做的：

template<typename _ForwardIterator, typename _Predicate>
    _ForwardIterator
    remove_if(_ForwardIterator __first, _ForwardIterator __last,
          _Predicate __pred)
    {

      __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);

      if(__first == __last)                             // ^^^^^ here a copy is made
        return __first;
      _ForwardIterator __result = __first;
      ++__first;
      for(; __first != __last; ++__first)
        if(!bool(__pred(*__first)))
          {
            *__result = _GLIBCXX_MOVE(*__first);
            ++__result;
          }
      return __result;
    }

解决方法是使set我们的仿函数成员静态：

struct comp {
    static set<int> s;
    comp() { s. clear(); }
    bool operator()(int i)
    {
        return !(s.insert(i)).second;
    }
};
set<int> comp::s;

但问题仍然存在：

我们是否需要确保谓词函子的可能副本不会破坏我们的逻辑？ 标准中是否有任何规定（或禁止）与此问题相关的某些行为？或者它是实现中的错误？

4

3 回答 3

5

是的，标准没有指定谓词将被复制多少次，也没有说明谓词将以什么顺序应用于容器的元素。本质上，谓词必须像纯函数一样工作；它们必须没有可观察的状态。1

所以remove_if在这里听起来不像是一个合适的算法。诸如将set外部存储到函子之类的技巧并不能解决问题；你仍然会调用未定义的行为。

1. 有关更深入的讨论，请参阅Scott Meyers 的Effective STL的第 39 条（“使谓词成为纯函数”） 。

于 2012-06-17T13:34:38.150 回答
3

我们是否需要确保谓词函子的可能副本不会破坏我们的逻辑？

是的，您应该假设谓词被复制。在 C++11 中，您可以考虑使用std::ref 或 std::cref。

另一种方法是修改您的comp结构以set通过引用获取：

struct comp {
    std::set<int>& s;
    comp(std::set<int> s) : s(s) {}
    bool operator()(int i)
    {
        return !(s.insert(i)).second;
    }
};

注意：我没有就这是否适用于 发表任何声明remove_if，我只是在解决包含不应被复制的状态的复制谓词的问题。

编辑正如评论中指出的那样，这种方法从根本上被打破了。谓词调用的结果不应依赖于可变状态。

于 2012-06-17T13:25:27.410 回答
2

是的，他们可以无限次地复制参数。比使成员集静态更好的方法是在函子之外创建集并将其作为构造函数参数传递。在内部存储一个指针。

于 2012-06-17T13:24:49.563 回答