c++ - 是否允许标准库算法复制谓词参数？

Question

假设我们想从 int vector 中删除重复值。通常的解决方案是使用 erase-remove 习惯用法对 vector 进行排序并删除重复项。但是我们需要维护不会被移除的元素的顺序，所以我们无法排序。所以有人可能想出这样的谓词并使用 with with remove_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;

但问题依然存在:

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

Answer 1

是的，标准没有指定谓词将被复制多少次，也没有说明谓词将以什么顺序应用于容器的元素。本质上，谓词的行为必须像 pure functions ;它们必须没有可观察的状态。¹

所以 remove_if 在这里听起来不像是合适的算法。将 set 外部存储到仿函数之类的 hack 不会解决问题；你仍然会调用未定义的行为。

---

<子>1。有关更深入的讨论，请参阅 Scott Meyers 的 Effective STL 的第 39 项(“使谓词成为纯函数”) .