Est-il valide d'utiliser std :: transform avec std :: back_inserter?

20

Cppreference a cet exemple de code pour 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; });

Mais cela dit aussi:

std::transformne garantit pas l'application dans l'ordre de unary_opou binary_op. Pour appliquer une fonction à une séquence dans l'ordre ou pour appliquer une fonction qui modifie les éléments d'une séquence, utilisez std::for_each.

C'est probablement pour permettre des implémentations parallèles. Cependant, le troisième paramètre de std::transformest un LegacyOutputIteratorqui a la postcondition suivante pour ++r:

Après cette opération, il rn'est pas nécessaire d'être incrémentable et aucune copie de la valeur précédente de rne doit plus être déréférencable ou incrémentable.

Il me semble donc que l'affectation de la sortie doit se faire dans l'ordre. Signifient-ils simplement que l'application de unary_oppeut être hors service et stockée dans un emplacement temporaire, mais copiée dans l'ordre de sortie? Cela ne ressemble pas à quelque chose que vous voudriez faire.

La plupart des bibliothèques C ++ n'ont pas encore implémenté d'exécuteurs parallèles, mais Microsoft l'a fait. Je suis sûr que c'est le code correspondant, et je pense qu'il appelle cette fonction pour enregistrer des morceaux de itérateurs à la sortie, ce qui est certainement pas une chose valable de le faire parce que peut être invalidée par incrémenter copies.populate()LegacyOutputIterator

Qu'est-ce que je rate?

Timmmm
la source
Un simple test dans godbolt montre que c'est un problème. Avec C ++ 20 et transformversion qui décide d'utiliser ou non le paralélisme. Le transformpour les grands vecteurs échoue.
Croolman
6
@Croolman Votre code est incorrect, car vous réinsérez dans s, ce qui invalide les itérateurs.
Daniel Langr
@DanielsaysreinstateMonica Oh schnitzel vous avez raison. Le peaufinait et le laissait dans un état non valide. Je reprends mon commentaire.
Croolman
Si vous utilisez std::transformavec la politique d'exaction, un itérateur d'accès aléatoire est requis, ce qui back_inserterne peut pas être réalisé. La documentation des pièces citées par l'OMI fait référence à ce scénario. Notez l'exemple dans la documentation utilise std::back_inserter.
Marek R
@Croolman Décide d'utiliser automatiquement le parallélisme?
curiousguy

Réponses:

9

1) Les exigences de l'itérateur de sortie dans la norme sont complètement rompues. Voir LWG2035 .

2) Si vous utilisez un itérateur de sortie purement et une plage de source d'entrée purement, l'algorithme ne peut pas faire grand-chose d'autre en pratique; il n'a d'autre choix que d'écrire dans l'ordre. (Cependant, une implémentation hypothétique peut choisir de mettre en cas particulier ses propres types, comme std::back_insert_iterator<std::vector<size_t>>; je ne vois pas pourquoi une implémentation voudrait le faire ici, mais elle est autorisée à le faire.)

3) Rien dans la norme ne garantit l' transformapplication des transformations dans l'ordre. Nous examinons un détail d'implémentation.

Cela std::transformne nécessite que des itérateurs de sortie ne signifie pas qu'il ne peut pas détecter des forces d'itérateur plus élevées et réorganiser les opérations dans de tels cas. En effet, les algorithmes distribuent tout le temps la force des itérateurs , et ils ont un traitement spécial pour les types d'itérateurs spéciaux (comme les pointeurs ou les itérateurs vectoriels) tout le temps .

Lorsque la norme veut garantir une commande particulière, elle sait comment la dire (voir std::copy«partir de firstet continuer vers last»).

TC
la source
5

De n4385:

§25.6.4 Transformer :

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

Renvoie: back_insert_iterator (x).

§23.5.2.1 Modèle de classe back_insert_iterator

using iterator_category = output_iterator_tag;

std::back_inserterNe peut donc pas être utilisé avec des versions parallèles de std::transform. Les versions qui prennent en charge les itérateurs de sortie lisent à partir de leur source avec les itérateurs d'entrée. Comme les itérateurs d'entrée ne peuvent être pré- et post-incrémentés (§23.3.5.2 Itérateurs d'entrée) et qu'il n'y a qu'une exécution séquentielle ( c'est -à- dire non parallèle), l'ordre doit être préservé entre eux et l'itérateur de sortie.

Paul Evans
la source
2
Notez que ces définitions de la norme C ++ n'évitent pas les implémentations pour fournir des versions spéciales d'algorithmes qui sont sélectionnés pour des types d'itérateurs supplémentaires. Par exemple, std::advancen'a qu'une seule définition qui prend d' entrée-itérateurs , mais libstdc ++ fournit des versions supplémentaires pour bidirectionnelle itérateurs et -accès-itérateurs aléatoires . La version particulière est ensuite exécutée en fonction du type d'itérateur passé .
Daniel Langr
Je ne pense pas que votre commentaire soit correct - ForwardIteratorcela ne signifie pas que vous devez faire les choses dans l'ordre. Mais vous avez souligné ce que j'ai manqué - pour les versions parallèles qu'ils n'utilisent ForwardIteratorpas OutputIterator.
Timmmm
1
Ah oui, oui je pense que nous sommes d'accord.
Timmmm
1
Cette réponse pourrait bénéficier de l'ajout de quelques mots pour expliquer ce qu'elle signifie réellement.
Barry
1
@Barry Ajout de quelques mots, tous les commentaires sont très appréciés.
Paul Evans
0

Donc, ce qui m'a manqué, c'est que les versions parallèles prennent LegacyForwardIterators, non LegacyOutputIterator. A LegacyForwardIterator peut être incrémenté sans invalider des copies de celui-ci, il est donc facile de l'utiliser pour implémenter un parallèle hors service std::transform.

Je pense que les versions non parallèles de std::transform doivent être exécutées dans l'ordre. Soit cppreference se trompe, soit la norme laisse simplement cette exigence implicite car il n'y a pas d'autre moyen de l'implémenter. (Le fusil de chasse ne parcourt pas la norme pour le savoir!)

Timmmm
la source
Les versions non parallèles de transform peuvent s'exécuter dans le désordre si tous les itérateurs sont suffisamment forts. Dans l'exemple de la question, ils ne le sont pas, de sorte que la spécialisation de transformdoit être en ordre.
Caleth
Non, ils ne le peuvent pas, car LegacyOutputIteratorvous oblige à l'utiliser dans l'ordre.
Timmmm
Il peut se spécialiser différemment pour std::back_insert_iterator<std::vector<T>>et std::vector<T>::iterator. Le premier doit être en ordre. Le second n'a pas une telle restriction
Caleth
Ah, attendez, je vois ce que vous voulez dire - s'il vous arrive de passer un LegacyForwardIteratordans le non parallèle transform, il pourrait avoir une spécialisation pour ce qui le fait dans le désordre. Bon point.
Timmmm
0

Je crois que la transformation est garantie d'être traitée dans l'ordre . std::back_inserter_iteratorest un itérateur de sortie (son iterator_categorytype de membre est un alias pour std::output_iterator_tag) selon [back.insert.iterator] .

Par conséquent, std::transformn'a pas d'autre option sur la façon de procéder à la prochaine itération que d'appeler membre operator++sur le resultparamètre.

Bien sûr, cela n'est valable que pour les surcharges sans politique d'exécution, où std::back_inserter_iteratorne peut pas être utilisé (ce n'est pas un itérateur de transfert ).


BTW, je ne voudrais pas argumenter avec des citations de cppreference. Les déclarations y sont souvent imprécises ou simplifiées. Dans de tels cas, il est préférable de regarder la norme C ++. Où, en ce qui concerne std::transform, il n'y a aucune citation sur l'ordre des opérations.

Daniel Langr
la source
"Standard C ++. Où, en ce qui concerne std :: transform, il n'y a pas de citation sur l'ordre des opérations" Puisque l'ordre n'est pas mentionné, n'est-il pas spécifié?
HolyBlackCat
@HolyBlackCat Explicitement non spécifié, mais imposé par l'itérateur de sortie. Notez qu'avec les itérateurs de sortie, une fois que vous l'incrémentez, vous ne pouvez plus déréférencer une valeur d'itérateur précédente.
Daniel Langr