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

Question

假设我们想要从ints 的向量中删除重复值.通常的解决方案是使用擦除 - 移除习语对矢量进行排序并擦除重复项.但我们需要保留不会被删除的元素的顺序,所以我们无法排序.所以有人可能会提出这样的谓词并与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

是的,标准没有指定谓词复制的次数,也没有说明谓词将以什么顺序应用于容器的元素.从本质上讲,谓词必须像纯函数一样 ; 他们必须没有可观察的状态.¹

所以remove_if这听起来不像一个合适的算法.诸如将set外部存储到仿函数的黑客将无法解决问题; 你仍然会调用未定义的行为.

_{1.有关更深入的讨论,请参阅Scott Meyers的Effective STL的第39项(" 使谓词纯函数 ").}