Formulazione standard C++: "attraverso tutti gli iteratori nell'intervallo" implica sequenzialità?

Question

This SO question ha scatenato una discussione su std::generate e le garanzie fatte dalla norma. In particolare, è possibile utilizzare gli oggetti funzione con stato interno e fare affidamento su generate(it1, it2, gen) per chiamare gen(), archiviare il risultato in *it, chiamare di nuovo gen(), archiviare in *(it + 1) ecc. Oppure può avviarsi sul retro, ad esempio?

Lo standard (n3337, §25.3.7/1) dice:

Effetti: Il primo algoritmo richiama l'oggetto funzione gen e assegna il valore restituito GEN attraverso tutti gli iteratori nell'intervallo [first,last) . Il secondo algoritmo richiama la funzione oggetto gen e assegna il valore restituito di gen attraverso tutti gli iteratori nell'intervallo [first,first + n) se n è positivo, altrimenti non fa nulla.

Sembra che nessun ordinamento è garantito, soprattutto perché altri paragrafi hanno forte formulazione, ad esempio std::for_each (Effetti: Si applica f al risultato di dereferenziazione ogni iteratore nella gamma [first,last), a partire dalla prima e procedendo a last - 1 . Se stiamo prendendo questa lettera, si garantisce solo per iniziare a first e terminerà alle last anche se - non ci sono garanzie sul ordinamento in mezzo).

Ma: Sia Microsoft's e Apache's C++ standard library entrambi danno esempi sulle loro pagine di documentazione che richiedono la valutazione di essere sequenziale. E sia libC++ (in algorithm) che libstdC++ (in bits/stl_algo.h) lo implementano in questo modo. Inoltre, si perde un sacco di potenziali applicazioni per generate senza questa garanzia.

Condivide la formulazione attuale implica sequenzialità? In caso contrario, si trattava di una svista dei membri del comitato o intenzionale?

(Sono ben consapevole che non ci sono molte persone che possono fornire risposte penetranti a questa domanda senza limitarsi a speculare o discutere, ma a mio modesto parere, questo non rende questa domanda "non costruttiva" come da linee guida SO .)

---

Grazie a @juanchopanza per sottolineare questo problema e mi riferimento al paragrafo relativo for_each.

Answer 1

Nella discussione di LWG475, std::for_each viene confrontato con std::transform. Si noti che "transform non garantisce l'ordine in cui è chiamato il suo oggetto funzione". Quindi, sì, il comitato è consapevole della mancanza di garanzie sequenziali nello standard.

Non v'è alcun obbligo opposto per comportamento non sequenziale o, in modo Microsoft e Apache sono liberi di utilizzare una valutazione sequenziale.

Answer 2

Ovunque lo standard non specifica un ordinamento su un algoritmo, si deve presumere che un'implementazione che può sfruttare il parallelismo. Il documento n3408 discute opzioni per parallelizzazione e punti alla libreria Thrust, che è sia un utilizzabile reimplementazione in parallelo abilitato degli algoritmi standard e un concetto proof-of-per la futura standardizzazione di parallelismo negli algoritmi.

Considerando l'implementazione di Thrust di generate, chiama gen in un ciclo parallelo ogni volta che la categoria iteratore è ad accesso casuale. Come hai osservato, questo è coerente con lo standard, quindi non dovresti assumere che generate sarà sempre sequenziale. (Ad esempio, un thread-safe std::rand può essere utilizzato in modo efficiente con generate e non richiede chiamata sequenziale.)

Gli unici algoritmi che garantiscono invocazione sequenziale sono quelli in numeric; se il tuo codice dipende dal richiamo sequenziale, devi utilizzare iota al posto di generate. Adattare un generatore esistente:

template<typename F> struct iota_adapter { 
    F f; 
    operator typename std::result_of<F()>::type() { return f(); } 
    void operator++() {} 
}; 
template<typename F> iota_adapter<F> iota_adapt(F &&f) { return {f}; } 

Usa come:

#include <numeric> 
#include <iostream> 

int main() { 
    int v[5], i = 0; 
    std::iota(std::begin(v), std::end(v), iota_adapt([&i]() { return ++i; })); 
    for (auto i: v) std::cout << i << '\n'; 
}