有状态的仿函数和STL:未定义的行为

Question

我正在关注这个Function对象教程

复制面食如下:

我无法理解以下内容:

应始终将谓词实现为无状态函数对象,以避免意外结果.无法保证算法在内部复制谓词的频率.因此,具有作为有状态函数对象实现的谓词可能具有未执行的结果.

示例如下:

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

如果我理解(读)它正确,它试图删除向量中标记为2的元素.remove_if算法返回容器的新端并尝试擦除所有容器.

输出:

1 3 5

显然,不仅第二个元素被删除,第四个元素也被删除.这种好奇心的答案很简单,所使用的算法'remove_if'在执行期间在内部复制谓词.此内部副本创建一个包含其原始状态的新谓词对象.

虽然我可以阅读似乎正在发生的事情,但我无法想象幕后发生的事情,这实际上标记了即使要移动到容器末端的第4个元素.这与单程或多程算法有关吗？(如果有人能指出我正确的方向如何推断出同样的事情,我将不胜感激)

另外,如果我评论擦除并记下输出.

1 3 5 4 5

导致容器损坏的原因是什么？

Answer 1

该引用的含义应该按面值进行.对于大多数STL算法,您不应该实现谓词仿函数,使其具有可观察状态(AKA"副作用"),因为:

• 没有定义容器上的迭代顺序,
• 该算法可以自由地制作仿函数的副本,
• 算法可能依赖于无状态,以便不破坏容器内容或崩溃.

对自己强制执行此操作的最简单方法是定义operator()为const.

有些例外情况,例如for_each上述情况均不适用.您可以在这里使用有状态仿函数.有关详细信息,请参阅此优秀文章:http://drdobbs.com/cpp/184403769.

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

至于你的旁注; 这不是"腐败",它只是一个如何remove_if工作的工件(即使对于有效的谓词也会发生这种情况).唯一的要求是左边的所有元素pos都是有效的(因为它们将被保留).对于从哪个元素开始存在没有要求pos(见这里).(Scott Meyers 的" Effective STL "第32章很好地解释了为什么remove_if(等等)表现得像这样).