标准库算法是否允许复制谓词参数？ [英] Are Standard Library algorithms allowed to copy predicate arguments?

问题描述

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

  struct comp {
 std :: set< int> S; 
 comp（）：s（）{} 
 bool operator（）（int i）
 {
 return！（s.insert（i））。second; 
} 
}; 
  

但是如果谓词对象会因为某种原因被复制，那么这会中断，因为我们会得到两个副本集合成员。事实上，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）// ^^^^^这里复制一份
 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。明确（）; } 
 bool operator（）（int i）
 {
 return！（s.insert（i））。second; 
} 
}; 
 set< int>补偿:: S; 
  

但问题仍然存在：

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

解决方案

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

因此 remove_if 听起来不像是这里适当的算法。诸如将集合外部存储到函子的窍门不能解决问题;您仍然会调用未定义的行为。

---

_{1。有关更深入的讨论，请参阅Scott Meyers的项目39（创建谓词纯函数） Effective STL 。}

Suppose we'd like to remove duplicate values from a vector of ints. The usual solution is to sort the vector and erase duplicates with erase-remove idiom. But we need to mantain the order of the elements that will not be removed, so we can't sort. So one might come up with a predicate like this and use with with remove_if algorithm:

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

But this will break if predicate object will be copied for some reason, since we'll get two copies of the set member. And indeed, the gcc's implementation of remove_if does exactly that:

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;
    }

The workaround is to make set member of our functor static:

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

But the question remains:

Do we need to make sure a possible copy of predicate functor will not break our logic? Is there anything in the standard that mandates (or prohibits) certain behaviour with regard to this issue? Or is it a bug in the implementation?

解决方案

Yes, the standard does not specify how many times the predicate will be copied, nor does it say in what order the predicate will be applied to elements of the container. Essentially, predicates must act like pure functions; they must have no observable state.¹

So remove_if does not sound like an appropriate algorithm here. Hacks such as storing the set externally to the functor will not solve the problem; you'll still be invoking undefined behaviour.

---

_{1. For a more in-depth discussion, see Item 39 ("Make predicates pure functions") of Scott Meyers' Effective STL.}

这篇关于标准库算法是否允许复制谓词参数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！