是否允许标准库算法复制谓词参数

Question

假设我们想从 int s 的向量中删除重复值。通常的解决方案是使用擦除-删除习惯用语对矢量进行排序并擦除重复项。但是我们需要保持不会被删除的元素的顺序，所以我们不能排序。因此，人们可能会想出这样的谓词，并与remove_if算法一起使用：

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

但是，如果谓词对象由于某种原因被复制，这将中断，因为我们将获得set成员的两个副本。事实上，海湾合作委员会对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;

但问题仍然存在：

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

Answer 1

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

所以remove_if在这里听起来不像是一个合适的算法。 诸如将set存储在函子外部之类的黑客将无法解决问题;您仍将调用未定义的行为。

---

_{1. 有关更深入的讨论，请参阅 Scott Meyers 的有效 STL 的第 39 项（"使谓词成为纯函数"）。}

Answer 2

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

是的，您应该假设谓词已复制。在 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，我只是在解决包含不应复制的状态的复制谓词的问题。

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

Answer 3

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