ordered map
v1.1.0
La bibliothèque de cartes ordonnées fournit une carte de hachage et un jeu de hachage qui préservent l'ordre d'insertion d'une manière similaire à OrderedDict de Python. Lors d'une itération sur la carte, les valeurs seront renvoyées dans le même ordre que celui dans lequel elles ont été insérées.
Les valeurs sont stockées de manière contiguë dans une structure sous-jacente, sans trous entre les valeurs, même après une opération d'effacement. Par défaut, un std::deque est utilisé pour cette structure, mais il est également possible d'utiliser un std::vector . Cette structure est directement accessible via la méthode values_container() et si la structure est un std::vector , une méthode data() est également fournie pour interagir facilement avec les API C. Cela permet une itération rapide mais avec l'inconvénient d'une opération d'effacement O(bucket_count). Une fonction O(1) pop_back() et une fonction O(1) unordered_erase() sont disponibles. Si l'effacement ordonné est souvent utilisé, une autre structure de données est recommandée.
Pour résoudre les collisions sur les hachages, la bibliothèque utilise un sondage linéaire Robin des Bois avec suppression par décalage vers l'arrière.
La bibliothèque fournit un comportement similaire à un std::deque/std::vector avec des valeurs uniques mais avec une complexité temporelle moyenne de O(1) pour les recherches et une complexité temporelle amortie de O(1) pour les insertions. Cela se fait au prix d’une empreinte mémoire un peu plus élevée (8 octets par compartiment par défaut).
Deux classes sont fournies : tsl::ordered_map et tsl::ordered_set .
Remarque : La bibliothèque utilise une puissance de deux pour la taille de son tableau de buckets afin de profiter du modulo rapide. Pour de bonnes performances, il faut que la table de hachage ait une fonction de hachage bien distribuée. Si vous rencontrez des problèmes de performances, vérifiez votre fonction de hachage.
tsl::ordered_map à partir du fichier CMakeLists.txt.std::unordered_map mais avec des insertions plus rapides et une utilisation de la mémoire réduite (voir le benchmark pour plus de détails).find avec un type différent de Key (par exemple, si vous avez une carte qui utilise std::unique_ptr<foo> comme clé, vous pouvez utiliser un foo* ou un std::uintptr_t comme paramètre de clé pour find sans construire un std::unique_ptr<foo> , voir exemple).precalculated_hash dans l'API).serialize/deserialize dans l'API pour plus de détails).-fno-exceptions sur Clang et GCC, sans option /EH sur MSVC ou simplement en définissant TSL_NO_EXCEPTIONS ). std::terminate est utilisé en remplacement de l'instruction throw lorsque les exceptions sont désactivées.std::unordered_map et std::unordered_set .std::unordered_map tsl::ordered_map essaie d'avoir une interface similaire à std::unordered_map , mais certaines différences existent.
RandomAccessIterator .std::vector et std::deque (voir API pour plus de détails). Si vous utilisez std::vector comme ValueTypeContainer , vous pouvez utiliser reserve() pour pré-allouer de l'espace et éviter l'invalidation des itérateurs lors de l'insertion.erase() , elle a une complexité de O (bucket_count). Une version O(1) plus rapide, unordered_erase() existe, mais elle rompt l'ordre d'insertion (voir API pour plus de détails). Un O(1) pop_back() est également disponible.operator== et operator!= dépendent de l'ordre. Deux tsl::ordered_map avec les mêmes valeurs mais insérés dans un ordre différent ne sont pas comparables.operator*() et operator->() renvoient une référence et un pointeur vers const std::pair<Key, T> au lieu de std::pair<const Key, T> rendant la valeur T non modifiable. Pour modifier la valeur, vous devez appeler la méthode value() de l'itérateur pour obtenir une référence mutable. Exemple: 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 , consultez l'API pour plus de détails.bucket_size , bucket , ...). La garantie de sécurité des threads est la même que celle std::unordered_map (c'est-à-dire qu'il est possible d'avoir plusieurs lecteurs simultanés sans écrivain).
Ces différences s'appliquent également entre std::unordered_set et tsl::ordered_set .
Sauf indication contraire, les fonctions bénéficient de la forte garantie d'exception, voir détails. Nous énumérons ci-dessous les cas dans lesquels cette garantie n'est pas fournie.
La garantie n'est fournie que si ValueContainer::emplace_back a la forte garantie d'exception (ce qui est vrai pour std::vector et std::deque tant que le type T n'est pas un type de déplacement uniquement avec un constructeur de déplacement qui peut lancer un exception, voir détails).
Les fonctions tsl::ordered_map::erase_if et tsl::ordered_set::erase_if n'ont la garantie que dans les conditions préalables listées dans leur documentation.
Pour utiliser la carte ordonnée, ajoutez simplement le répertoire d'inclusion à votre chemin d'inclusion. Il s'agit d'une bibliothèque d'en-tête uniquement .
Si vous utilisez CMake, vous pouvez également utiliser la cible exportée tsl::ordered_map à partir du CMakeLists.txt avec 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 le projet a été installé via make install , vous pouvez également utiliser find_package(tsl-ordered-map REQUIRED) au lieu de add_subdirectory .
Le code doit fonctionner avec n'importe quel compilateur conforme à la norme C++ 11 et a été testé avec GCC 4.8.4, Clang 3.5.0 et Visual Studio 2015.
Pour exécuter les tests, vous aurez besoin de la bibliothèque Boost Test et de 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 L'API peut être trouvée ici.
# 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;
} Les surcharges hétérogènes permettent l'utilisation d'autres types que Key pour les opérations de recherche et d'effacement tant que les types utilisés sont hachables et comparables à Key .
Pour activer les surcharges hétérogènes dans tsl::ordered_map/set , l'identifiant qualifié KeyEqual::is_transparent doit être valide. Cela fonctionne de la même manière que pour std::map::find . Vous pouvez soit utiliser std::equal_to<> , soit définir votre propre objet fonction.
KeyEqual et Hash devront être capables de gérer les différents types.
# 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 bibliothèque fournit un moyen efficace de sérialiser et de désérialiser une carte ou un ensemble afin qu'il puisse être enregistré dans un fichier ou envoyé via le réseau. Pour ce faire, l'utilisateur doit fournir un objet fonction pour la sérialisation et la désérialisation.
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 ()();
};Notez que l'implémentation laisse la compatibilité binaire (endianisme, représentation binaire flottante, taille de int, ...) des types qu'elle sérialise/désérialise entre les mains des objets fonction fournis si la compatibilité est requise.
Plus de détails concernant les méthodes serialize et deserialize peuvent être trouvés dans l'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);
}
} Il est possible d'utiliser une bibliothèque de sérialisation pour éviter le passe-partout.
L'exemple suivant utilise Boost Serialization avec le flux de compression Boost zlib pour réduire la taille du fichier sérialisé résultant. L'exemple nécessite C++20 en raison de l'utilisation de la syntaxe de liste de paramètres de modèle dans lambdas, mais il peut être adapté à des versions moins récentes.
# 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);
}
}Le code est sous licence MIT, voir le fichier LICENSE pour plus de détails.
