Qu'est-ce qu'un bon moyen de * temporairement * trier un vecteur?

Question

J'ai un std :: vecteur que je dois trier par des algorithmes sélectionnés pour certaines opérations, mais pour maintenir son état d'origine (par exemple les articles commandés par quand ils ont été inscrits) le reste du temps.

Il est évident que je peux utiliser std :: copie pour créer un vecteur et genre, mais temporaire, je me demande s'il y a une meilleure façon, peut-être par les éléments horodater sont entrés.

Vive

Answer 1

Vous pouvez créer un std :: vecteur qui contient tous les indices du premier vecteur. Vous pouvez ensuite trier l'index vecteur que vous le souhaitez. Cela devrait être rapide et le plus important, ne signifie pas que vous avez de ne pas copier le premier vecteur (ce qui est probablement plus coûteux!).

Answer 2

Si cela ne vous dérange pas un peu de Boost vous pouvez utiliser la bibliothèque multiindice. Voir cette réponse de moi où vous trouverez quelques exemples de code.

En fait, il vous permet de garder plusieurs « vues » des mêmes données, chacune avec un ordre différent. Dans votre cas, vous serez en mesure de garder une vue « séquence », où les données sont en ordre d'insertion (comme un vecteur) et une vue « sorted » dans lequel les données sont triées en fonction de certains critères (comme une carte) .

Answer 3

Tout vecteur donné sera trié dans au plus une façon à tout moment.

Il existe deux alternatives:

Copier sur un vecteur temporaire et sorte que souhaité. À moins que le vecteur est très grand et vous avez un espace limité, ce qui est presque certainement la meilleure façon. Même si vous êtes préoccupé par la performance, le coût de faire une copie va être plus petit que le coût du tri, et si le coût de la copie est importante le tri va être beaucoup plus lent que la copie.

Sinon, vous pouvez garder une certaine façon (l'horodatage vous avez mentionné?) De pouvoir trier le vecteur de retour à l'ordre d'origine. Cela va être lent, puisque vous voulez que voulez faire si le vecteur était très grande, mais si vous ne pouvez pas faire un vecteur temporaire c'est la seule façon de le faire.

Answer 4

Quel que soit le produit que vous triez, vous pouvez l'envelopper dans une structure qui a de multiples champs de tri.

struct someThing
{
    int sortOrder1;
    int sortOrder2;
    ...
    int sortOrderN;
    //payload data object here
} //note: this code may have some sytax errors (I haven't actually tried compiling this ;), but hope the idea is clear

(ou peut-être ajouter les ordres de tri à la structure de base elle-même?)

Ensuite, lorsque vous avez besoin peut calculer les différents ordres de tri, et réordonner votre liste en fonction du type d'ordre dont vous avez besoin.

Answer 5

Je suggère stocker des pointeurs intelligents, les données d'origine, dans chaque vector. std::vector vous permet de fournir différentes méthodes de tri. De plus, avec des pointeurs intelligents, ils seront détruits automatiquement lorsque toutes les références à l'élément sont supprimés.