unordered_set unordered_map unordered example c++ c++11 unordered-map

unordered_set - unordered_map c++ example



std:: unordered_map:: find utilizando un tipo diferente al tipo Key? (7)

Tengo un unordered_map que usa un tipo de cadena como clave:

std::unordered_map<string, value> map;

Se proporciona una especialización std::hash para la string , así como un operator== adecuado operator== .

Ahora también tengo una clase de "vista de cadena", que es un puntero débil en una cadena existente, evitando las asignaciones de montón:

class string_view { string *data; size_t begin, len; // ... };

Ahora me gustaría poder verificar si existe una clave en el mapa usando un objeto string_view . Desafortunadamente, std::unordered_map::find toma un argumento Key , no un argumento T genérico.

(Claro, puedo "promover" uno en una string , pero eso causa una asignación que me gustaría evitar.)

Lo que me hubiera gustado en cambio era algo como

template<class Key, class Value> class unordered_map { template<class T> iterator find(const T &t); };

lo que requeriría que operator==(T, Key) y std::hash<T>() estén adecuadamente definidos, y devolvería un iterador a un valor coincidente.

¿Hay algún trabajo alrededor?

Como se mencionó anteriormente, C ++ 14 no proporciona una búsqueda heterogénea para std::unordered_map (a diferencia de std::map ). Puede usar Boost.MultiIndex para definir un sustituto bastante estrecho de std::unordered_map que le permite buscar string_view s sin asignar std::string s temporal:

Live Coliru Demo

#include <boost/multi_index_container.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/member.hpp> #include <string> using namespace boost::multi_index; struct string_view { std::string *data; std::size_t begin,len; }; template<typename T,typename Q> struct mutable_pair { T first; mutable Q second; }; struct string_view_hash { std::size_t operator()(const string_view& v)const { return boost::hash_range( v.data->begin()+v.begin,v.data->begin()+v.begin+v.len); } std::size_t operator()(const std::string& s)const { return boost::hash_range(s.begin(),s.end()); } }; struct string_view_equal_to { std::size_t operator()(const std::string& s1,const std::string& s2)const { return s1==s2; } std::size_t operator()(const std::string& s1,const string_view& v2)const { return s1.size()==v2.len&& std::equal( s1.begin(),s1.end(), v2.data->begin()+v2.begin); } std::size_t operator()(const string_view& v1,const std::string& s2)const { return v1.len==s2.size()&& std::equal( v1.data->begin()+v1.begin,v1.data->begin()+v1.begin+v1.len, s2.begin()); } }; template<typename Q> using unordered_string_map=multi_index_container< mutable_pair<std::string,Q>, indexed_by< hashed_unique< member< mutable_pair<std::string,Q>, std::string, &mutable_pair<std::string,Q>::first >, string_view_hash, string_view_equal_to > > >; #include <iostream> int main() { unordered_string_map<int> m={{"hello",0},{"boost",1},{"bye",2}}; std::string str="helloboost"; auto it=m.find(string_view{&str,5,5}); std::cout<<it->first<<","<<it->second<<"/n"; }

Salida

boost,1

Disculpe por responder a esta pregunta tan antigua, pero aún aparece en los resultados del motor de búsqueda ... En este caso, su unordered_map está usando el tipo de cadena como su clave, el método de búsqueda está buscando una referencia a una cadena que no generará una asignación. Tu clase string_view almacena un puntero a una cadena. Por lo tanto, su clase string_view puede desreferir el puntero a una referencia del tipo necesario para su mapa sin causar una asignación. El método se vería así ...

string &string_view::getRef() const { return *_ptr; }

y para usar el string_view con el mapa se vería así

auto found=map.find(string_view_inst.getRef());

tenga en cuenta que esto no funcionará para la clase string_view c ++ 17, ya que no almacena internamente un objeto std :: string

PD. Es probable que su clase string_view no sea ideal para cachés de CPU ya que almacena un puntero a una cadena asignada en algún lugar del montón, y la cadena misma almacena un puntero a los datos reales ubicados en otro lugar del montón. Cada vez que acceda a su string_view resultará en una doble referencia.

Esta solución tiene inconvenientes, que pueden o no hacerla inviable para su contexto.

Puedes hacer una clase de envoltorio:

struct str_wrapper { const char* start, end; };

Y cambia tu mapa para usar str_wrapper como su clave. Tendría que agregar 2 constructores a str_wrapper, uno para std :: string y otro para su string_view. La decisión principal es si hacer que estos constructores realicen copias profundas o superficiales.

Por ejemplo, si usa std :: string solo para inserciones y str_view solo para búsquedas, haría que el constructor de std :: string sea más profundo y str_view uno superficial (esto se puede aplicar en tiempo de compilación si usa un contenedor personalizado) Unordered_map). Si quiere evitar las fugas de memoria en la copia profunda, necesitará campos adicionales para admitir la destrucción adecuada.

Si su uso es más variado, (buscando std :: string''s o insertando por str_view), habrá inconvenientes, lo que, de nuevo, podría hacer que el enfoque sea demasiado desagradable como para ser inviable. Depende de su uso previsto.

Otra opción más es dividir la búsqueda y la administración de datos mediante el uso de múltiples contenedores:

std::unordered_map<string_view, value> map; std::vector<unique_ptr<const char[]>> mapKeyStore;

Las búsquedas se realizan utilizando string_view s sin la necesidad de asignaciones. Cada vez que se inserta una nueva clave, primero debemos agregar una asignación de cadena real:

mapKeyStore.push_back(conv(str)); // str can be string_view, char*, string... as long as it converts to unique_ptr<const char[]> or whatever type map.emplace(mapKeyStore.back().get(), value)

Sería mucho más intuitivo usar std::string en mapKeyStore . Sin embargo, el uso de std::string no garantiza que la memoria de la cadena no cambie (por ejemplo, si el vector cambia de tamaño). Con el unique_ptr esto se hace cumplir. Sin embargo, necesitamos alguna rutina especial de conversión / asignación, llamada conv en el ejemplo. Si tiene un contenedor de cadenas personalizado que garantiza la consistencia de los datos en los movimientos (y obliga al vector a usar movimientos), entonces puede usarlo aquí.

El inconveniente

La desventaja del método anterior es que el manejo de las eliminaciones no es trivial y costoso si se hace ingenuo. Si el mapa solo se crea una vez o solo crece, esto no es un problema y el patrón anterior funciona bastante bien.

Ejemplo de ejecución

El siguiente ejemplo incluye una eliminación ingenua de una clave.

#include <vector> #include <unordered_map> #include <string> #include <string_view> #include <iostream> #include <memory> #include <algorithm> using namespace std; using PayLoad = int; unique_ptr<const char[]> conv(string_view str) { unique_ptr<char[]> p (new char [str.size()+1]); memcpy(p.get(), str.data(), str.size()+1); return move(p); } int main() { unordered_map<string_view, PayLoad> map; vector<unique_ptr<const char[]>> mapKeyStore; // Add multiple values mapKeyStore.push_back(conv("a")); map.emplace(mapKeyStore.back().get(), 3); mapKeyStore.push_back(conv("b")); map.emplace(mapKeyStore.back().get(), 1); mapKeyStore.push_back(conv("c")); map.emplace(mapKeyStore.back().get(), 4); // Search all keys cout << map.find("a")->second; cout << map.find("b")->second; cout << map.find("c")->second; // Delete the "a" key map.erase("a"); mapKeyStore.erase(remove_if(mapKeyStore.begin(), mapKeyStore.end(), [](const auto& a){ return strcmp(a.get(), "a") == 0; }), mapKeyStore.end()); // Test if verything is OK. cout << ''/n''; for(auto it : map) cout << it.first << ": " << it.second << "/n"; return 0; }

Por supuesto, los dos contenedores se pueden colocar en una envoltura que maneja la inserción y la eliminación por sí misma.

Parece que tan recientemente como C ++ 14, incluso el map básico obtuvo un resultado de plantilla para los tipos is_transparent en la comparación. Lo más probable es que la implementación correcta para los contenedores de hash no fuera evidente de inmediato.

Por lo que puedo ver tus dos opciones son:

Podrías permitir que tu vista se pueda convertir implícitamente a un std::string :

class StringView { // ... operator std::string() const { return data->substr(begin, len); } // ... };

P0919R2 ¡La búsqueda heterogénea de contenedores desordenados se ha fusionado en el borrador de trabajo de C ++ 2a!

El resumen parece una combinación perfecta con mi pregunta original :-)

Resumen

Esta propuesta agrega un soporte de búsqueda heterogéneo a los contenedores asociativos no ordenados en la biblioteca estándar de C ++. Como resultado, no se necesita la creación de un objeto de clave temporal cuando se proporciona un tipo diferente (pero compatible) como clave para la función miembro. Esto también hace que las interfaces de contenedor asociativo no ordenadas y regulares y la funcionalidad sean más compatibles entre sí.

Con los cambios propuestos por este documento, el siguiente código funcionará sin ningún impacto de rendimiento adicional:

template<typename Key, typename Value> using h_str_umap = std::unordered_map<Key, Value, string_hash>; h_str_umap<std::string, int> map = /* ... */; map.find("This does not create a temporary std::string object :-)"sv);