Quelle est la différence entre std::set et std::vector ?

Question

Je suis en train d'apprendre le STL. J'ai lu à propos de set contenant. J'ai une question concernant l'utilisation de set ? Après avoir lu description de l'ensemble il semble qu'il soit inutile car nous pouvons le remplacer par vector . Pourriez-vous nous dire quels sont les avantages et les inconvénients de vector vs set des conteneurs. Remerciements

Answer 1

A set est ordonné. Il est garantie de rester dans un ordre spécifique, selon un foncteur que vous fournissez. Quels que soient les éléments que vous ajoutez ou supprimez (à moins que vous n'ajoutiez un doublon, ce qui n'est pas autorisé dans une classe de set ), il sera toujours commandé.

A vector a exactement et seulement l'ordre que vous lui donnez explicitement. Les éléments d'un vector sont là où vous les avez mis. Si vous les avez mis dans le désordre, alors ils sont dans le désordre ; vous devez maintenant sort le conteneur pour les remettre en ordre.

Il faut l'admettre, set a une utilisation relativement limitée. Avec une discipline appropriée, il est possible d'insérer des éléments dans une vector et le maintenir en ordre. Cependant, si vous insérez et retirez constamment des éléments du conteneur, vous risquez de vous retrouver dans une situation très difficile, vector se heurtera à de nombreux problèmes. Il y aura beaucoup de copies/déplacements d'éléments et ainsi de suite, puisqu'il s'agit en fait d'un simple tableau.

Le temps nécessaire à l'insertion d'un élément dans un vector est proportionnel au nombre d'éléments déjà présents dans la base de données. vector . Le temps nécessaire à l'insertion d'un élément dans une set est proportionnelle à la log₂ du nombre d'éléments. Si le nombre d'éléments est élevé, la différence est énorme. log₂(100 000) est ~16 ; c'est une amélioration majeure de la vitesse. Il en va de même pour la suppression.

Cependant, si vous effectuez toutes vos insertions en une seule fois, au moment de l'initialisation, il n'y a pas de problème. Vous pouvez tout insérer dans le fichier vector , la trier (en payant ce prix une fois), puis utiliser des algorithmes standard pour les données triées. vectors pour trouver des éléments et itérer sur la liste triée. Et tandis que l'itération sur les éléments d'une set n'est pas vraiment lent, l'itération sur un fichier vector est plus rapide.

Il y a donc des cas où un vector bat un set . Ceci étant dit, vous ne devriez pas vous soucier des dépenses liées à ce type d'optimisation à moins que vous ne sachiez que c'est nécessaire. Utilisez donc un set à moins que vous n'ayez l'expérience du type de système que vous écrivez (et donc que vous sachiez que vous avez besoin de cette performance) ou que vous ayez des données de profilage en main qui vous indiquent que vous avez besoin d'un vector et non un set .

Answer 2

Il s'agit de deux choses différentes : c'est vous qui décidez de l'ordre des vecteurs et vous pouvez mettre autant de choses égales que vous le souhaitez dans un vecteur. Les ensembles sont ordonnés conformément aux règles internes de l'ensemble (vous pouvez définir les règles, mais l'ensemble s'occupe de l'ordre), et vous ne pouvez pas mettre plusieurs éléments égaux dans un ensemble.

Bien sûr, vous pouvez maintenir un vecteur d'éléments uniques, mais vos performances en pâtiront considérablement lorsque vous effectuerez des opérations orientées vers un ensemble. Par exemple, supposons que vous disposiez d'un ensemble de 10000 éléments et d'un vecteur de 10000 éléments distincts non ordonnés. Supposons maintenant que vous deviez vérifier si une valeur X fait partie des valeurs de l'ensemble (ou des valeurs du vecteur). Lorsque X ne figure pas parmi les éléments, la recherche dans le vecteur est 100 fois plus lente. Vous constaterez des différences de performances similaires dans le calcul des unions et des intersections d'ensembles.

En résumé, les ensembles et les vecteurs ont des objectifs différents. Il est possible d'utiliser un vecteur au lieu d'un ensemble, mais cela nécessiterait plus de travail et nuirait probablement aux performances.

Answer 3

Formulaire cpluplus.com set :

Les ensembles sont des conteneurs qui stockent des éléments uniques suivant un modèle spécifique. spécifique.

l'ensemble est ordonné ET les éléments sont représentés de manière unique

alors que vect :

Les vecteurs sont des conteneurs de séquences représentant des tableaux qui peuvent changer en taille.

le vecteur est donc dans l'ordre dans lequel vous le remplissez ET peut contenir plusieurs articles identiques

préférer l'ensemble :

• si vous souhaitez filtrer plusieurs valeurs identiques
• si vous souhaitez analyser les éléments dans un ordre précis (pour ce faire dans un vecteur, il faut trier spécifiquement le vecteur).

préférer le vecteur :

• si vous souhaitez conserver des valeurs identiques
• si vous souhaitez analyser les éléments dans le même ordre que vous les avez poussés (en supposant que vous ne traitiez pas l'ordre vectoriel)

Answer 4

La simple différence est que le set ne peut contenir que des valeurs uniques et qu'il est trié. Vous pouvez donc l'utiliser dans les cas où vous avez besoin de trier continuellement les valeurs après chaque insertion/suppression.

set<int> a;
vector<int> b;
for (int i = 0; i < 10; ++i)
{
    int val = rand() % 10;
    a.insert(val);
    b.push_back(val);
}
cout << "--SET---\n"; for (auto i : a) cout << i << ","; cout << endl;
cout << "--VEC---\n"; for (auto j : b) cout << j << ","; cout << endl;

Le résultat est le suivant

--SET---
0,1,2,4,7,8,9,
--VEC---
1,7,4,0,9,4,8,8,2,4,

Answer 5

Il est plus rapide de rechercher un élément dans un ensemble que dans un vecteur (O(log(n)) contre O(n)). Pour rechercher un élément dans un vecteur, il faut itérer tous les éléments du vecteur, mais l'ensemble utilise l'arbre rouge-noir pour optimiser la recherche, seuls quelques éléments seront recherchés pour trouver une correspondance.

L'ensemble est ordonné, ce qui signifie que vous ne pouvez l'itérer que du plus petit au plus grand par ordre, ou dans l'ordre inverse.

Mais le vecteur n'est pas ordonné, vous pouvez le parcourir par l'ordre d'insertion.