Insertion dans un vecteur à l’avant

iterator insert ( iterator position, const T& x );

Déclaration de fonction de l’opérateur d’insertion de la classe std::Vector .

Le type de retour de cette fonction est un iterator pointant sur l’élément inséré. Ma question est, étant donné ce type de retour, quel est le moyen le plus efficace (cela fait partie d’un programme plus vaste que je lance où la vitesse est essentielle, je recherche donc le moyen le plus efficace en termes de calcul) d’insertion au début. Est-ce le suivant?

 //Code 1 vector intvector; vector::iterator it; it = myvector.begin(); for(int i = 1; i <= 100000; i++){ it = intvector.insert(it,i); }

Ou,

 //Code 2 vector intvector; for(int i = 1; i <= 100000; i++){ intvector.insert(intvector.begin(),i); }

Essentiellement, dans le code 2, est le paramètre,

 intvector.begin()

“Coûteux” à évaluer informatiquement par rapport à l’utilisation de l’iterator retourné dans le code 1 ou les deux devraient-ils être tout aussi économiques / coûteux?

L’efficacité d’obtenir le point d’insertion n’a aucune importance, elle sera éclipsée par l’inefficacité de la réorganisation en continu des données existantes à chaque insertion.

Utilisez std :: deque pour cela, c’est pour cela qu’il a été conçu.

Si l’un des besoins critiques de votre programme consiste à insérer des éléments au début d’un conteneur : vous devez alors utiliser un std::deque et non un std::vector . std::vector est seulement bon pour insérer des éléments à la fin.

Diagramme STL pour le choix des conteneurs

D’autres conteneurs ont été introduits en C ++ 11. Je devrais commencer à trouver un graphique mis à jour avec ces nouveaux conteneurs et à l’insérer ici.

Un vieux fil, mais il est apparu au bureau d’un collègue comme premier résultat de recherche pour une requête Google.

Il existe une alternative à l’utilisation d’un deque qui mérite d’être envisagée:

 std::vector foo; for (int i = 0; i < 100000; ++i) foo.push_back(T()); std::reverse( foo.begin(), foo.end() );

Vous utilisez toujours un vecteur nettement plus élaboré que deque pour la performance. En outre, les échanges (qui est ce qui utilise inverse) sont très efficaces. En revanche, la complexité, bien que toujours linéaire, est augmentée de 50%.

Comme toujours, mesurez avant de décider quoi faire.

deque est probablement la solution appropriée suggérée par d’autres. Mais pour que tout soit complet, supposons que vous deviez effectuer cette insertion frontale une seule fois, qu’ailleurs dans le programme, vous n’ayez pas besoin d’effectuer d’autres opérations sur le front, et que sinon, vector fournira l’interface dont vous avez besoin. Si tout cela est vrai, vous pouvez append les éléments avec le très efficace push_back , puis reverse le vecteur pour tout mettre en ordre. Cela aurait une complexité linéaire plutôt que polynomiale comme ce serait le cas lors de l’insertion à l’avant.

Si vous recherchez une méthode d’insertion efficace au premier plan sur le plan informatique, vous voudrez probablement utiliser un deque au lieu d’un vecteur.

Lorsque vous utilisez un vecteur, vous connaissez généralement le nombre réel d’éléments qu’il aura. Dans ce cas, réserver le nombre requirejs d’éléments (100 000 dans le cas que vous indiquez) et les remplir à l’aide de l’opérateur [] est le moyen le plus rapide. Si vous avez vraiment besoin d’un insert efficace à l’avant, vous pouvez utiliser deque ou list , en fonction de vos algorithmes.

Vous pouvez également envisager d’inverser la logique de votre algorithme et de l’insérer à la fin, ce qui est généralement plus rapide pour les vecteurs.

Je pense que vous devriez changer le type de votre conteneur si vous voulez vraiment insérer des données au début. C’est la raison pour laquelle le vecteur n’a pas de fonction membre push_front ().