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

假设我们想从一个向量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;

但问题依然存在：

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

来源

2012-06-17 jrok

是的，标准没有指定谓词将被复制的次数，也没有说明谓词将以什么顺序应用于容器的元素。基本上，谓词必须像pure functions一样行事;他们必须没有可观察到的状态。因此remove_if听起来不像这里适当的算法。诸如将set外部存储到仿函数的窍门将不能解决问题;你仍然会调用未定义的行为。

_{1.对于更深入的讨论，请参见第39项（“制作谓词纯函数”）的斯科特迈尔斯Effective STL。}

来源

2012-06-17 13:34:38

+1关于纯功能和良好参考的好处。 – juanchopanza

有标准指定顺序的算法。像'std :: copy'，不是？标准中的“备注：稳定”是什么意思，是不是要求订单得到保留？ – jrok

@jrok：只有在保留元素的相对顺序不会改变的意义上，它才是稳定的，而不是OP所希望的。（并且'copy'不带谓词，'copy_if'不带谓词，'copy_if'只带一个，但没有指定它的应用顺序。） –

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

来源

2012-06-17 13:24:49

我相信这样的结果仍然没有明确定义;该标准没有强制命令'remove_if'必须将谓词应用于容器元素。 –

@OliCharlesworth：true，但是，由于标准指定它适用于Forward Iterator，所以大多数实现将实际应用它以便出于效率原因。有时候我想知道标准是否应该明确要求这个标准，标准的问题不能保证通常提出的是人们最终依赖（通常没有意识到）依赖于实现依赖的保证。 –

@OliCharlesworth：除了什么马修已经提到的，该结果被存储在一个'OutputIterator'（即它不能走回头路）和谓词的执行次数恰好是容器的大小更重要。除了测试每个元素的前向循环以及决定是否复制之外，以任何其他方式执行都是不可能的。 –

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

是的，你应该假设谓词被复制。在C++ 11中，您可以考虑使用std::ref or 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-17 13:25:27 juanchopanza

我相信这个结果还没有明确定义;该标准没有强制命令'remove_if'必须将谓词应用于容器元素。 –

@OliCharlesworth我甚至没有考虑'remove_if'，只是处理复制的谓词问题。我会澄清我的答案。 – juanchopanza

这是同一问题的一部分。谓词必须表现为[纯函数]（http://en.wikipedia.org/wiki/Pure_function）。 –

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

回答

相关问题