ordered map
v1.1.0
La biblioteca de mapas ordenados proporciona un mapa hash y un conjunto hash que preserva el orden de inserción de una manera similar a OrderedDict de Python. Al iterar sobre el mapa, los valores se devolverán en el mismo orden en que se insertaron.
Los valores se almacenan de forma contigua en una estructura subyacente, sin espacios entre valores incluso después de una operación de borrado. De forma predeterminada, se usa un std::deque para esta estructura, pero también es posible usar un std::vector . Se puede acceder directamente a esta estructura a través del método values_container() y si la estructura es std::vector , también se proporciona un método data() para interactuar fácilmente con las API de C. Esto proporciona una iteración rápida pero con el inconveniente de una operación de borrado O(bucket_count). Están disponibles las funciones O(1) pop_back() y O(1) unordered_erase() . Si se utiliza con frecuencia el borrado ordenado, se recomienda otra estructura de datos.
Para resolver colisiones en hashes, la biblioteca utiliza un sondeo lineal de Robin Hood con eliminación por desplazamiento hacia atrás.
La biblioteca proporciona un comportamiento similar a std::deque/std::vector con valores únicos pero con una complejidad de tiempo promedio de O(1) para búsquedas y una complejidad de tiempo amortizada de O(1) para inserciones. Esto tiene el precio de una huella de memoria un poco mayor (8 bytes por depósito de forma predeterminada).
Se proporcionan dos clases: tsl::ordered_map y tsl::ordered_set .
Nota : La biblioteca utiliza una potencia de dos para el tamaño de su matriz de depósitos para aprovechar el módulo rápido. Para obtener un buen rendimiento, es necesario que la tabla hash tenga una función hash bien distribuida. Si encuentra problemas de rendimiento, verifique su función hash.
tsl::ordered_map desde CMakeLists.txt.std::unordered_map pero con inserciones más rápidas y uso de memoria reducido (consulte el punto de referencia para obtener más detalles).find con un tipo diferente a Key (por ejemplo, si tiene un mapa que usa std::unique_ptr<foo> como clave, puede usar foo* o std::uintptr_t como parámetro clave para find sin construir un std::unique_ptr<foo> , ver ejemplo).precalculated_hash en API).serialize/deserialize en la API para obtener más detalles).-fno-exceptions en Clang y GCC, sin una opción /EH en MSVC o simplemente definiendo TSL_NO_EXCEPTIONS ). std::terminate se usa en reemplazo de la instrucción throw cuando las excepciones están deshabilitadas.std::unordered_map y std::unordered_set .std::unordered_map tsl::ordered_map intenta tener una interfaz similar a std::unordered_map , pero existen algunas diferencias.
RandomAccessIterator .std::vector y std::deque (consulte la API para obtener más detalles). Si usa std::vector como ValueTypeContainer , puede usar reserve() para preasignar algo de espacio y evitar la invalidación de los iteradores al insertar.erase() , tiene una complejidad de O (bucket_count). Existe una versión O(1) más rápida, unordered_erase() , pero rompe el orden de inserción (consulte la API para obtener más detalles). También está disponible un O(1) pop_back() .operator== y operator!= dependen del orden. Dos tsl::ordered_map con los mismos valores pero insertados en un orden diferente no se comparan iguales.operator*() y operator->() devuelven una referencia y un puntero a const std::pair<Key, T> en lugar de std::pair<const Key, T> lo que hace que el valor T no sea modificable. Para modificar el valor, debe llamar al método value() del iterador para obtener una referencia mutable. Ejemplo: tsl::ordered_map< int , int > map = {{ 1 , 1 }, { 2 , 1 }, { 3 , 1 }};
for ( auto it = map.begin(); it != map.end(); ++it) {
// it->second = 2; // Illegal
it. value () = 2 ; // Ok
}IndexType ; consulte la API para obtener más detalles.bucket_size , bucket , ...). La garantía de seguridad de subprocesos es la misma que std::unordered_map (es decir, es posible tener varios lectores simultáneos sin ningún escritor).
Estas diferencias también se aplican entre std::unordered_set y tsl::ordered_set .
Si no se menciona lo contrario, las funciones tienen una sólida garantía de excepción; consulte los detalles. A continuación enumeramos los casos en los que no se proporciona esta garantía.
La garantía solo se proporciona si ValueContainer::emplace_back tiene una fuerte garantía de excepción (lo cual es cierto para std::vector y std::deque siempre que el tipo T no sea un tipo de solo movimiento con un constructor de movimiento que pueda generar un excepción, ver detalles).
Las funciones tsl::ordered_map::erase_if y tsl::ordered_set::erase_if solo tienen garantía bajo las condiciones previas enumeradas en su documentación.
Para usar el mapa ordenado, simplemente agregue el directorio de inclusión a su ruta de inclusión. Es una biblioteca de solo encabezados .
Si usa CMake, también puede usar el destino exportado tsl::ordered_map desde CMakeLists.txt con target_link_libraries .
# Example where the ordered-map project is stored in a third-party directory
add_subdirectory (third-party/ordered-map)
target_link_libraries (your_target PRIVATE tsl::ordered_map) Si el proyecto se instaló mediante make install , también puede usar find_package(tsl-ordered-map REQUIRED) en lugar de add_subdirectory .
El código debería funcionar con cualquier compilador compatible con el estándar C++ 11 y ha sido probado con GCC 4.8.4, Clang 3.5.0 y Visual Studio 2015.
Para ejecutar las pruebas necesitará la biblioteca Boost Test y CMake.
git clone https://github.com/Tessil/ordered-map.git
cd ordered-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_ordered_map_tests La API se puede encontrar aquí.
# include < iostream >
# include < string >
# include < cstdlib >
# include < tsl/ordered_map.h >
# include < tsl/ordered_set.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;
}
for ( auto it = map. begin (); it != map. end (); ++it) {
// it->second += 2; // Not valid.
it. value () += 2 ;
}
if (map. find ( ' d ' ) != map. end ()) {
std::cout << " Found 'd'. " << std::endl;
}
const std:: size_t precalculated_hash = std::hash< char >()( ' d ' );
// If we already know the hash beforehand, we can pass it as argument to speed-up the lookup.
if (map. find ( ' d ' , precalculated_hash) != map. end ()) {
std::cout << " Found 'd' with hash " << precalculated_hash << " . " << std::endl;
}
tsl::ordered_set< char , std::hash< char >, std::equal_to< char >,
std::allocator< char >, std::vector< char >> set;
set. reserve ( 6 );
set = { ' 3 ' , ' 4 ' , ' 9 ' , ' 2 ' };
set. erase ( ' 2 ' );
set. insert ( ' 1 ' );
set. insert ( ' ' );
set. pop_back ();
set. insert ({ ' 0 ' , ' ' });
// Get raw buffer for C API: 34910
std::cout << atoi (set. data ()) << std::endl;
} Las sobrecargas heterogéneas permiten el uso de otros tipos además de Key para operaciones de búsqueda y borrado, siempre que los tipos utilizados sean hash y comparables a Key .
Para activar las sobrecargas heterogéneas en tsl::ordered_map/set , el ID calificado KeyEqual::is_transparent debe ser válido. Funciona de la misma manera que para std::map::find . Puede usar std::equal_to<> o definir su propio objeto de función.
Tanto KeyEqual como Hash deberán poder manejar los diferentes tipos.
# include < functional >
# include < iostream >
# include < string >
# include < tsl/ordered_map.h >
struct employee {
employee ( int id, std::string name) : m_id(id), m_name(std::move(name)) {
}
// Either we include the comparators in the class and we use `std::equal_to<>`...
friend bool operator ==( const employee& empl, int empl_id) {
return empl. m_id == empl_id;
}
friend bool operator ==( int empl_id, const employee& empl) {
return empl_id == empl. m_id ;
}
friend bool operator ==( const employee& empl1, const employee& empl2) {
return empl1. m_id == empl2. m_id ;
}
int m_id;
std::string m_name;
};
// ... or we implement a separate class to compare employees.
struct equal_employee {
using is_transparent = void ;
bool operator ()( const employee& empl, int empl_id) const {
return empl. m_id == empl_id;
}
bool operator ()( int empl_id, const employee& empl) const {
return empl_id == empl. m_id ;
}
bool operator ()( const employee& empl1, const employee& empl2) const {
return empl1. m_id == empl2. m_id ;
}
};
struct hash_employee {
std:: size_t operator ()( const employee& empl) const {
return std::hash< int >()(empl. m_id );
}
std:: size_t operator ()( int id) const {
return std::hash< int >()(id);
}
};
int main () {
// Use std::equal_to<> which will automatically deduce and forward the parameters
tsl::ordered_map<employee, int , hash_employee, std::equal_to<>> map;
map. insert ({ employee ( 1 , " John Doe " ), 2001 });
map. insert ({ employee ( 2 , " Jane Doe " ), 2002 });
map. insert ({ employee ( 3 , " John Smith " ), 2003 });
// John Smith 2003
auto it = map. find ( 3 );
if (it != map. end ()) {
std::cout << it-> first . m_name << " " << it-> second << std::endl;
}
map. erase ( 1 );
// Use a custom KeyEqual which has an is_transparent member type
tsl::ordered_map<employee, int , hash_employee, equal_employee> map2;
map2. insert ({ employee ( 4 , " Johnny Doe " ), 2004 });
// 2004
std::cout << map2. at ( 4 ) << std::endl;
} La biblioteca proporciona una forma eficaz de serializar y deserializar un mapa o un conjunto para poder guardarlo en un archivo o enviarlo a través de la red. Para hacerlo, requiere que el usuario proporcione un objeto de función tanto para la serialización como para la deserialización.
struct serializer {
// Must support the following types for U: std::uint64_t, float
// and std::pair<Key, T> if a map is used or Key for a set.
template < typename U>
void operator ()( const U& value);
}; struct deserializer {
// Must support the following types for U: std::uint64_t, float
// and std::pair<Key, T> if a map is used or Key for a set.
template < typename U>
U operator ()();
};Tenga en cuenta que la implementación deja la compatibilidad binaria (endianidad, representación binaria flotante, tamaño de int, ...) de los tipos que serializa/deserializa en manos de los objetos de función proporcionados si se requiere compatibilidad.
Se pueden encontrar más detalles sobre los métodos serialize y deserialize en la API.
# include < cassert >
# include < cstdint >
# include < fstream >
# include < type_traits >
# include < tsl/ordered_map.h >
class serializer {
public:
explicit serializer ( const char * file_name) {
m_ostream. exceptions (m_ostream. badbit | m_ostream. failbit );
m_ostream. open (file_name, std::ios::binary);
}
template < class T ,
typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr >
void operator ()( const T& value) {
m_ostream. write ( reinterpret_cast < const char *>(&value), sizeof (T));
}
void operator ()( const std::pair<std:: int64_t , std:: int64_t >& value) {
(* this )(value. first );
(* this )(value. second );
}
private:
std::ofstream m_ostream;
};
class deserializer {
public:
explicit deserializer ( const char * file_name) {
m_istream. exceptions (m_istream. badbit | m_istream. failbit | m_istream. eofbit );
m_istream. open (file_name, std::ios::binary);
}
template < class T >
T operator ()() {
T value;
deserialize (value);
return value;
}
private:
template < class T ,
typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr >
void deserialize (T& value) {
m_istream. read ( reinterpret_cast < char *>(&value), sizeof (T));
}
void deserialize (std::pair<std:: int64_t , std:: int64_t >& value) {
deserialize (value. first );
deserialize (value. second );
}
private:
std::ifstream m_istream;
};
int main () {
const tsl::ordered_map<std:: int64_t , std:: int64_t > map = {{ 1 , - 1 }, { 2 , - 2 }, { 3 , - 3 }, { 4 , - 4 }};
const char * file_name = " ordered_map.data " ;
{
serializer serial (file_name);
map. serialize (serial);
}
{
deserializer dserial (file_name);
auto map_deserialized = tsl::ordered_map<std:: int64_t , std:: int64_t >:: deserialize (dserial);
assert (map == map_deserialized);
}
{
deserializer dserial (file_name);
/* *
* If the serialized and deserialized map are hash compatibles (see conditions in API),
* setting the argument to true speed-up the deserialization process as we don't have
* to recalculate the hash of each key. We also know how much space each bucket needs.
*/
const bool hash_compatible = true ;
auto map_deserialized =
tsl::ordered_map<std:: int64_t , std:: int64_t >:: deserialize (dserial, hash_compatible);
assert (map == map_deserialized);
}
} Es posible utilizar una biblioteca de serialización para evitar el texto estándar.
El siguiente ejemplo utiliza Boost Serialization con el flujo de compresión Boost zlib para reducir el tamaño del archivo serializado resultante. El ejemplo requiere C++20 debido al uso de la sintaxis de la lista de parámetros de plantilla en lambdas, pero se puede adaptar a versiones menos recientes.
# include < boost/archive/binary_iarchive.hpp >
# include < boost/archive/binary_oarchive.hpp >
# include < boost/iostreams/filter/zlib.hpp >
# include < boost/iostreams/filtering_stream.hpp >
# include < boost/serialization/split_free.hpp >
# include < boost/serialization/utility.hpp >
# include < cassert >
# include < cstdint >
# include < fstream >
# include < tsl/ordered_map.h >
namespace boost { namespace serialization {
template < class Archive , class Key , class T >
void serialize (Archive & ar, tsl::ordered_map<Key, T>& map, const unsigned int version) {
split_free (ar, map, version);
}
template < class Archive , class Key , class T >
void save (Archive & ar, const tsl::ordered_map<Key, T>& map, const unsigned int /* version */ ) {
auto serializer = [&ar]( const auto & v) { ar & v; };
map. serialize (serializer);
}
template < class Archive , class Key , class T >
void load (Archive & ar, tsl::ordered_map<Key, T>& map, const unsigned int /* version */ ) {
auto deserializer = [&ar]< typename U>() { U u; ar & u; return u; };
map = tsl::ordered_map<Key, T>:: deserialize (deserializer);
}
}}
int main () {
tsl::ordered_map<std:: int64_t , std:: int64_t > map = {{ 1 , - 1 }, { 2 , - 2 }, { 3 , - 3 }, { 4 , - 4 }};
const char * file_name = " ordered_map.data " ;
{
std::ofstream ofs;
ofs. exceptions (ofs. badbit | ofs. failbit );
ofs. open (file_name, std::ios::binary);
boost::iostreams::filtering_ostream fo;
fo. push ( boost::iostreams::zlib_compressor ());
fo. push (ofs);
boost::archive::binary_oarchive oa (fo);
oa << map;
}
{
std::ifstream ifs;
ifs. exceptions (ifs. badbit | ifs. failbit | ifs. eofbit );
ifs. open (file_name, std::ios::binary);
boost::iostreams::filtering_istream fi;
fi. push ( boost::iostreams::zlib_decompressor ());
fi. push (ifs);
boost::archive::binary_iarchive ia (fi);
tsl::ordered_map<std:: int64_t , std:: int64_t > map_deserialized;
ia >> map_deserialized;
assert (map == map_deserialized);
}
}El código tiene la licencia MIT; consulte el archivo LICENCIA para obtener más detalles.
