c++ - programacion - Un estándar:: mapa que realiza un seguimiento del orden de inserción?
manual de programacion android pdf (14)
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 usar un vector<pair<string,int>> lugar, pero necesito buscar la cadena e incrementar los valores enteros unas 10,000,000 de veces, así 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].
// ¡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_;
};
Aquí hay una solución que solo requiere una biblioteca de plantillas estándar sin utilizar el multiindex de boost:
Puede usar std::map<std::string,int>; y vector <data>; donde en el mapa se almacena el índice de la ubicación de los datos en el vector y el vector almacena los datos en el orden 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
}
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í.
Lo que quiere (sin recurrir a Boost) es lo que yo llamo un "hash ordenado", que es esencialmente una combinación 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 desarrolladores de bibliotecas 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 SO durante mi fase de investigación para ver si algo como OrderedHash ya existía sin requerir que ingresara en una biblioteca masiva. Estaba decepcionado. Así que escribí el mío. Y ahora lo he compartido.
Mantenga una list<string> insertionOrder paralela list<string> insertionOrder .
Cuando sea el momento de imprimir, itere en la lista y realice búsquedas en el mapa .
each element in insertionOrder // walks in insertionOrder..
print map[ element ].second // but lookup is in map
No puede hacer eso con un mapa, pero podría usar dos estructuras separadas, el mapa y el vector, y mantenerlos sincronizados, es decir, cuando borre del mapa, busque y elimine 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.
Otra forma de implementar esto es con un map lugar de un vector . Te mostraré este enfoque y discutiré las diferencias:
Solo crea 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 sobre data_ en el orden correcto. La forma de hacerlo es iterar a través de insertion_order_ , y para cada elemento que obtenga de esa iteración, haga una búsqueda en data_ con el valor de insertion_order_
Puede utilizar el hash_map más eficiente para insertion_order, ya que no le importa iterar directamente a través de insertion_order_ .
Para hacer inserciones, puedes 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 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 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 del uso del mapa frente al vector para insertion_order_
- búsquedas directamente en datos, en ambos casos son O (1)
- las inserciones en el enfoque vectorial son O (1), las inserciones en el enfoque del mapa son O (logn)
- las eliminaciones en el enfoque vectorial son O (n) porque debe buscar el elemento para eliminar. Con el enfoque del mapa son O (logn).
Tal vez 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.
Puede combinar un std::vector con un std::tr1::unordered_map (una tabla hash). Aquí hay un enlace a la documentación de Boost 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 está haciendo cientos de miles de búsquedas, la diferencia entre O (log n) búsqueda para std::map y O (1) para una tabla hash podría 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'';
}
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> 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.
Si tiene solo 50 valores en std :: map, puede copiarlos a 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 tu 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;
Tessil tiene una implementación muy buena de un mapa ordenado (y un conjunto) que es una licencia de MIT. Puede encontrarlo aquí: ordered-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;
}
}
Un mapa de pares (str, int) e int estático que se incrementa en llamadas de inserción indexa pares de datos. Ponga en una estructura que puede devolver el intval estático con un miembro index () tal vez?
Una cosa que debes tener en cuenta es la pequeña cantidad de elementos de datos que estás usando. 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.
Utilice boost::multi_index con los índices de mapa y lista.