Standardowe sformułowanie C++: Czy "przez wszystkie iteratory w zasięgu" implikuje sekwencyjność?

Question

This SO question wywołał dyskusję na temat std::generate i gwarancji wykonanych przez standard. W szczególności, czy możesz używać obiektów funkcji ze stanem wewnętrznym i polegać na generate(it1, it2, gen), aby zadzwonić pod numer gen(), zapisać wynik w *it, ponownie zadzwonić pod numer gen(), zapisać w numerze *(it + 1), lub czy może on rozpocząć się od tyłu?

normy (n3337, §25.3.7/1), to mówi:

efektów: pierwszy algorytm wywołuje obiekt funkcji gen i przypisuje się wartość powrotną gen przez wszystkie iteratorami w zakresie [first,last) . Drugi algorytm wywołuje funkcję obiektu gen i przypisuje wartość zwracaną przez gen przez wszystkie iteratory w zakresie [first,first + n), jeśli n jest dodatnia, w przeciwnym razie nie robi nic.

Wydaje się, że nie zamawianie jest gwarantowany, zwłaszcza, że ​​inne paragrafy mają mocniejsze brzmienie, na przykład std::for_each (efekty: Dotyczy f do wyniku wyłuskania każdą iterację w zakresie [first,last), począwszy od pierwszego i przejściem do last - 1 Jeśli przyjmujemy to dosłownie, gwarantuje to tylko rozpoczęcie od first i kończy się na last - brak gwarancji na zamówienie pomiędzy).

Ale: Zarówno Microsoft's i Apache's C++ standard library zarówno podać przykłady na swoich stronach dokumentacji, które wymagają oceny być sekwencyjna. I zarówno libC++ (w algorithm) jak i libstdC++ (w bits/stl_algo.h) implementują to w ten sposób. Co więcej, tracisz wiele potencjalnych aplikacji dla generate bez tej gwarancji.

Czy obecne sformułowanie implikuje sekwencyjność? Jeśli nie, czy było to niedopatrzenie ze strony członków komitetu czy celowe?

(Wiem, że niewielu ludzi może dostarczyć wnikliwych odpowiedzi na to pytanie, nie spekulując ani nie dyskutując, ale moim skromnym zdaniem nie czyni to pytanie "nie konstruktywnym" zgodnie z wytycznymi SO .)

---

Dzięki @juanchopanza za wskazanie tego problemu i powołując mnie do ust o for_each.

Answer 1

W dyskusji na temat LWG475, std::for_each jest porównywany z std::transform. Zauważono, że "transform nie gwarantuje kolejności, w której jego obiekt funkcji jest nazywany". Tak, tak, komisja jest świadoma braku gwarancji sekwencyjnych w standardzie.

Nie ma przeciwnych wymagań dla zachowania niesekwencyjnego, więc Microsoft i Apache mogą swobodnie korzystać z oceny sekwencyjnej.

Answer 2

Wszędzie tam, gdzie standard nie określa kolejności w algorytmie, należy założyć, że implementacja może wykorzystać to do równoległości. Artykuł n3408 omawia opcje równoległości i wskazuje bibliotekę Thrust, która jest zarówno użyteczną reimplementacją standardowego algorytmu z obsługą równoległą, jak i proof-of-concept dla przyszłej standaryzacji równoległości w algorytmach.

Patrząc na implementację Thrust generate, wywołuje ona gen w równoległej pętli, gdy kategoria iteratora jest losowym dostępem. Jak zauważyłeś, jest to zgodne ze standardem, więc nie powinieneś zakładać, że generate zawsze będzie sekwencyjny. (Na przykład, gwint bezpieczny std::rand można skutecznie stosować generate i nie wymaga sekwencyjnego wywołania).

Jedynymi algorytmów, które gwarantują sekwencyjne wywołania są te, w numeric; jeśli twój kod zależy od wywołania sekwencyjnego, powinieneś użyć iota zamiast generate. Adaptacja istniejącego generatora:

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

wykorzystania jako:

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