c++ - 有状态仿函数和 STL : Undefined behaviour

Question

我正在关注这个Function objects tutorial

复制下面的意大利面:

我无法理解以下内容:

谓词应始终作为无状态函数对象来实现，以避免意外结果。无法保证算法在内部复制谓词的频率。因此，将谓词实现为有状态函数对象可能会产生意外结果。

例子如下:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

class predicate
{
public:
   predicate(int condition) :
      condition_(condition), state_(0) {}
   bool operator()(int) { return ++state_ == condition_; }

private:
   int condition_;
   int state_;
};

int main()
{
   std::vector<int> vec;
   vec.push_back(1);
   vec.push_back(2);
   vec.push_back(3);
   vec.push_back(4);
   vec.push_back(5);

   predicate p(2);
   std::vector<int>::iterator pos =
      std::remove_if(vec.begin(), vec.end(), p);
   vec.erase(pos, v.end());

   std::copy(vec.begin(), vec.end(),
             std::ostream_iterator<int>(std::cout, " "));

   return 0;
}

如果我正确理解(阅读)它，它会尝试删除 vector 中标记为 2 的元素。 remove_if 算法返回容器的新末端并尝试删除所有容器。

输出:

1 3 5

很明显，不仅第二个元素被移除了，第四个元素也被移除了。对这种好奇心的回答很简单，即所使用的算法“remove_if”在执行过程中会在内部复制谓词。并且这个内部拷贝创建了一个包含其原始状态的新谓词对象。

虽然我能读懂似乎正在发生的事情，但我无法想象幕后发生的事情实际上标记了第四个元素被移动到容器的末尾。这是否与算法是单次通过还是多次通过有关？ (如果有人能指出正确的方向如何推断出相同的结果，我将不胜感激)

旁注，如果我评论删除并注意输出。

1 3 5 4 5

是什么导致容器损坏？

Answer 1

这句话的意思应该从表面上看。对于大多数 STL 算法，您不应该实现具有可观察状态(也称为“副作用”)的谓词仿函数，因为:

• 未定义容器的迭代顺序，
• 算法可以自由复制仿函数，
• 该算法可能依赖于无状态，以免损坏容器内容或崩溃。

对自己实现此操作的最简单方法是将 operator() 定义为 const。

也有异常(exception)，例如 for_each，以上均不适用。您可以在这里自由使用有状态仿函数。有关详细信息，请参阅这篇优秀文章:http://drdobbs.com/cpp/184403769 .

在幕后，您的 STL 实现的作者可以按照他们喜欢的任何方式自由编写 remove_if(和其他算法)，只要它符合标准规定的要求。除了承认它是未定义的之外，没有真正的理由过分担心你得到你所看到的行为的确切原因。如果您想了解具体细节，我只想看一下您正在使用的 STL 实现中的 remove_if 代码。

至于你的旁注；这不是“损坏”，它只是 remove_if 工作方式的产物(即使对于有效谓词也会发生这种情况)。唯一的要求是 pos left 的所有元素都有效(因为要保留它们)。对于从 pos 开始存在哪些元素没有要求(参见 here )。 (Scott Meyers 的 "Effective STL" 的第 32 章很好地解释了为什么 remove_if(等等)会这样)。