A std :: map que realiza un seguimiento del orden de inserción?

Question

Actualmente tengo un std::map<std::string,int> que almacena un valor entero en un identificador de cadena único, y busco con la cadena. Hace principalmente lo que quiero, excepto que no hace un seguimiento del orden de inserción. Cuando itere el mapa para imprimir los valores, se ordenan según la cadena; pero quiero que se clasifiquen según el orden de (primera) inserción.

Pensé en utilizar un vector<pair<string,int>> en su lugar, pero tengo que buscar la cadena e incrementar los valores enteros unas 10.000.000 de veces, por lo que no sé si un vector será significativamente más lento.

¿Hay alguna manera de usar std :: map o hay otro contenedor estándar que se adapte mejor a mis necesidades?

[Estoy en GCC 3.4, y probablemente no tenga más de 50 pares de valores en mi std :: map].

Answer 1

No puede hacer eso con un mapa, pero puede usar dos estructuras separadas, el mapa y el vector y mantenerlos sincronizados, es decir, cuando elimina del mapa, busca y elimina el elemento del vector. O puede crear un map<string, pair<int,int>>, y en su par almacenar el tamaño() del mapa al insertarlo para registrar la posición, junto con el valor de int, y luego cuando imprima, use el miembro de posición para ordenar.

Answer 2

Si necesita ambas estrategias de búsqueda, terminará con dos contenedores. Puede usar un vector con sus valores reales (int s) y poner un map< string, vector< T >::difference_type> al lado, devolviendo el índice al vector.

Para completar todo eso, puede encapsular ambos en una clase.

Pero creo boost has a container con múltiples índices.

Answer 3

Si solo tiene 50 valores en std :: map, puede copiarlos en std :: vector antes de imprimirlos y ordenarlos mediante std :: sort utilizando el functor apropiado.

O podría usar boost::multi_index. Permite usar varios índices. En su caso podría ser similar al siguiente:

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

que te pueden combinar una std::vector con un (una tabla hash) std::tr1::unordered_map. Aquí hay un enlace al Boost's documentation para unordered_map. Puede usar el vector para realizar un seguimiento del orden de inserción y la tabla hash para realizar las búsquedas frecuentes. Si realiza cientos de miles de búsquedas, la diferencia entre la búsqueda O (log n) para std::map y O (1) para una tabla hash puede ser 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

Esto está relacionado con la respuesta de Faisals. Puede crear una clase de contenedor alrededor de un mapa y un vector y mantenerlos sincronizados fácilmente. La encapsulación adecuada le permitirá controlar el método de acceso y, por lo tanto, qué contenedor usar ... el vector o el mapa. Esto evita el uso de Boost o algo así.

Answer 6

Otra forma de implementar esto es con un map en lugar de un vector. Le mostraré este enfoque y analizaré las diferencias:

Solo cree una clase que tenga dos mapas detrás de escena.

#include <map> 
#include <string> 

using namespace std; 

class SpecialMap { 
    // usual stuff... 

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

A continuación, puede exponer a un iterador iterador sobre data_ en el orden correcto. La forma de hacerlo es iterar insertion_order_, y para cada elemento que se obtiene de esa iteración, hacer una búsqueda en el data_ con el valor de insertion_order_

Puede utilizar la más eficiente para hash_map insertion_order ya no le importa sobre iterar directamente a través de insertion_order_.

Para hacer inserciones, puede tener un método como este:

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

Hay muchas maneras de hacer el diseño mejor y preocuparse por el rendimiento, pero esto es un buen esqueleto para empezar en la implementación de esta funcionalidad por su cuenta. Puede hacerlo con plantilla, y puede almacenar pares como valores en data_ para que pueda hacer referencia fácilmente a la entrada en insertion_order_. Pero dejo estos problemas de diseño como un ejercicio :-).

actualización: supongo que debería decir algo sobre la eficiencia de la utilización de un mapa vs vector para insertion_order_

• búsquedas directamente en los datos, en ambos casos son O (1)
• insertos en el enfoque vectorial son O (1), las inserciones en el enfoque del mapa son O (logn)
• eliminaciones en el enfoque vectorial son O (n) porque tiene que buscar el elemento para eliminar. Con el enfoque del mapa son O (logn).

Quizás si no va a utilizar eliminaciones tanto, debe utilizar el enfoque vectorial. El enfoque del mapa sería mejor si estuviera apoyando un orden diferente (como la prioridad) en lugar del orden de inserción.

Answer 7

Una cosa que debe tener en cuenta es la cantidad de elementos de datos que está utilizando. Es posible que sea más rápido usar solo el vector. Hay algunos gastos generales en el mapa que pueden hacer que resulte más costoso realizar búsquedas en conjuntos de datos pequeños que el vector más simple. Por lo tanto, si sabe que siempre usará la misma cantidad de elementos, haga una evaluación comparativa y vea si el rendimiento del mapa y el vector es lo que realmente cree que es. Puede encontrar que la búsqueda en un vector con solo 50 elementos es casi la misma que en el mapa.

Answer 8

Mantener un paralelo list<string> insertionOrder.

Cuando es el momento de imprimir, iterar en la listay realizar búsquedas en el mapa .

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

Answer 9

// Debería ser como este hombre!

// Esto mantiene la complejidad de la inserción es O (logN) y la eliminación también es 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

Aquí es una solución que sólo requiere biblioteca de plantillas estándar sin necesidad de utilizar multiindex de impulso:
Usted podría utilizar std::map<std::string,int>; y vector <data>; donde en el mapa se almacena el índice de la ubicación de los datos en almacena los datos vectoriales y de vectores con el fin de inserción . Aquí el acceso a los datos tiene una complejidad O (log n). visualizar datos en orden de inserción tiene O (n) complejidad. la inserción de datos tiene complejidad O (log n).

Por ejemplo:

#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

Uso boost::multi_index con el mapa y la lista de índices.

Answer 12

Lo que quiere (sin recurrir a Boost) es lo que llamo un "hash pedido", que es esencialmente un mashup de un hash y una lista vinculada con cadenas o enteros (o ambos al mismo tiempo). Un hash ordenado mantiene el orden de los elementos durante la iteración con el rendimiento absoluto de un hash.

He estado recopilando una biblioteca de fragmentos de C++ relativamente nueva que completa lo que veo como agujeros en el lenguaje C++ para los desarrolladores de bibliotecas C++. Vaya aquí:

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

Grab:

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

Si los datos controlados por el usuario serán colocados en la tabla hash, también puede que quiera:

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

Me encontré con este hilo SO durante mi fase de investigación para ver si ya existía algo así como OrderedHash sin necesidad de incluir una biblioteca masiva. Estaba decepcionado. Así que escribí el mío. Y ahora lo he compartido.

Answer 13

Tessil tiene una muy buena implementación de mapa ordenado (y conjunto) que es la licencia de MIT. Lo puedes encontrar aquí: ordered-map

ejemplo Mapa

#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

Un mapa de par (str, int) e int estática que se incrementa en el inserto llama índices de pares de datos. Ponga en una estructura que puede devolver el intval estático con un miembro index() tal vez?