¿Un mapa std :: que realiza un seguimiento del orden de inserción?

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

Pensé en usar a vector<pair<string,int>>en su lugar, pero necesito buscar la cadena e incrementar los valores enteros alrededor de 10,000,000 de veces, así que no sé si a std::vectorserá significativamente más lento.

¿Hay alguna forma de uso std::mapo hay otro stdcontenedor que mejor se adapte a mis necesidades?

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

Gracias.

Si solo tiene 50 valores en std :: map, puede copiarlos en std :: vector antes de imprimir y ordenarlos a través de std :: sort usando el functor apropiado.

O puede usar boost :: multi_index . Permite utilizar varios índices. En su caso, podría verse así:

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;

Puede combinar a std::vectorcon a std::tr1::unordered_map(una tabla hash). Aquí hay un enlace a la documentación de Boost para unordered_map. Puede utilizar el vector para realizar un seguimiento del orden de inserción y la tabla hash para realizar búsquedas frecuentes. Si está realizando cientos de miles de búsquedas, la diferencia entre la búsqueda O (log n) std::mapy 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';
}

Mantenga un paralelo list<string> insertionOrder.

Cuando llegue el momento de imprimir, repita la lista y busque en el mapa .

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

Tessil tiene una muy buena implementación de mapa ordenado (y conjunto) que es una licencia MIT. Puede encontrarlo aquí: order-map

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

Si necesita ambas estrategias de búsqueda, terminará con dos contenedores. Puede usar a vectorcon sus valores reales inty poner un map< string, vector< T >::difference_type> junto a él, devolviendo el índice al vector.

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

Pero creo que boost tiene un contenedor con múltiples índices.

Lo que quieres (sin recurrir a Boost) es lo que yo llamo un "hash ordenado", que es esencialmente un mashup de un hash y una lista vinculada con claves de cadena o enteras (o ambas 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 armando una biblioteca de fragmentos de C ++ relativamente nueva que llena lo que veo como agujeros en el lenguaje C ++ para los desarrolladores de bibliotecas de C ++. Ven aquí:

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

Agarrar:

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

Si los datos controlados por el usuario se colocarán en el hash, es posible que también desee:

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 de SO durante mi fase de investigación para ver si ya existía algo como OrderedHash sin que tuviera que colocar una biblioteca masiva. Estaba decepcionado. Así que escribí el mío. Y ahora lo he compartido.

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, encuentra 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 en la posición del registro, junto con el valor del int, y luego, cuando imprima, use el miembro de posición para ordenar.

Otra forma de implementar esto es con a en maplugar de a vector. Le mostraré este enfoque y discutiré las diferencias:

Simplemente 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 un iterador a iterador data_en el orden correcto. La forma en que lo hace es iterar insertion_order_, y para cada elemento que obtenga de esa iteración, realice una búsqueda en el data_con el valor deinsertion_order_

Puede usar el más eficiente hash_mappara insertion_order ya que no le importa iterar directamente 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 formas en que puede mejorar el diseño y preocuparse por el rendimiento, pero este es un buen esqueleto para comenzar a implementar esta funcionalidad por su cuenta. Puede crear una plantilla y, de hecho, podría 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 ejercicio :-).

Actualización : supongo que debería decir algo sobre la eficiencia de usar mapa frente a vector para insertion_order_

• búsquedas directamente en los datos, en ambos casos son O (1)
• las inserciones en el enfoque de vector son O (1), las inserciones en el enfoque de mapa son O (logn)
• las eliminaciones en el enfoque de vector son O (n) porque debe buscar el elemento para eliminar. Con el enfoque de mapa son O (logn).

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

Aquí hay una solución que requiere solo una biblioteca de plantillas estándar sin usar el índice múltiple de boost:
puede usar std::map<std::string,int>;y vector <data>;dónde en el mapa almacena el índice de la ubicación de los datos en el vector y almacena los datos en el orden de inserción. Aquí el acceso a los datos tiene una complejidad O (log n). mostrar datos en orden de inserción tiene una complejidad O (n). la inserción de datos tiene una 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
}

Esto está algo relacionado con la respuesta de Faisal. Puede crear una clase contenedora 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 usar Boost o algo por el estilo.

Una cosa que debe tener en cuenta es la pequeña cantidad de elementos de datos que está utilizando. Es posible que sea más rápido usar solo el vector. Hay una sobrecarga en el mapa que puede hacer que sea más costoso realizar búsquedas en conjuntos de datos pequeños que con un vector más simple. Por lo tanto, si sabe que siempre utilizará aproximadamente 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 igual que el mapa.

// ¡Debería ser como este hombre!

// Esto mantiene que 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_;
};

Úselo boost::multi_indexcon mapas y listas de índices.

Un mapa de par (str, int) e int estático que se incrementa en las llamadas de inserción indexa pares de datos. ¿Poner una estructura que pueda devolver el valor int estático con un miembro index () quizás?