有状态函子 &STL:未定义的行为 [英] Stateful functors & STL : Undefined behaviour

问题描述

我正在关注这个 函数对象教程

复制下面的意大利面:

我无法理解以下内容:

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

示例如下:

#include #include <向量>#include <算法>#include <迭代器>类谓词{上市:谓词(int 条件):条件_(条件)，状态_(0){}bool operator()(int) { return ++state_ == condition_;}私人的:int条件_；国际状态_；};int main(){std::vectorvec;vec.push_back(1);vec.push_back(2);vec.push_back(3);vec.push_back(4);vec.push_back(5);谓词 p(2);std::vector::iterator pos =std::remove_if(vec.begin(), vec.end(), p);vec.erase(pos, v.end());std::copy(vec.begin(), vec.end(),std::ostream_iterator(std::cout, " "));返回0；}

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

输出:

1 3 5

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

虽然我可以看到似乎正在发生的事情，但我无法想象幕后发生的事情，这些幕后实际上标记了要移动到容器末尾的第 4 个元素.这与算法是单程还是多程有关吗?(如果有人能指出我如何推断出正确的方向，我也将不胜感激)

顺便说一句，如果我评论擦除&注意输出.

1 3 5 4 5

是什么导致容器损坏?

解决方案

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

• 未定义容器的迭代顺序，
• 算法可以自由复制函子，
• 算法可能依赖无状态，以免破坏容器内容或崩溃.

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

有一些例外情况，例如 for_each，上述情况都不适用.您可以在此处自由使用有状态函子.有关更多信息，请参阅这篇优秀文章:http://drdobbs.com/cpp/184403769.>

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

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

I am following this Function objects tutorial

Copy-pasta below:

I am unable to understand the following:

Predicates should always be implemented as stateless function objects to avoid unexpected results. There is no guarantee how often an algorithm might internally copy the predicate. Thus, having predicates that are implemented as stateful function objects might have unexecpted results.

The example is as follows:

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

If I understand (read) it correctly , it is attempting to remove the element marked as 2 in the vector. remove_if algorithm returns a new end of the container and attempting to erase all of it.

Output :

1 3 5

Clearly, not only the second element has been removed but also the fourth one. The answer to this curiosity is simply that the used algorithm 'remove_if' internally copies the predicate during its execution. And this internal copy creates a new predicate object containing its original state.

Though I can read what seems to be happening, I am unable to picture what is happening behind the scenes which actually marked even the 4th element to be moved to the end of the container. Does this have to do with an algorithm being single pass or multiple pass? ( also I would be grateful if some one could point me in the right direction how to deduce the same)

On a side note , if i comment the erase & note the output.

1 3 5 4 5

What causes the container to get corrupted ?

解决方案

The meaning of that quote should be taken at face value. For the majority of the STL algorithms, you should not implement your predicate functor such that it has observable state (AKA "side effects"), because:

• the iteration order over the container is not defined,
• the algorithm is free to make copies of the functor,
• the algorithm may depend on statelessness in order to not corrupt the container contents or crash.

The simplest way to enforce this upon yourself is to define operator() as const.

There are exceptions, such as for_each, for which none of the above apply. You are free to use stateful functors here. For more info, see this excellent article: http://drdobbs.com/cpp/184403769.

Behind the scenes, the authors of your STL implementation are free to write the remove_if (and other algorithms) any way they like, so long as it conforms to the requirements laid down by the standard. There's no real reason to worry too much about exactly why you're getting the behaviour you're seeing, beyond acknowledging that it's undefined. If you want to know the specifics, I would just take a look at the code for remove_if in the STL implementation that you're using.

As for your side-note; this is not "corruption", it's simply an artifact of how remove_if works (this would occur even for a valid predicate). The only requirement is that all the elements to the left of pos are valid (because they are to be retained). There are no requirements on what elements exist from pos onward (see here). (Chapter 32 of "Effective STL" by Scott Meyers has a good explanation of why remove_if (and so on) behave like this).

这篇关于有状态函子 &STL:未定义的行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！