Un std :: map qui garde une trace de l'ordre d'insertion?

J'ai actuellement un std::map<std::string,int>qui stocke une valeur entière dans un identifiant de chaîne unique, et je recherche la chaîne. Il fait principalement ce que je veux, sauf que cela ne suit pas l'ordre d'insertion. Ainsi, lorsque j'itère la carte pour imprimer les valeurs, elles sont triées en fonction de la chaîne; mais je veux qu'ils soient triés selon l'ordre de (première) insertion.

J'ai pensé à utiliser a à la vector<pair<string,int>>place, mais je dois rechercher la chaîne et incrémenter les valeurs entières environ 10 000 000 fois, donc je ne sais pas si a std::vectorsera beaucoup plus lent.

Y a-t-il un moyen d'utiliser std::mapou y a-t-il un autre stdcontenant qui répond mieux à mes besoins?

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

Merci.

Si vous n'avez que 50 valeurs dans std :: map, vous pouvez les copier dans std :: vector avant de les imprimer et les trier via std :: sort en utilisant le foncteur approprié.

Ou vous pouvez utiliser boost :: multi_index . Il permet d'utiliser plusieurs index. Dans votre cas, cela pourrait ressembler à ceci:

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;

Vous pouvez combiner a std::vectoravec une std::tr1::unordered_map(une table de hachage). Voici un lien vers la documentation de Boost pour unordered_map. Vous pouvez utiliser le vecteur pour suivre l'ordre d'insertion et la table de hachage pour effectuer les recherches fréquentes. Si vous effectuez des centaines de milliers de recherches, la différence entre la recherche O (log n) std::mapet O (1) pour une table de hachage peut être significative.

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';
}

Gardez un parallèle list<string> insertionOrder.

Lorsqu'il est temps d'imprimer, parcourez la liste et effectuez des recherches dans la carte .

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

Tessil a une très belle implémentation de la carte ordonnée (et de l'ensemble) qui est une licence MIT. Vous pouvez le trouver ici: plan-ordonné

Exemple de carte

#include <iostream>
#include <string>
#include <cstdlib>
#include "ordered_map.h"

int main() {
tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}};
map.insert({'b', 4});
map['h'] = 5;
map['e'] = 6;

map.erase('a');


// {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}


map.unordered_erase('b');

// Break order: {d, 1} {g, 3} {e, 6} {h, 5}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
}

Si vous avez besoin des deux stratégies de recherche, vous vous retrouverez avec deux conteneurs. Vous pouvez utiliser a vectoravec vos valeurs réelles int, et mettre un à map< string, vector< T >::difference_type> côté, renvoyant l'index dans le vecteur.

Pour compléter tout cela, vous pouvez encapsuler les deux dans une seule classe.

Mais je crois que boost a un conteneur avec plusieurs indices.

Ce que vous voulez (sans recourir à Boost), c'est ce que j'appelle un "hash ordonné", qui est essentiellement un mashup d'un hachage et d'une liste chaînée avec des clés de chaîne ou de nombre entier (ou les deux en même temps). Un hachage ordonné maintient l'ordre des éléments lors de l'itération avec la performance absolue d'un hachage.

J'ai mis en place une bibliothèque d'extraits de code C ++ relativement nouvelle qui remplit ce que je considère comme des trous dans le langage C ++ pour les développeurs de bibliothèques C ++. Va ici:

https://github.com/cubiclesoft/cross-platform-cpp

Saisir:

templates/detachable_ordered_hash.cpp
templates/detachable_ordered_hash.h
templates/detachable_ordered_hash_util.h

Si les données contrôlées par l'utilisateur sont placées dans le hachage, vous pouvez également souhaiter:

security/security_csprng.cpp
security/security_csprng.h

Invoquez-le:

#include "templates/detachable_ordered_hash.h"
...
// The 47 is the nearest prime to a power of two
// that is close to your data size.
//
// If your brain hurts, just use the lookup table
// in 'detachable_ordered_hash.cpp'.
//
// If you don't care about some minimal memory thrashing,
// just use a value of 3.  It'll auto-resize itself.
int y;
CubicleSoft::OrderedHash<int> TempHash(47);
// If you need a secure hash (many hashes are vulnerable
// to DoS attacks), pass in two randomly selected 64-bit
// integer keys.  Construct with CSPRNG.
// CubicleSoft::OrderedHash<int> TempHash(47, Key1, Key2);
CubicleSoft::OrderedHashNode<int> *Node;
...
// Push() for string keys takes a pointer to the string,
// its length, and the value to store.  The new node is
// pushed onto the end of the linked list and wherever it
// goes in the hash.
y = 80;
TempHash.Push("key1", 5, y++);
TempHash.Push("key22", 6, y++);
TempHash.Push("key3", 5, y++);
// Adding an integer key into the same hash just for kicks.
TempHash.Push(12345, y++);
...
// Finding a node and modifying its value.
Node = TempHash.Find("key1", 5);
Node->Value = y++;
...
Node = TempHash.FirstList();
while (Node != NULL)
{
  if (Node->GetStrKey())  printf("%s => %d\n", Node->GetStrKey(), Node->Value);
  else  printf("%d => %d\n", (int)Node->GetIntKey(), Node->Value);

  Node = Node->NextList();
}

Je suis tombé sur ce fil SO lors de ma phase de recherche pour voir si quelque chose comme OrderedHash existait déjà sans me demander de déposer dans une bibliothèque massive. J'étais déçu. Alors j'ai écrit le mien. Et maintenant je l'ai partagé.

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

Une autre façon de l'implémenter est d' maputiliser un au lieu d'un vector. Je vais vous montrer cette approche et discuter des différences:

Créez simplement une classe avec deux cartes dans les coulisses.

#include <map>
#include <string>

using namespace std;

class SpecialMap {
  // usual stuff...

 private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> data_;
};

Vous pouvez ensuite exposer un itérateur à un itérateur data_dans le bon ordre. La façon dont vous faites cela est de parcourir insertion_order_, et pour chaque élément que vous obtenez de cette itération, faites une recherche dans le data_avec la valeur deinsertion_order_

Vous pouvez utiliser le plus efficace hash_mappour insertion_order car vous ne vous souciez pas de l'itération directe insertion_order_.

Pour faire des insertions, vous pouvez avoir une méthode comme celle-ci:

void SpecialMap::Insert(const string& key, int value) {
  // This may be an over simplification... You ought to check
  // if you are overwriting a value in data_ so that you can update
  // insertion_order_ accordingly
  insertion_order_[counter_++] = key;
  data_[key] = value;
}

Il existe de nombreuses façons d'améliorer la conception et de vous soucier des performances, mais c'est un bon squelette pour vous aider à implémenter cette fonctionnalité vous-même. Vous pouvez créer un modèle et stocker des paires en tant que valeurs dans data_ afin de pouvoir facilement référencer l'entrée dans insertion_order_. Mais je laisse ces problèmes de conception comme un exercice :-).

Mise à jour : je suppose que je devrais dire quelque chose sur l'efficacité de l'utilisation de la carte par rapport au vecteur pour insertion_order_

• recherches directement dans les données, dans les deux cas sont O (1)
• les insertions dans l'approche vectorielle sont O (1), les insertions dans l'approche cartographique sont O (logn)
• les suppressions dans l'approche vectorielle sont O (n) car vous devez rechercher l'élément à supprimer. Avec l'approche cartographique, ils sont O (logn).

Peut-être que si vous n'utilisez pas autant de suppressions, vous devriez utiliser l'approche vectorielle. L'approche de la carte serait meilleure si vous preniez en charge un ordre différent (comme la priorité) au lieu d'un ordre d'insertion.

Voici une solution qui ne nécessite que la bibliothèque de modèles standard sans utiliser le multiindex de boost:
Vous pouvez utiliser std::map<std::string,int>;et vector <data>;où dans la carte vous stockez l'index de l'emplacement des données dans le vecteur et stocke les données vectorielles dans l'ordre d'insertion. Ici, l'accès aux données a une complexité O (log n). l'affichage des données dans l'ordre d'insertion a une complexité O (n). l'insertion de données a une complexité O (log n).

Par exemple:

#include<iostream>
#include<map>
#include<vector>

struct data{
int value;
std::string s;
}

typedef std::map<std::string,int> MapIndex;//this map stores the index of data stored 
                                           //in VectorData mapped to a string              
typedef std::vector<data> VectorData;//stores the data in insertion order

void display_data_according_insertion_order(VectorData vectorData){
    for(std::vector<data>::iterator it=vectorData.begin();it!=vectorData.end();it++){
        std::cout<<it->value<<it->s<<std::endl;
    }
}
int lookup_string(std::string s,MapIndex mapIndex){
    std::MapIndex::iterator pt=mapIndex.find(s)
    if (pt!=mapIndex.end())return it->second;
    else return -1;//it signifies that key does not exist in map
}
int insert_value(data d,mapIndex,vectorData){
    if(mapIndex.find(d.s)==mapIndex.end()){
        mapIndex.insert(std::make_pair(d.s,vectorData.size()));//as the data is to be
                                                               //inserted at back 
                                                               //therefore index is
                                                               //size of vector before
                                                               //insertion
        vectorData.push_back(d);
        return 1;
    }
    else return 0;//it signifies that insertion of data is failed due to the presence
                  //string in the map and map stores unique keys
}

Ceci est quelque peu lié à la réponse de Faisals. Vous pouvez simplement créer une classe wrapper autour d'une carte et d'un vecteur et les garder facilement synchronisés. Une encapsulation correcte vous permettra de contrôler la méthode d'accès et donc le conteneur à utiliser ... le vecteur ou la carte. Cela évite d'utiliser Boost ou quelque chose comme ça.

Une chose dont vous devez tenir compte est le petit nombre d'éléments de données que vous utilisez. Il est possible qu'il soit plus rapide d'utiliser uniquement le vecteur. Il y a une surcharge dans la carte qui peut rendre plus coûteuse les recherches dans de petits ensembles de données que le vecteur plus simple. Donc, si vous savez que vous utiliserez toujours à peu près le même nombre d'éléments, faites une analyse comparative et voyez si les performances de la carte et du vecteur sont ce que vous pensez vraiment. Vous pouvez trouver que la recherche dans un vecteur avec seulement 50 éléments est presque identique à la carte.

// Devrait être comme cet homme!

// Ceci maintient la complexité de l'insertion est O (logN) et la suppression est également O (logN).

class SpecialMap {
private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> insertion_order_reverse_look_up; // <- for fast delete
  map<string, Data> data_;
};

À utiliser boost::multi_indexavec les index de carte et de liste.

Une carte de paires (str, int) et int statique qui s'incrémente lors des appels d'insertion indexe les paires de données. Mettre dans une structure qui peut retourner le statique int val avec un membre index () peut-être?