Un std::map que de garder une trace de l'ordre d'insertion?

Question

J'ai actuellement un std::map<std::string,int> qui stocke une valeur de nombre entier à un unique identificateur de chaîne, et je ne regarde jusqu'à la corde. Il n'est surtout ce que je veux, sauf qu'il ne garde pas la trace de l'ordre d'insertion. Alors, quand je itérer la carte à imprimer les valeurs, ils sont triés en fonction de la chaîne; mais je veux qu'ils soient triés selon l'ordre de la (première) d'insertion.

J'ai pensé à utiliser un vector<pair<string,int>> à la place, mais j'ai besoin de regarder pour la chaîne et incrémenter les valeurs entières sur les 10 000 000 de fois, donc je ne sais pas si un vecteur va être beaucoup plus lent.

Est-il possible d'utiliser std::map ou il y a une autre mst récipient qui convient le mieux à mon besoin?

[Je suis sur GCC 3.4, et j'ai probablement pas plus de 50 paires de valeurs dans mon std::map].

Answer 1

Si vous avez seulement 50 valeurs dans std::map vous pourriez les copier sur std::vector avant de les imprimer et de les trier via std::sort utilisation appropriée du foncteur.

Ou vous pourriez utiliser boost::multi_index. Il permet d'utiliser plusieurs indices. Dans votre cas, il pourrait ressembler à ce qui suit:

struct value_t {
      string s;
      int    i;
};
struct string_tag {};
typedef multi_index_container<
    value_t,
    indexed_by<
    	random_access<>, // this index represents insertion order
    	hashed_unique< tag<string_tag>, member<value_t, string, &value_t::s> >
    >
> values_t;

Answer 2

Vous pouvez combiner std::vector avec un std::tr1::unordered_map (une table de hachage). Voici un lien pour Stimuler la documentation pour unordered_map. Vous pouvez utiliser le vecteur de garder une trace de l'ordre d'insertion et de la table de hachage à faire de fréquentes recherches. Si vous êtes en train de faire des centaines de milliers de recherches, la différence entre O(log n) recherche pour std::map et O(1) pour une table de hachage peut être significatif.

std::vector<std::string> insertOrder;
std::tr1::unordered_map<std::string, long> myTable;

// Initialize the hash table and record insert order.
myTable["foo"] = 0;
insertOrder.push_back("foo");
myTable["bar"] = 0;
insertOrder.push_back("bar");
myTable["baz"] = 0;
insertOrder.push_back("baz");

/* Increment things in myTable 100000 times */

// Print the final results.
for (int i = 0; i < insertOrder.size(); ++i)
{
    const std::string &s = insertOrder[i];
    std::cout << s << ' ' << myTable[s] << '\n';
}

Answer 3

Garder un parallèle list<string> insertionOrder.

Quand il est temps d'imprimer, d'itérer sur la liste et faire des recherches dans la carte.

each element in insertionOrder  // walks in insertionOrder..
    print map[ element ].second // but lookup is in map

Answer 4

Si vous avez besoin de stratégies de recherche, vous allez vous retrouver avec deux récipients. Vous pouvez utiliser un vector avec vos valeurs réelles (ints), et de mettre un map< string, vector< T >::difference_type> à côté de lui, retourner l'index dans le vecteur.

Pour compléter le tout, vous pouvez encapsuler les deux dans une même classe.

Mais je crois boost a un récipient avec de multiples indices.

Answer 5

Vous ne pouvez pas faire avec une carte, mais vous pouvez utiliser deux structures distinctes - la carte et le vecteur et de les garder synchronisés - c'est quand vous supprimez de la carte, trouver et supprimer l'élément du vecteur. Ou vous pouvez créer un map<string, pair<int,int>> - et dans votre paire de stocker la taille() de la carte lors de l'insertion à la position de l'enregistrement, ainsi que la valeur de l'int, puis lors de l'impression, utiliser la position de membre de tri.