ordered map
v1.1.0
A biblioteca de mapas ordenados fornece um mapa hash e um conjunto de hash que preservam a ordem de inserção de maneira semelhante ao OrderedDict do Python. Ao iterar no mapa, os valores serão retornados na mesma ordem em que foram inseridos.
Os valores são armazenados de forma contígua em uma estrutura subjacente, sem lacunas entre os valores, mesmo após uma operação de apagamento. Por padrão, um std::deque é usado para esta estrutura, mas também é possível usar um std::vector . Esta estrutura é diretamente acessível através do método values_container() e se a estrutura for std::vector , um método data() também é fornecido para interagir facilmente com APIs C. Isso fornece iteração rápida, mas com a desvantagem de uma operação de apagamento O(bucket_count). As funções O(1) pop_back() e O(1) unordered_erase() estão disponíveis. Se o apagamento ordenado for usado com frequência, outra estrutura de dados é recomendada.
Para resolver colisões em hashes, a biblioteca usa sondagem Robin Hood linear com exclusão de deslocamento para trás.
A biblioteca fornece um comportamento semelhante a std::deque/std::vector com valores únicos, mas com uma complexidade de tempo média de O(1) para pesquisas e uma complexidade de tempo amortizada de O(1) para inserções. Isso tem o preço de um consumo de memória um pouco maior (8 bytes por bucket por padrão).
Duas classes são fornecidas: tsl::ordered_map e tsl::ordered_set .
Nota : A biblioteca usa uma potência de dois para o tamanho de sua matriz de buckets para aproveitar as vantagens do módulo rápido. Para um bom desempenho, é necessário que a tabela hash tenha uma função hash bem distribuída. Se você encontrar problemas de desempenho, verifique sua função hash.
tsl::ordered_map do CMakeLists.txt.std::unordered_map mas com inserções mais rápidas e uso de memória reduzido (consulte o benchmark para obter detalhes).find com um tipo diferente de Key (por exemplo, se você tiver um mapa que usa std::unique_ptr<foo> como chave, você pode usar um foo* ou um std::uintptr_t como parâmetro key para find sem construir um std::unique_ptr<foo> , veja o exemplo).precalculated_hash na API).serialize/deserialize na API para obter detalhes).-fno-exceptions no Clang e GCC, sem uma opção /EH no MSVC ou simplesmente definindo TSL_NO_EXCEPTIONS ). std::terminate é usado em substituição à instrução throw quando as exceções são desativadas.std::unordered_map e std::unordered_set .std::unordered_map tsl::ordered_map tenta ter uma interface semelhante a std::unordered_map , mas existem algumas diferenças.
RandomAccessIterator .std::vector e std::deque (consulte API para obter detalhes). Se você usar std::vector como ValueTypeContainer , poderá usar reserve() para pré-alocar algum espaço e evitar a invalidação dos iteradores na inserção.erase() lenta, tem uma complexidade de O (bucket_count). Existe uma versão O(1) mais rápida unordered_erase() , mas ela quebra o pedido de inserção (consulte a API para obter detalhes). Um O(1) pop_back() também está disponível.operator== e operator!= dependem da ordem. Dois tsl::ordered_map com os mesmos valores, mas inseridos em uma ordem diferente, não são iguais.operator*() e operator->() retornam uma referência e um ponteiro para const std::pair<Key, T> em vez de std::pair<const Key, T> tornando o valor T não modificável. Para modificar o valor você deve chamar o método value() do iterador para obter uma referência mutável. Exemplo: 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 ; verifique a API para obter detalhes.bucket_size , bucket , ...). A garantia de segurança de thread é igual a std::unordered_map (ou seja, é possível ter vários leitores simultâneos sem gravador).
Essas diferenças também se aplicam entre std::unordered_set e tsl::ordered_set .
Salvo menção em contrário, as funções têm a forte garantia de exceção, veja detalhes. Listamos abaixo os casos em que esta garantia não é prestada.
A garantia só é fornecida se ValueContainer::emplace_back tiver a garantia de exceção forte (o que é verdadeiro para std::vector e std::deque contanto que o tipo T não seja um tipo somente de movimentação com um construtor de movimentação que pode lançar um exceção, veja detalhes).
As funções tsl::ordered_map::erase_if e tsl::ordered_set::erase_if só têm garantia sob as pré-condições listadas em sua documentação.
Para usar o mapa ordenado, basta adicionar o diretório include ao seu caminho de inclusão. É uma biblioteca somente de cabeçalho .
Se você usar o CMake, também poderá usar o destino exportado tsl::ordered_map do CMakeLists.txt com 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) Se o projeto foi instalado por meio de make install , você também pode usar find_package(tsl-ordered-map REQUIRED) em vez de add_subdirectory .
O código deve funcionar com qualquer compilador compatível com o padrão C++ 11 e foi testado com GCC 4.8.4, Clang 3.5.0 e Visual Studio 2015.
Para executar os testes você precisará da biblioteca Boost Test e do 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 A API pode ser encontrada aqui.
# 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;
} Sobrecargas heterogêneas permitem o uso de outros tipos além de Key para operações de pesquisa e apagamento, desde que os tipos usados sejam hasháveis e comparáveis a Key .
Para ativar as sobrecargas heterogêneas em tsl::ordered_map/set , o ID qualificado KeyEqual::is_transparent deve ser válido. Funciona da mesma maneira que std::map::find . Você pode usar std::equal_to<> ou definir seu próprio objeto de função.
Tanto KeyEqual quanto Hash precisarão ser capazes de lidar com os 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;
} A biblioteca fornece uma maneira eficiente de serializar e desserializar um mapa ou conjunto para que ele possa ser salvo em um arquivo ou enviado pela rede. Para fazer isso, é necessário que o usuário forneça um objeto de função para serialização e desserialização.
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 ()();
};Observe que a implementação deixa a compatibilidade binária (endianness, representação binária flutuante, tamanho de int, ...) dos tipos que ela serializa/desserializa nas mãos dos objetos de função fornecidos, se a compatibilidade for necessária.
Mais detalhes sobre os métodos serialize e deserialize podem ser encontrados na 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);
}
} É possível usar uma biblioteca de serialização para evitar o clichê.
O exemplo a seguir usa Boost Serialization com o fluxo de compactação Boost zlib para reduzir o tamanho do arquivo serializado resultante. O exemplo requer C++20 devido ao uso da sintaxe da lista de parâmetros do modelo em lambdas, mas pode ser adaptado para versões menos recentes.
# 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);
}
}O código está licenciado sob a licença MIT, consulte o arquivo LICENSE para obter detalhes.
