Czy można używać std :: transform z std :: back_inserter?

Cppreference ma ten przykładowy kod dla std::transform:

std::vector<std::size_t> ordinals;
std::transform(s.begin(), s.end(), std::back_inserter(ordinals),
               [](unsigned char c) -> std::size_t { return c; });

Ale mówi również:

std::transformnie gwarantuje zastosowania unary_oplub binary_op. Aby zastosować funkcję do sekwencji w kolejności lub zastosować funkcję, która modyfikuje elementy sekwencji, użyj std::for_each.

Ma to prawdopodobnie umożliwić równoległe wdrożenia. Jednak trzecim parametrem std::transformjest LegacyOutputIteratornastępujący warunek ++r:

Po tej operacji rnie wymaga się, aby była inkrementowalna, a wszelkie kopie poprzedniej wartości rnie muszą już być dereferencyjne ani inkrementowalne.

Wydaje mi się więc, że przyporządkowanie danych wyjściowych musi nastąpić po kolei. Czy oznaczają one po prostu, że aplikacja unary_opmoże być nieczynna i przechowywana w tymczasowej lokalizacji, ale kopiowana na wyjście w odpowiedniej kolejności? To nie brzmi jak coś, co kiedykolwiek chciałbyś zrobić.

Większość bibliotek C ++ nie zaimplementowało jeszcze równoległych programów wykonawczych, ale Microsoft ma. Jestem prawie pewien, że jest to odpowiedni kod i myślę, że wywołuje tę populate()funkcję, aby rejestrować iteratory w porcjach danych wyjściowych, co z pewnością nie jest prawidłową rzeczą, ponieważ LegacyOutputIteratormoże zostać unieważnione przez zwiększenie jej kopii.

czego mi brakuje?

1) Wymagania iteratora wyjściowego w normie są całkowicie zepsute. Zobacz LWG2035 .

2) Jeśli używasz iteratora czysto wyjściowego i zakresu wyłącznie wejściowego źródła, algorytm może zrobić niewiele więcej; nie ma wyboru, musi pisać w kolejności. (Jednak hipotetyczna implementacja może wybrać specjalne przypadki własnych typów, na przykład std::back_insert_iterator<std::vector<size_t>>; Nie rozumiem, dlaczego jakakolwiek implementacja chciałaby to zrobić tutaj, ale jest to dozwolone).

3) Nic w standardowych gwarancjach, które transformstosują transformacje w kolejności. Patrzymy na szczegół implementacji.

To std::transformwymaga tylko iteratorów wyjściowych, co nie oznacza, że ​​nie może wykryć wyższych sił iteratora i zmienić kolejność operacji w takich przypadkach. Rzeczywiście, algorytmy wysyłką na iteratora wytrzymałość przez cały czas , a oni mają specjalnego traktowania dla specjalnych typów iterator (jak wskazówki lub iteratory wektor) cały czas .

Kiedy standard chce zagwarantować określone zamówienie, wie, jak to powiedzieć (patrz std::copy„zaczynając od firsti przechodząc do last”).

Od n4385:

§25.6.4 Przekształcenie :

template<class InputIterator, class OutputIterator, class UnaryOperation>
constexpr OutputIterator
transform(InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op);

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class UnaryOperation>
ForwardIterator2
transform(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 result, UnaryOperation op);

template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
constexpr OutputIterator
transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);

template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class BinaryOperation>
ForwardIterator
transform(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator result, BinaryOperation binary_op);

§23.5.2.1.2 back_inserter

template<class Container>
constexpr back_insert_iterator<Container> back_inserter(Container& x);

Zwraca: back_insert_iterator (x).

§23.5.2.1 Szablon klasy back_insert_iterator

using iterator_category = output_iterator_tag;

Dlatego std::back_inserternie można go używać z równoległymi wersjami std::transform. Wersje obsługujące iteratory wyjściowe czytane ze źródła za pomocą iteratorów wejściowych. Od iteratory wejściowe mogą być tylko przed i po zwiększany (§23.3.5.2 iteratory wejściowe) i jest tylko kolejny ( tj nierównoległe) wykonanie, zlecenie musi być zachowana między nimi a iteratora wyjściowego.

Więc tęskniłem za tym, że wersje równoległe wymagają LegacyForwardIterators, a nie LegacyOutputIterator. LegacyForwardIterator Może być zwiększany bez unieważniania kopie, więc łatwo jest wykorzystać do wdrożenia out-of-order równolegle std::transform.

Myślę, że nierównoległe wersje std::transform muszą być wykonywane w kolejności. Albo cppreferencja jest w tym zakresie błędna, albo być może standard po prostu pozostawia to wymaganie niejawne, ponieważ nie ma innego sposobu na jego wdrożenie. (Strzelba nie przedziera się przez standard, żeby się dowiedzieć!)

Uważam, że transformacja jest gwarantowana w kolejności . std::back_inserter_iteratorjest iteratorem wyjściowym (jego iterator_categorytyp elementu jest aliasem std::output_iterator_tag) zgodnie z [back.insert.iterator] .

W związku z tym std::transformnie ma innej opcji, jak przejść do następnej iteracji, niż wywołać członka operator++w resultparametrze.

Oczywiście dotyczy to tylko przeciążeń bez zasad wykonywania, w których std::back_inserter_iteratornie można ich używać (nie jest to iterator przekazywania ).

BTW, nie argumentowałbym cytatami z cppreferencji. Stwierdzenia tam często są nieprecyzyjne lub uproszczone. W takich przypadkach lepiej spojrzeć na standard C ++. Tam, gdzie w odniesieniu do std::transform, nie ma cytatu o kolejności operacji.