Comment l'insert multimap de la stl respecte-t-il les commandes?

Question

J'ai quelques données qui viennent avec un index entier. Je génère continuellement de nouvelles données qui doivent être ajoutées à la collection de données que j'ai, triées par cet index, en même temps je veux facilement pouvoir aller au début des données et les parcourir. Cela ressemble à std :: multimap est juste ce dont j'ai besoin.

Cependant, j'ai également besoin de conserver les données avec le même index dans l'ordre dans lequel elles ont été insérées, ce qui signifie que lorsque je parcourt les données, j'arrive aux données antérieures aux données ultérieures.

Est-ce que multimap fait cela?

Je n'ai trouvé aucune garantie que c'est le cas. Dans le manuel sgi, je n'ai pas vu de mention de si. Je l'ai essayé sur l'implémentation de gcc 4.3.4 et cela semblait être le cas pour certains cas de tests limités, mais bien sûr je me demandais si la norme l'exige et je peux m'en fier. Pour être plus clair en réponse à certaines des réponses, je voulais que les données soient triées d'abord par l'index (non unique) et ensuite par le temps d'insertion. J'avais espéré que la deuxième partie viendrait peut-être gratuitement avec multimap, mais il semble que ce ne soit pas le cas.

Answer 1

À moins d'avoir manqué quelque chose, la norme n'offre aucune garantie de ce genre.

La solution de contournement la plus évidente consisterait à inclure un numéro de séquence en tant que clé secondaire. Par exemple, dans votre classe, incluez une longueur statique non signée, et chaque fois que vous créez un objet à insérer dans le multimap, placez sa valeur actuelle dans votre objet et incrémentez-la. Dans la fonction de comparaison de votre objet, utilisez ce compteur comme facteur décisif pour la commande si les données que vous utilisez actuellement en tant que clé se comparent égales. Notez que dans ce cas, chaque clé sera unique, de sorte que vous pouvez utiliser une carte au lieu d'un multimap.

Answer 2

Non ce n'est pas le cas. Si vous voulez cela, vous devriez utiliser un "conteneur de séquence" comme un vecteur. Vous pouvez charger un vecteur avec des paires std :: par exemple?

Answer 3

On dirait que multimap est ce que vous avez besoin ...

Cependant, j'ai besoin aussi des données avec le même indice à conserver dans l'ordre dans lequel il a été inséré, dans ce cas sens que lorsque je parcourt les données que j'obtiens aux données antérieures avant les données ultérieures.

Ce sera dans l'ordre de l'index. Si l'index augmente au fur et à mesure que vous insérez plus d'éléments, alors oui en raison de la nature de votre index, les données "antérieures" viendront en premier.

Sinon, non. Vous pouvez conserver deux multimaps sur les mêmes données. Un gardé pour l'indice, l'autre dans l'ordre du temps d'insertion:

std::multimap<index, T*> orderedByIndex; 
std::multimap<time, T*> orderedByInsertionTime; 

vous donnant la possibilité de parcourir la carte dans les deux sens. Je lis ceci pour signifier que vous voulez parfois itérer par index ou parfois itérer par temps d'insertion, mais voir la réponse ci-dessus si vous voulez dire premier index puis temps d'insertion.)

Answer 4

Les éléments appartenant à la même clé est ordened par lower_bound et upper_bound fonctions lorsque vous récupérez les informations, donc vous n'avez pas la garantie que vous aurez accès (par equal_range) les éléments dans l'ordre qu'ils étaient inséré.

Answer 5

Boost multi_index prend en charge ce que vous essayez de faire, si vous ne voulez pas prendre la solution de contournement donnée par Jerry Coffin.

Answer 6

Si je vous ai bien compris, vous devez trier les données à l'aide d'une clé. Chaque fois que vous insérez 2 choses avec la même clé, vous devez les récupérer dans l'ordre d'insertion.

Si c'est le cas, alors vous devez jeter un oeil à la mise en œuvre de votre multimap. Selon la façon dont il gère le cas de plusieurs insertions avec la même clé, il peut ou non avoir cette garantie. Je suppose que la norme n'offre pas ce genre de garantie, car cela limiterait la mise en œuvre pour un cas très particulier.

Une autre approche est d'opter pour une carte (non multi) et de créer un composé clé. La clé se compose de la clé normale que vous choisissez et d'un compteur toujours croissant. En comparaison, avec des clés égales, le numéro d'insertion rend la clé unique. De cette façon, vous forcez les clés uniques et l'ordre sur des touches "normales" égales (j'espère que c'était compréhensible). Je suppose que la dernière approche est la plus facile à implémenter.

---

Option: (pas préférable)

Vous pouvez toujours opter pour une structure de données self-made avec cette garantie. Je choisirais un arbre (Red-Black ou AVL par exemple) avec un vecteur pour contenir les données insérées. Sur l'itération, vous devez trouver le nœud, aller au vecteur et parcourir son contenu. Chaque fois que vous avez terminé avec le vecteur, vous continuez avec le noeud suivant.

Answer 7

Il semble que la nouvelle norme (C++ 11) a changé ceci:

L'ordre des paires clé-valeur dont les clés comparer équivalente est de l'ordre d'insertion et ne change pas. ^{[cppreference]}

Je hésite à l'utiliser si, comme cela semble être un détail facilement passer inaperçue lors de la modification de la bibliothèque standard C++ pour être 11 compatible et il est le genre de détail qui silencieusement provoquer des erreurs si La bibliothèque de votre compilateur n'a pas pu être implémentée correctement.