C++ std::vector::iterator n'est pas un pointeur, pourquoi?

Vous êtes tout à fait correct que vector::iterator peut être implémenté par un simple pointeur (voir ici) -- en fait, le concept d'itérateur est basée sur celle d'un pointeur vers un élément de tableau. Pour les autres conteneurs, tels que map,list, ou deque toutefois, un pointeur ne fonctionne pas à tous. Alors pourquoi ce n'est pas fait? Voici trois raisons pour lesquelles une implémentation de classe est préférable à un pointeur brut.

1. implémenter un itérateur comme type séparé permet des fonctionnalités supplémentaires (au-delà de ce qui est requis par la norme), par exemple (ajouté dans l'édition suivante Quentins commentaire) la possibilité d'ajouter des assertions quand déréférencement d'un itérateur, par exemple, en mode de débogage.

2. résolution de surcharge si l'itérateur est un pointeur T*, il peut être passé comme argument valable pour une fonction prenant T*, alors que ce ne serait pas possible avec un type d'itérateur. Et donc de faire de std::vector<>::iterator un pointeur change en fait le comportement du code existant. Considérons, par exemple,

   template<typename It>
   void foo(It begin, It end);
   void foo(const double*a, const double*b, size_t n=0);
   
   std::vector<double> vec;
   foo(vec.begin(), vec.end());    // which foo is called?
   

3. recherche dépendante de l'argument (ADL; pointed out by juanchopanza) si vous faites un appel non qualifié, ADL s'assure que les fonctions en namespace std ne sera recherché que si les arguments sont des types définis dans namespace std. Donc,

   std::vector<double> vec;
   sort(vec.begin(), vec.end());             // calls std::sort
   sort(vec.data(), vec.data()+vec.size());  // fails to compile
   

   std::sort n'est pas trouvé, si vector<>::iterator n'étaient qu'un pointeur.

la mise en oeuvre de l'itérateur est définition de la mise en oeuvre, à condition de satisfaire aux exigences de la norme. Il pourrait être un pointeur vector, ça marcherait. Il y a plusieurs raisons pour ne pas utiliser un pointeur;

• consistance avec d'autres récipients.
• debug vérification d'erreurs et de soutien
• résolution de la surcharge, les itérateurs basés sur la classe permettent des surcharges au travail en les différenciant de simples les pointeurs

si tous les itérateurs étaient des pointeurs, alors ++it sur un map ne l'incrémenterait pas à l'élément suivant puisque la mémoire n'a pas besoin d'être non-contiguë. Après le souvenir contigu de std:::vector la plupart des conteneurs standards nécessitent des pointeurs "plus intelligents" - donc des itérateurs.

les exigences physiques de l'itérateur s'adaptent très bien avec l'exigence logique que le mouvement entre les éléments est un "idiome" bien défini de l'itération sur eux, pas seulement en se déplaçant vers le prochain lieu de mémoire.

il s'agissait de l'une des exigences et des buts de la conception initiale du LTS; la relation orthogonale entre les conteneurs, les algorithmes et la connexion des deux à travers les itérateurs.

maintenant qu'il s'agit de classes, vous pouvez ajouter toute une série de vérifications d'erreurs et de contrôles de bon sens pour déboguer le code (et ensuite le supprimer pour optimiser le code de publication).

etant Donné le positif aspects les itérateurs basés sur la classe apportent, pourquoi devrait ou ne devrait pas vous utilisez simplement des pointeurs pour std::vector itérateurs - la cohérence. Implémentations de début std::vector a effectivement utilisé des pointeurs simples, vous pouvez les utiliser pour vector. Une fois que vous avez à utiliser des classes pour les autres itérateurs, compte tenu des positifs qu'ils apportent, en appliquant cela à vector devient une bonne idée.

parce que STL a été conçu avec l'idée que vous pouvez écrire quelque chose qui itère sur un itérateur, peu importe si cet itérateur est juste équivalent à un pointeur vers un élément de mémoire-tableaux contigus (comme std::array ou std::vector) ou quelque chose comme une liste chaînée, un jeu de clés, quelque chose qui est généré à la volée sur l'accès etc.

ne vous y trompez pas: dans le cas vectoriel, le déréférencement pourrait (sans options de débogage) se dégrader en une simple inlinable pointer dereference, donc il n'y aurait même pas de overhead après la compilation!

la raison d'être de l'utilisation d'un pointeur est moins de frais généraux, plus élevé performance, surtout si un compilateur d'optimisation détecte une itération et fait son truc (instructions vectorielles et autres). Utilisation d'itérateurs peut-être plus difficile pour le compilateur d'optimiser.

C'est le malentendu au cœur de la question. Une implémentation de classe bien formée n'aura pas de frais généraux, et des performances identiques, tout cela parce que le compilateur peut optimiser l'abstraction et traiter la classe iterator comme un pointeur dans le cas de std::vector.

cela dit,

MSVC++ 2013 ou libstdc++ dans Mingw 4.7, utilisez une classe spéciale pour vector les itérateurs

parce qu'ils considèrent que l'ajout d'une couche d'abstraction class iterator pour définir la notion d'itération sur un std::vector est plus bénéfique que d'utiliser un pointeur ordinaire à cette fin.

les Abstractions ont un ensemble différent de coûts par rapport aux avantages, typiquement plus de complexité de conception (pas nécessairement liée à la performance ou aux frais généraux) en échange de flexibilité, d'épreuves futures, de cacher des détails de mise en œuvre. Les compilateurs ci-dessus ont décidé que cette complexité supplémentaire est un coût approprié pour payer les avantages d'avoir une abstraction.

la raison d'être de l'utilisation d'un pointeur est moins de frais généraux, plus élevé performance, surtout si un compilateur d'optimisation détecte une itération et fait son truc (instructions vectorielles et autres). Utilisation d'itérateurs peut-être plus difficile pour le compilateur d'optimiser.

c'est peut-être le cas, mais ce n'est pas le cas. Si votre implémentation n'est pas totalement merdique, une structure enveloppant un pointeur atteindra la même vitesse.

avec cela à l'esprit, il est simple de voir que les avantages simples comme de meilleurs messages de diagnostic (nommant l'itérateur au lieu de T*), une meilleure résolution de surcharge, ADL, et la vérification de débogage font de la struct un gagnant clair sur le pointeur. Le pointeur brut a pas d'avantages.

j'ai contourné cet obstacle en déréférencant et en renvoyant immédiatement à l'itérateur. Ça a l'air ridicule, mais ça satisfait MSVC...

class Thing {
  . . .
};

void handleThing(Thing* thing) {
  // do stuff
}

vector<Thing> vec;
// put some elements into vec now

for (auto it = vec.begin(); it != vec.end(); ++it)
  // handleThing(it);   // this doesn't work, would have been elegant ..
  handleThing(&*it);    // this DOES work