Una std :: mappa che tiene traccia dell'ordine di inserimento?

Question

Attualmente ho uno std::map<std::string,int> che memorizza un valore intero su un identificatore di stringa univoco e cerco con la stringa. Fa principalmente quello che voglio, tranne per il fatto che non tiene traccia dell'ordine di inserimento. Quindi quando eseguo l'iterazione della mappa per stampare i valori, vengono ordinati in base alla stringa; ma voglio che siano ordinati secondo l'ordine di (primo) inserimento.

Ho pensato di utilizzare un vector<pair<string,int>> invece, ma ho bisogno di cercare la stringa e incrementare i valori interi di circa 10.000.000 di volte, quindi non so se un vettore sarà molto più lento.

C'è un modo per usare std :: map o c'è un altro container std che si adatta meglio alle mie necessità?

[Sono su GCC 3.4 e probabilmente non ho più di 50 coppie di valori nella mia std :: map].

Answer 1

Non è possibile farlo con una mappa, ma è possibile utilizzare due strutture separate - la mappa e il vettore e mantenerle sincronizzate - ovvero quando si elimina dalla mappa, trovare ed eliminare l'elemento dal vettore. Oppure puoi creare un map<string, pair<int,int>> - e nella tua coppia memorizzare la dimensione() della mappa al momento dell'inserimento nella posizione del record, insieme al valore dell'int, e quindi quando stampi, usa il membro della posizione per ordinare.

Answer 2

Se hai bisogno di entrambe le strategie di ricerca, finirai con due contenitori. È possibile utilizzare uno vector con i valori effettivi (int s) e posizionare uno map< string, vector< T >::difference_type> accanto, restituendo l'indice nel vettore.

Per completare tutto ciò, è possibile incapsulare entrambi in una classe.

Ma credo che boost has a container con più indici.

Answer 3

Se si hanno solo 50 valori in std :: map, è possibile copiarli su std :: vector prima di stampare e ordinare tramite std :: sort utilizzando il functor appropriato.

Oppure è possibile utilizzare boost::multi_index. Permette di utilizzare diversi indici. Nel tuo caso potrebbe essere simile al seguente:

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 4

si potrebbe combinare un std::vector con una (una tabella di hash) std::tr1::unordered_map. Ecco un collegamento a Boost's documentation per unordered_map. È possibile utilizzare il vettore per tenere traccia dell'ordine di inserimento e la tabella hash per eseguire le ricerche frequenti. Se stai facendo centinaia di migliaia di ricerche, la differenza tra la ricerca O (log n) per std::map e O (1) per una tabella hash potrebbe essere significativa.

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 5

Questo è in qualche modo correlato alla risposta Faisals. Puoi semplicemente creare una classe wrapper attorno a una mappa e un vettore e mantenerli facilmente sincronizzati. L'incapsulamento corretto ti consentirà di controllare il metodo di accesso e quindi quale contenitore usare ... il vettore o la mappa. Questo evita l'uso di Boost o qualcosa del genere.

Answer 6

Un altro modo per implementare questo è con un map anziché uno vector. Ti mostrerò questo approccio e discuterò le differenze:

Basta creare una classe con due mappe dietro le quinte.

#include <map> 
#include <string> 

using namespace std; 

class SpecialMap { 
    // usual stuff... 

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

È quindi possibile esporre un iteratore per iteratore su data_ nel giusto ordine. Il modo di fare che è iterare attraverso insertion_order_, e per ogni elemento che si ottiene da questa iterazione, fare una ricerca nel data_ con il valore da insertion_order_

È possibile utilizzare il più efficiente hash_map per insertion_order dal momento che non si cura su iterando direttamente attraverso insertion_order_.

Per fare inserti, si può avere un metodo come questo:

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

Ci sono un sacco di modi per rendere il design migliore e preoccuparsi delle prestazioni, ma questo è un buona ossatura per iniziare sull'implementazione di questa funzionalità da soli. Puoi renderlo basato su modelli e potresti effettivamente memorizzare coppie come valori in data_ in modo da poter facilmente fare riferimento alla voce in insertion_order_. Ma lascio questi problemi di progettazione come un esercizio :-).

Aggiornamento: Suppongo che dovrei dire qualcosa su efficienza del usando la mappa vs. vettore per insertion_order_

• ricerche direttamente in dati, in entrambi i casi sono O (1)
• inserti in l'approccio vettoriale è O (1), gli inserimenti nell'approccio mappa sono O (logn)
• le eliminazioni nell'approccio vettoriale sono O (n) perché è necessario eseguire la scansione dell'elemento da rimuovere. Con l'approccio mappa sono O (logn).

Forse, se non si intende utilizzare le eliminazioni, è necessario utilizzare l'approccio vettoriale. L'approccio cartografico sarebbe meglio se tu stessi supportando un diverso ordinamento (come priorità) invece dell'ordine di inserimento.

Answer 7

Una cosa che devi considerare è il numero ridotto di elementi di dati che stai utilizzando. È possibile che sia più veloce usare solo il vettore. Nella mappa è presente un sovraccarico che può comportare costi più elevati per la ricerca in insiemi di dati di piccole dimensioni rispetto al vettore più semplice. Quindi, se sai che utilizzerai sempre lo stesso numero di elementi, fai un benchmarking e vedi se le prestazioni della mappa e del vettore sono ciò che pensi davvero che sia. È possibile trovare la ricerca in un vettore con solo 50 elementi è quasi la stessa della mappa.

Answer 8

Mantieni un parallelo list<string> insertionOrder.

Quando è il momento di stampare, iterare sulla lista e fare ricerche nella mappa.

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

Answer 9

// Dovrebbe essere come quest'uomo!

// Ciò mantiene la complessità dell'inserimento O (logN) e anche l'eliminazione 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_; 
}; 

Answer 10

Ecco soluzione che richiede solo libreria di template standard senza utilizzare multiindex di spinta:
Si potrebbe utilizzare std::map<std::string,int>; e vector <data>; dove nel mappa memorizzare l'indice della posizione dei dati nel vettore e vettoriali memorizza i dati in ordine di inserimento . Qui l'accesso ai dati ha complessità O (log n). la visualizzazione dei dati nell'ordine di inserimento ha una complessità O (n). l'inserimento dei dati ha complessità O (log n).

Per esempio:

#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 
} 

Answer 11

Usa boost::multi_index con il programma e l'elenco degli indici.

Answer 12

Quello che si desidera (senza ricorrere a Boost) è quello che io chiamo un "hash ordinato", che è essenzialmente un mashup di un hash e una lista collegata con chiavi stringa o numeri interi (o entrambi allo stesso tempo). Un hash ordinato mantiene l'ordine degli elementi durante l'iterazione con la prestazione assoluta di un hash.

Ho assemblato una libreria di snippet C++ relativamente recente che riempie ciò che vedo come buchi nel linguaggio C++ per gli sviluppatori di librerie C++. Vai qui:

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

Grab:

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

Se i dati controllati dall'utente saranno collocati nella hash, si potrebbe anche voler:

security/security_csprng.cpp 
security/security_csprng.h 

invocarlo:

#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(); 
} 

Mi sono imbattuto in questo thread SO durante la mia fase di ricerca per vedere se qualcosa come OrderedHash esistesse già senza che mi fosse necessario inserire una libreria enorme. Io ero delusa. Così ho scritto il mio. E ora l'ho condiviso.

Answer 13

Tessil ha una implementazione molto bella della mappa ordinata (e impostata) che è la licenza MIT. Lo si può trovare qui: ordered-map

Mappa esempio

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

Answer 14

Una mappa di coppia (str, int) e int statico che incrementa sull'inserto chiamate indici coppie di dati. Inserisci una struttura che può restituire il valore stat int int con un membro index() forse?