Conteneurs STL triés dynamiquement

Question

Comme je suis assez nouveau dans la STL, je me demandais s’il existait des conteneurs triables de manière dynamique? Pour le moment, je pense actuellement à utiliser un vecteur en conjonction avec les divers algorithmes de tri, mais je ne suis pas sûr s'il existe une sélection plus appropriée compte tenu de la complexité (supposée) linéaire de l'insertion d'entrées dans un vecteur trié.

Pour clarifier & "dynamiquement &", je recherche un conteneur que je puisse modifier l’ordre de tri au moment de l’exécution - par exemple. triez-les dans un ordre croissant, puis triez-les ultérieurement dans un ordre décroissant.

Answer 1

Si vous savez que vous allez trier une seule valeur par ordre croissant ou décroissant, votre ami est défini. Utilisez un itérateur inversé lorsque vous souhaitez & "Trier &"; dans le sens opposé.

Si vos objets sont complexes et que vous allez effectuer un tri de différentes manières en fonction des champs de membre dans les objets, il est probablement préférable d'utiliser un vecteur et un tri. Essayez de faire vos insertions en même temps, puis appelez une fois tri. Si cela n’est pas faisable, alors deque peut être une meilleure option que le vecteur pour les grandes collections d’objets.

Je pense que si vous êtes intéressé par ce niveau d'optimisation, vous feriez mieux de profiler votre code à l'aide de données réelles. (Quel est probablement le meilleur conseil que quiconque puisse donner ici: peu importe que vous appeliez une sorte après chaque insertion si vous ne le faites qu'une fois dans une lune bleue.)

Answer 2

Vous voudrez regarder std :: map

std::map<keyType, valueType>

La carte est triée sur la < opérateur fourni pour keyType.

Ou

std::set<valueType>

Également trié sur le < opérateur de l'argument de modèle, mais n'autorise pas les éléments en double.

Il y a

std::multiset<valueType>

qui fait la même chose que std :: set mais autorise des éléments identiques.

Je recommande vivement & "La bibliothèque standard C ++ &"; par Josuttis pour plus d'informations. C’est l’aperçu le plus complet de la bibliothèque std, très lisible et riche en informations obscures et pas si obscures.

En outre, comme mentionné par 17 des 26 participants, Effective Stl de Meyers mérite une lecture.

Answer 3

Il semble que vous souhaitiez un multi-index conteneur . Cela vous permet de créer un conteneur et d'indiquer à celui-ci les différentes manières de parcourir les éléments qu'il contient. Le conteneur conserve ensuite plusieurs listes d'éléments, qui sont mises à jour à chaque insertion / suppression.

Si vous souhaitez vraiment re-trier le conteneur, vous pouvez appeler le std :: sort sur n'importe quel std :: deque , std :: vector , ou même un simple tableau de style C. Cette fonction utilise un troisième argument facultatif pour déterminer comment trier le contenu.

Answer 4

Le stl ne fournit aucun conteneur de ce type. Vous pouvez définir le vôtre, avec soit un set / multiset , soit un vector , mais vous allez devoir trier à chaque fois que la fonction de tri change en appelant sort (pour un vecteur ) ou en créant une nouvelle collection (pour set / multiset ).

Si vous souhaitez simplement passer d'un ordre de tri croissant à un ordre de tri décroissant, vous pouvez utiliser l'itérateur inverse de votre conteneur en appelant rbegin () et rend () . au lieu de begin () et end () . Le vecteur et le set / multiset sont des conteneurs réversibles, donc cela fonctionnerait pour l'un ou l'autre.

Answer 5

std :: set est fondamentalement un conteneur trié.

Answer 6

Vous devez absolument utiliser un ensemble / une carte. Comme dit hazzen, vous obtenez O (log n) insert / find. Vous ne l'obtiendrez pas avec un vecteur trié; vous pouvez obtenir O (log n) find en utilisant la recherche binaire, mais l'insertion est O (n) car l'insertion (ou la suppression) d'un élément peut entraîner le déplacement de tous les éléments existants dans le vecteur.

Answer 7

Ce n'est pas si simple. Dans mon expérience, insérer / supprimer est utilisé moins souvent que trouver. L'avantage du vecteur trié est qu'il nécessite moins de mémoire et qu'il est plus convivial pour le cache. Si vous possédez une version compatible avec les cartes STL (comme celle que j'ai déjà liée), il est facile de changer de version et d'utiliser un conteneur optimal pour chaque situation.

Answer 8

En théorie, un conteneur associatif (ensemble, multiset, carte, carte multiple) devrait être votre meilleure solution.

En pratique, cela dépend du nombre moyen d'éléments que vous insérez. pour moins de 100 éléments, un vecteur est probablement la meilleure solution pour les raisons suivantes: - éviter l'allocation-désallocation continue - cache amical en raison de la localisation des données ces avantages seront probablement supérieurs au tri continu. Évidemment, cela dépend aussi du nombre d'insertion-suppression que vous devez faire. Allez-vous effectuer une insertion / une interprétation par image?

Plus généralement: parlez-vous d'une application critique en termes de performances?

rappelez-vous de ne pas optimiser prématurément ...

Answer 9

La réponse est, comme toujours, ça dépend.

set et multiset permettent de conserver les éléments triés, mais sont généralement optimisés pour un ensemble équilibré d'ajouts, de suppressions et de récupérations. Si vous avez des opérations de recherche viriles, un vecteur trié peut être plus approprié, puis utilisez lower_bound pour rechercher l'élément.

De plus, votre deuxième exigence de recourir à un ordre différent au moment de l'exécution signifiera en réalité que set et multiset ne sont pas appropriés car le prédicat ne peut pas être modifié en même temps. / p>

Je recommanderais donc un vecteur trié. Mais n'oubliez pas de transmettre le même prédicat à lower_bound que vous avez transmis au tri précédent, car les résultats seront indéfinis et très probablement incorrects si vous transmettez le prédicat incorrect.

Answer 10

Set et multiset utilisent un arbre binaire sous-jacent; vous pouvez définir l'opérateur < = pour votre propre usage. Ces conteneurs restent eux-mêmes triés. Par conséquent, ils ne constituent peut-être pas le meilleur choix si vous modifiez les paramètres de tri. Les vecteurs et les listes sont probablement les meilleurs si vous envisagez de recourir à de nombreuses ressources; en général, la liste a son propre tri (généralement un mergesort) et vous pouvez utiliser l'algorithme de recherche binaire stl sur des vecteurs. Si les inserts dominent, la liste surperforme le vecteur.

Answer 11

Les

cartes et ensembles STL sont tous deux des conteneurs triés.

J'appuie la recommandation du livre de Doug T: le livre Josuttis STL est le meilleur livre que j'ai jamais vu comme livre d'apprentissage et de référence.

Effective STL est également un excellent livre pour apprendre les détails intérieurs de STL et ce que vous devriez et ne devriez pas faire.

Answer 12

Pour "Compatible STL" vecteur trié, voir AssocVector de A. Alexandrescu à partir de Loki .