ordered map
v1.1.0
Die Ordered-Map-Bibliothek stellt eine Hash-Map und einen Hash-Satz bereit, die die Einfügereihenfolge auf ähnliche Weise wie Pythons OrderedDict beibehalten. Beim Durchlaufen der Karte werden die Werte in derselben Reihenfolge zurückgegeben, in der sie eingefügt wurden.
Die Werte werden zusammenhängend in einer zugrunde liegenden Struktur gespeichert, sodass auch nach einem Löschvorgang keine Lücken zwischen den Werten entstehen. Standardmäßig wird für diese Struktur ein std::deque verwendet, es ist jedoch auch möglich, einen std::vector zu verwenden. Auf diese Struktur kann direkt über die Methode values_container() zugegriffen werden. Wenn es sich bei der Struktur um einen std::vector , wird auch eine Methode data() bereitgestellt, um die einfache Interaktion mit C-APIs zu ermöglichen. Dies ermöglicht eine schnelle Iteration, hat jedoch den Nachteil einer O(bucket_count)-Löschoperation. Es stehen die Funktionen O(1) pop_back() und O(1) unordered_erase() zur Verfügung. Wenn häufig geordnetes Löschen verwendet wird, wird eine andere Datenstruktur empfohlen.
Um Kollisionen bei Hashes aufzulösen, verwendet die Bibliothek lineares Robin-Hood-Probing mit Rückwärtsverschiebungslöschung.
Die Bibliothek bietet ein Verhalten ähnlich einem std::deque/std::vector mit eindeutigen Werten, jedoch mit einer durchschnittlichen Zeitkomplexität von O(1) für Suchvorgänge und einer amortisierten Zeitkomplexität von O(1) für Einfügungen. Dies geht mit einem etwas höheren Speicherbedarf einher (standardmäßig 8 Byte pro Bucket).
Es werden zwei Klassen bereitgestellt: tsl::ordered_map und tsl::ordered_set .
Hinweis : Die Bibliothek verwendet eine Zweierpotenz für die Größe ihres Buckets-Arrays, um das schnelle Modulo zu nutzen. Für eine gute Leistung ist es erforderlich, dass die Hash-Tabelle über eine gut verteilte Hash-Funktion verfügt. Wenn Sie auf Leistungsprobleme stoßen, überprüfen Sie Ihre Hash-Funktion.
tsl::ordered_map aus CMakeLists.txt verwenden.std::unordered_map , jedoch mit schnelleren Einfügungen und reduzierter Speichernutzung (Einzelheiten siehe Benchmark).find mit einem anderen Typ als Key ermöglichen (z. B. wenn Sie eine Karte haben, die std::unique_ptr<foo> als Schlüssel verwendet, können Sie „ foo* oder std::uintptr_t als Schlüsselparameter verwenden find ohne einen std::unique_ptr<foo> zu konstruieren, siehe Beispiel).precalculated_hash in der API).serialize/deserialize in der API).-fno-exceptions auf Clang und GCC, ohne /EH -Option auf MSVC oder einfach durch Definition TSL_NO_EXCEPTIONS ). std::terminate wird als Ersatz für die throw -Anweisung verwendet, wenn Ausnahmen deaktiviert sind.std::unordered_map und std::unordered_set sehr ähnlich ist.std::unordered_map tsl::ordered_map versucht, eine ähnliche Schnittstelle wie std::unordered_map zu haben, es bestehen jedoch einige Unterschiede.
RandomAccessIterator .std::vector und std::deque (Einzelheiten finden Sie in der API). Wenn Sie std::vector als ValueTypeContainer verwenden, können Sie reserve() verwenden, um etwas Speicherplatz vorab zuzuweisen und die Ungültigmachung der Iteratoren beim Einfügen zu vermeiden.erase() Operation, sie hat eine Komplexität von O(bucket_count). Es gibt eine schnellere O(1)-Version unordered_erase() , die jedoch die Einfügereihenfolge unterbricht (Einzelheiten finden Sie in der API). Ein O(1) pop_back() ist ebenfalls verfügbar.operator== und operator!= sind reihenfolgeabhängig. Zwei tsl::ordered_map mit denselben Werten, die jedoch in einer anderen Reihenfolge eingefügt werden, sind nicht gleich.operator*() und operator->() eine Referenz und einen Zeiger auf const std::pair<Key, T> anstelle von std::pair<const Key, T> zurück, wodurch der Wert T nicht geändert werden kann. Um den Wert zu ändern, müssen Sie die value() Methode des Iterators aufrufen, um eine veränderbare Referenz zu erhalten. Beispiel: 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 ausgelöst werden. Weitere Informationen finden Sie in der API.bucket_size , bucket , ...). Die Thread-Sicherheitsgarantie ist dieselbe wie bei std::unordered_map (dh es ist möglich, mehrere gleichzeitige Leser ohne Schreiber zu haben).
Diese Unterschiede gelten auch zwischen std::unordered_set und tsl::ordered_set .
Sofern nicht anders angegeben, verfügen Funktionen über die starke Ausnahmegarantie, siehe Details. Im Folgenden führen wir Fälle auf, in denen diese Garantie nicht gegeben ist.
Die Garantie wird nur bereitgestellt, wenn ValueContainer::emplace_back über die starke Ausnahmegarantie verfügt (was für std::vector und std::deque gilt, solange der Typ T kein reiner Verschiebungstyp mit einem Verschiebungskonstruktor ist, der eine auslösen kann Ausnahme, siehe Details).
Die Funktionen tsl::ordered_map::erase_if und tsl::ordered_set::erase_if haben die Garantie nur unter den in ihrer Dokumentation aufgeführten Voraussetzungen.
Um ordered-map zu verwenden, fügen Sie einfach das Include-Verzeichnis zu Ihrem Include-Pfad hinzu. Es handelt sich um eine reine Header- Bibliothek.
Wenn Sie CMake verwenden, können Sie auch das exportierte Ziel tsl::ordered_map aus CMakeLists.txt mit target_link_libraries verwenden.
# 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) Wenn das Projekt über make install installiert wurde, können Sie auch find_package(tsl-ordered-map REQUIRED) anstelle von add_subdirectory verwenden.
Der Code sollte mit jedem C++11-Standard-kompatiblen Compiler funktionieren und wurde mit GCC 4.8.4, Clang 3.5.0 und Visual Studio 2015 getestet.
Zum Ausführen der Tests benötigen Sie die Boost-Testbibliothek und 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 Die API finden Sie hier.
# 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;
} Heterogene Überladungen ermöglichen die Verwendung anderer Typen als Key für Such- und Löschvorgänge, sofern die verwendeten Typen hashbar und mit Key vergleichbar sind.
Um die heterogenen Überladungen in tsl::ordered_map/set zu aktivieren, muss die qualifizierte ID KeyEqual::is_transparent gültig sein. Es funktioniert genauso wie für std::map::find . Sie können entweder std::equal_to<> verwenden oder Ihr eigenes Funktionsobjekt definieren.
Sowohl KeyEqual als auch Hash müssen in der Lage sein, mit den verschiedenen Typen umzugehen.
# 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;
} Die Bibliothek bietet eine effiziente Möglichkeit, eine Karte oder einen Satz zu serialisieren und zu deserialisieren, sodass er in einer Datei gespeichert oder über das Netzwerk gesendet werden kann. Dazu muss der Benutzer ein Funktionsobjekt sowohl für die Serialisierung als auch für die Deserialisierung bereitstellen.
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 ()();
};Beachten Sie, dass die Implementierung die binäre Kompatibilität (Endianness, Float-Binärdarstellung, Größe von int, ...) der Typen, die sie serialisiert/deserialisiert, den bereitgestellten Funktionsobjekten überlässt, wenn Kompatibilität erforderlich ist.
Weitere Details zu den serialize und deserialize finden Sie in der 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 ist möglich, eine Serialisierungsbibliothek zu verwenden, um das Boilerplate zu vermeiden.
Im folgenden Beispiel wird die Boost-Serialisierung mit dem Boost-zlib-Komprimierungsstream verwendet, um die Größe der resultierenden serialisierten Datei zu reduzieren. Das Beispiel erfordert C++20 aufgrund der Verwendung der Template-Parameterlistensyntax in Lambdas, kann aber an weniger aktuelle Versionen angepasst werden.
# 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);
}
}Der Code ist unter der MIT-Lizenz lizenziert. Weitere Informationen finden Sie in der LICENSE-Datei.
