Différence entre insert et push_back d'un vecteur C++

Question

Je voudrais savoir quelle(s) différence(s) il y a entre vector 's push_back y insert fonctions.

Existe-t-il une ou des différences structurelles ?

Y a-t-il une ou des différences de performances vraiment importantes ?

Answer 1

La principale différence réside dans leur fonctionnalité. push_back place toujours un nouvel élément à la fin du fichier vector y insert permet de sélectionner la position d'un nouvel élément. Cela a un impact sur les performances. vector Les éléments sont déplacés dans la mémoire uniquement lorsqu'il est nécessaire d'augmenter leur longueur parce que la mémoire qui leur a été allouée est insuffisante. D'autre part, les insert permet de déplacer tous les éléments après la position sélectionnée d'un nouvel élément. Il suffit de lui faire une place. C'est pourquoi insert peuvent souvent être moins efficaces que les push_back .

Answer 2

Les fonctions ont des objectifs différents. vector::insert vous permet d'insérer un objet à une position spécifiée dans le fichier vector considérant que vector::push_back collera simplement l'objet à l'extrémité. Voir l'exemple suivant :

using namespace std;
vector<int> v = {1, 3, 4};
v.insert(next(begin(v)), 2);
v.push_back(5);
// v now contains {1, 2, 3, 4, 5}

Vous pouvez utiliser insert pour effectuer le même travail que push_back con v.insert(v.end(), value) .

Answer 3

Outre le fait que push_back(x) fait la même chose que insert(x, end()) (peut-être avec des performances légèrement supérieures), il y a plusieurs choses importantes à savoir à propos de ces fonctions :

1. push_back n'existe que sur BackInsertionSequence donc, par exemple, il n'existe pas sur les conteneurs set . Il n'a pas pu le faire parce que push_back() vous assure qu'il s'ajoutera toujours à la fin.
2. Certains conteneurs peuvent également satisfaire FrontInsertionSequence et ils ont push_front . Cette condition est satisfaite par deque mais pas par vector .
3. En insert(x, ITERATOR) provient de InsertionSequence , ce qui est courant pour les set y vector . De cette façon, vous pouvez utiliser soit set o vector comme cible d'insertions multiples. Cependant, set a en outre insert(x) qui fait pratiquement la même chose (cette première insertion en set permet uniquement d'accélérer la recherche de l'emplacement approprié en commençant par un itérateur différent - une fonctionnalité qui n'est pas utilisée dans ce cas).

Notez que dans le dernier cas, si vous ajoutez des éléments dans la boucle, l'opération container.push_back(x) y container.insert(x, container.end()) fera effectivement la même chose. Toutefois, ce ne sera pas le cas si vous obtenez ceci container.end() d'abord et l'utiliser ensuite dans toute la boucle.

Par exemple, vous pouvez risque le code suivant :

auto pe = v.end();
for (auto& s: a)
    v.insert(pe, v);

Cette opération permet de copier l'ensemble des a en v vecteur, dans l'ordre inverse et seulement si vous avez la chance que le vecteur ne soit pas réalloué pour l'extension (vous pouvez éviter cela en appelant reserve() premier) ; si vous n'avez pas cette chance, vous obtiendrez ce que l'on appelle UndefinedBehavior(tm) (comportement non défini). Théoriquement, cela n'est pas autorisé car les itérateurs de vecteurs sont considérés comme invalidés à chaque fois qu'un nouvel élément est ajouté.

Si vous procédez de cette manière :

copy(a.begin(), a.end(), back_inserter(v);

il copiera a à la fin de v dans l'ordre initial, sans risque d'invalidation de l'itérateur.

[EDIT] J'ai précédemment fait en sorte que ce code ait cette apparence, et c'était une erreur parce que inserter maintient en fait la validité et l'avancement de l'itérateur :

copy(a.begin(), a.end(), inserter(v, v.end());

Ce code ajoutera donc également tous les éléments dans l'ordre initial, sans aucun risque.

Answer 4

Je ne l'ai pas vu dans les commentaires ci-dessus, mais il est important de le savoir :

Si nous souhaitons ajouter un nouvel élément à un vecteur donné et que la nouvelle taille du vecteur (y compris le nouvel élément) dépasse la capacité actuelle du vecteur, cela entraînera une réaffectation automatique de l'espace de stockage alloué. Et comme l'allocation de mémoire est une action que nous souhaitons minimiser, elle augmentera la capacité du vecteur. à la fois en push_back et en insert de la même manière (pour un vecteur à n éléments, on ajoutera environ n/2).

En termes d'efficacité de la mémoire, on peut donc dire sans risque de se tromper qu'il faut utiliser ce que l'on préfère. par exemple :

std::vector<int> test_Insert = { 1,2,3,4,5,6,7 };
std::vector<int> test_Push_Back = { 1,2,3,4,5,6,7 };

std::cout << test_Insert.capacity() << std::endl;
std::cout << test_Push_Back.capacity() << std::endl;

test_Insert.push_back(8);
test_Push_Back.insert(test_Push_Back.end(), 8);

std::cout << test_Insert.capacity() << std::endl;
std::cout << test_Push_Back.capacity() << std::endl;

Ce code s'imprimera :

7

7

10

10