为generate保证是顺序执行的？ [英] Is generate Guaranteed to be Executed Sequentially?

问题描述

有人告诉我，<一个href="http://stackoverflow.com/questions/33280217/how-to-use-algorithms-to-fill-vector-of-vectors/33282441?noredirect=1#comment54361802_33280760">here即：

  

生成的顺序，不能保证=>取决于实施

我已经看过了 gcc的实施生成 ：

 的（; __first = __last;！++ __第一）
* __第一= __gen（）;
 

和Visual Studio中实现它完全相同的方式。这是一种解脱，我作为使用拉姆达在生成读取和写入，以捕获可能undeterministic结果：

  INT富[] = {1，0，13};
矢量＆lt; int的＆GT;杆（3）;

产生（bar.begin（），bar.end（），[＆安培;]（）{
    静态自动I = 0;
    静态自动总= 0;

    共有+ = foo的[I]
    返回富[I] /总和;
}）;
 

我希望 栏包含 {1，0，0} 。

如果我允许的0误差失序这甚至可能会导致一个除执行。

所以我睡更容易，如果这个问题能有证据来回答生成需要按顺序执行。

由于这里说明，我知道 实验::并行::生成 不会是连续的。我只是问生成。

解决方案

我很感兴趣这方面都做了一些研究。

目前这个答案的底部是相关部门从标准的副本作为2011年。

您将从性病的模板声明见::生成＆LT;＆GT; 迭代器参数必须符合的概念 ForwardIterator 和输出迭代器分别。

一个ForwardIterator的不支持随机访问的。它只能读取或顺序写。一个输出迭代器更严格的 - 它的运算符* 隐含包括符++ <效果/ code>。这是概念的一个明确的特征。

因此​​，通过暗示，这个功能的实现的必须的访问元素顺序（并因此产生价值顺序）以来的不这样做会撕毁合同隐含在接口。

因此​​，标准的确实（含蓄，平静地）保证的std ::生成初始化它的元素顺序。这将是不可能写一个良好的实施的std ::生成的没有。

QED

  

25.3.7生成[a​​lg.generate]

 模板＆LT;类ForwardIterator，类发生器＆GT;
无效生成（ForwardIterator第一，ForwardIterator最后，
发电机GEN）;

模板＆LT;类输出迭代器，班级规模，班发电机＆GT;
输出迭代器generate_n（输出迭代器第一，大小为n，发电机GEN）;
 

  

1效果：第一种算法调用函数对象根和   通过该范围内的所有的迭代分配根的返回值   [第一，最后）。第二种算法调用函数对象根和   通过该范围内的所有的迭代分配根的返回值   [第一，+ N）如果n为正，否则就什么也不做。

     

2   要求：根不带任何参数，尺寸应转换到   整体式（4.7，12.3）。

     

3返回：generate_n回报第一+ N的   为n的非负的值和第一对负的值。

     

4的复杂性：   究竟最后的 - 第一，N或0调用根和任务的，   分别。

I was told here that:

The order of generate is not guaranteed => depending on the implementation

I have looked up gcc's implementation of generate:

  for (; __first != __last; ++__first)
*__first = __gen();

And Visual Studio implements it identically to that. This is a relief to me as using a lambda in generate that reads and writes to a capture could have undeterministic results:

int foo[] = {1, 0, 13};
vector<int> bar(3);

generate(bar.begin(), bar.end(), [&]() {
    static auto i = 0;
    static auto total = 0;

    total += foo[i];
    return foo[i] / total;
});

I expect bar to contain {1, 0, 0}.

If I am allowed to execute out of order this could even cause a divide by 0 error.

So I'd sleep easier if this question could be answered with proof that generate is required to execute sequentially.

As a note here, I know that experimental::parallel::generate will not be sequential. I'm just asking about generate.

解决方案

I was intrigued by this so have done some research.

At the bottom of this answer is a copy of the relevant section from the standard as of 2011.

You will see from the template declaration of std::generate<> that the iterator parameters must conform to the concept of a ForwardIterator and OutputIterator respectively.

A ForwardIterator does not support random access. it can only read or write sequentially. An OutputIterator is even more restrictive - its operator* implicitly includes the effect of an operator++. This is an explicit feature of the concept.

Therefore, by implication, the implementation of this function must access elements sequentially (and therefore generate values sequentially) since to not do so would break the contract implicit in the interface.

Therefore the standard does (implicitly and quietly) guarantee that std::generate initialise its elements sequentially. It would be impossible to write a well-formed implementation of std::generate that did not.

QED

25.3.7 Generate [alg.generate]

template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
Generator gen);

template<class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

1 Effects: The first algorithm invokes the function object gen and assigns the return value of gen through all the iterators in the range [first,last). The second algorithm invokes the function object gen and assigns the return value of gen through all the iterators in the range [first,first + n) if n is positive, otherwise it does nothing.

2 Requires: gen takes no arguments, Size shall be convertible to an integral type (4.7, 12.3).

3 Returns: generate_n returns first + n for non-negative values of n and first for negative values.

4 Complexity: Exactly last - first, n, or 0 invocations of gen and assignments, respectively.

这篇关于为generate保证是顺序执行的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！