À quoi sert le std::contiguous_iterator ?

Question

Dans quel but puis-je l'utiliser ? Pourquoi est-il meilleur que random_access_iterator ? Y a-t-il un avantage à l'utiliser ?

Answer 1

Pour un itérateur contigu, vous pouvez obtenir un pointeur sur l'élément vers lequel l'itérateur "pointe", et l'utiliser comme un pointeur sur un tableau contigu.

Cela ne peut pas être garanti avec un itérateur à accès aléatoire.

Rappelez-vous que par exemple std::deque est un conteneur à accès aléatoire, mais ce n'est généralement pas un conteneur contigu (par opposition à std::vector qui est à la fois à accès aléatoire et contigu).

Answer 2

En C++17, la notion de std::contiguous_iterator . Il y a le ContiguousIterator nommé exigence cependant. Cela représente un itérateur à accès aléatoire sur une séquence d'éléments où chaque élément est stocké de manière contiguë, exactement de la même manière qu'un tableau. Ce qui signifie qu'il est possible, étant donné un pointeur vers un value_type d'un itérateur, pour effectuer une arithmétique de pointeur sur ce pointeur, ce qui fonctionne exactement de la même manière que d'effectuer la même arithmétique sur les itérateurs correspondants.

Le but est de permettre des implémentations plus efficaces des algorithmes sur les itérateurs qui sont contigus. Ou d'interdire l'utilisation d'algorithmes sur des itérateurs qui ne sont pas contigus. Par exemple, si vous essayez de passer des itérateurs C++ dans une interface C basée sur des pointeurs vers des tableaux. Vous pouvez envelopper de telles interfaces derrière des algorithmes génériques, en vérifiant la contiguïté de l'itérateur dans le modèle.

Ou du moins, vous le pourriez en théorie ; en C++17, ce n'était pas vraiment possible La raison étant qu'il n'y avait pas vraiment de moyen de tester si un itérateur était un ContiguousIterator. Il n'y a aucun moyen de demander à un pointeur si faire de l'arithmétique de pointeur sur un pointeur vers un élément de l'itérateur est légal. Et il n'y avait pas std::contiguous_iterator_category que l'on pourrait utiliser pour de tels itérateurs (car cela pourrait causer des problèmes de compatibilité). Vous ne pouviez donc pas utiliser les outils SFINAE pour vérifier qu'un itérateur était contigu.

C++20 std::contiguous_iterator concept résout ce problème. Il résout également l'autre problème des itérateurs contigus. Vous voyez, l'explication ci-dessus du comportement de ContiguousIterator part du principe que nous avons un pointeur sur un élément de la plage. Mais comment l'obtenir ? La méthode évidente serait de faire quelque chose comme std::addressof(*it) mais que se passe-t-il si it est l'itérateur de fin ? L'itérateur de fin n'est pas déréférençable, donc vous ne pouvez pas le faire. En fait, même si vous savez qu'un itérateur est contigu, comment allez-vous le convertir en un pointeur équivalent ?

Le site std::contiguous_iterator résout ces deux problèmes. std::to_address est disponible, qui convertira tout itérateur contigu en sa valeur de pointeur équivalente. Et il existe une balise de traits qu'un itérateur doit fournir pour indiquer qu'il s'agit en fait d'un itérateur contigu, au cas où la balise par défaut to_address se trouve être valide pour un itérateur non contigu.

Answer 3

Un itérateur à accès aléatoire ne nécessite qu'un temps constant (iterator) + (offset) alors que les itérateurs contigus ont la garantie la plus forte que std::addressof(*((iterator) + (offset))) == std::addressof(*(iterator)) + (offset) (sans tenir compte des surcharges operator& s).

Cela signifie essentiellement que l'itérateur est un pointeur ou un emballage léger autour d'un pointeur, de sorte qu'il est équivalent à un pointeur sur ses éléments, alors qu'un itérateur à accès aléatoire peut faire plus, au prix d'être éventuellement plus volumineux et de ne pas pouvoir le transformer en un simple pointeur.

Answer 4

En tant que concept C++20, je pense que vous pouvez l'utiliser pour spécifier un algorithme différent si le conteneur est contigu. Peut-être en exploitant la localité du cache.