ordered map
v1.1.0
Pustaka peta terurut menyediakan peta hash dan kumpulan hash yang mempertahankan urutan penyisipan dengan cara yang mirip dengan OrderedDict Python. Saat melakukan iterasi pada peta, nilai akan dikembalikan dalam urutan yang sama seperti saat dimasukkan.
Nilai-nilai disimpan secara berdekatan dalam struktur yang mendasarinya, tidak ada lubang di antara nilai-nilai bahkan setelah operasi penghapusan. Secara default, std::deque digunakan untuk struktur ini, tetapi std::vector juga dapat digunakan. Struktur ini dapat diakses langsung melalui metode values_container() dan jika strukturnya adalah std::vector , metode data() juga disediakan untuk berinteraksi dengan mudah dengan C API. Ini memberikan iterasi yang cepat tetapi dengan kelemahan operasi penghapusan O(bucket_count). Fungsi O(1) pop_back() dan O(1) unordered_erase() tersedia. Jika penghapusan berurutan sering digunakan, disarankan untuk menggunakan struktur data lain.
Untuk mengatasi tabrakan pada hash, perpustakaan menggunakan pemeriksaan Robin Hood linier dengan penghapusan shift mundur.
Pustaka menyediakan perilaku yang mirip dengan std::deque/std::vector dengan nilai unik tetapi dengan kompleksitas waktu rata-rata O(1) untuk pencarian dan kompleksitas waktu diamortisasi sebesar O(1) untuk penyisipan. Hal ini disebabkan oleh jejak memori yang sedikit lebih tinggi (8 byte per bucket secara default).
Dua kelas disediakan: tsl::ordered_map dan tsl::ordered_set .
Catatan : Pustaka menggunakan pangkat dua untuk ukuran susunan bucketnya guna memanfaatkan modulo cepat. Untuk kinerja yang baik, tabel hash memerlukan fungsi hash yang terdistribusi dengan baik. Jika Anda mengalami masalah kinerja, periksa fungsi hash Anda.
tsl::ordered_map dari CMakeLists.txt.std::unordered_map tetapi dengan penyisipan lebih cepat dan penggunaan memori lebih sedikit (lihat tolok ukur untuk detailnya).find dengan tipe yang berbeda dari Key (misalnya jika Anda memiliki peta yang menggunakan std::unique_ptr<foo> sebagai kunci, Anda dapat menggunakan foo* atau std::uintptr_t sebagai parameter kunci untuk find tanpa membuat std::unique_ptr<foo> , lihat contoh).precalculated_hash di API).serialize/deserialize di API untuk detailnya).-fno-exceptions di Clang dan GCC, tanpa opsi /EH di MSVC atau cukup dengan mendefinisikan TSL_NO_EXCEPTIONS ). std::terminate digunakan sebagai pengganti instruksi throw ketika pengecualian dinonaktifkan.std::unordered_map dan std::unordered_set .std::unordered_map tsl::ordered_map mencoba memiliki antarmuka yang mirip dengan std::unordered_map , tetapi ada beberapa perbedaan.
RandomAccessIterator .std::vector dan std::deque (lihat API untuk detailnya). Jika Anda menggunakan std::vector sebagai ValueTypeContainer , Anda dapat menggunakan reserve() untuk mengalokasikan sebagian ruang terlebih dahulu dan menghindari pembatalan iterator saat dimasukkan.erase() yang lambat, memiliki kompleksitas O(bucket_count). Ada versi O(1) yang lebih cepat unordered_erase() , tetapi merusak urutan penyisipan (lihat API untuk detailnya). O(1) pop_back() juga tersedia.operator== dan operator!= bergantung pada urutan. Dua tsl::ordered_map dengan nilai yang sama tetapi disisipkan dalam urutan berbeda tidak dapat dibandingkan sama.operator*() dan operator->() mengembalikan referensi dan pointer ke const std::pair<Key, T> alih-alih std::pair<const Key, T> membuat nilai T tidak dapat dimodifikasi. Untuk mengubah nilai, Anda harus memanggil metode value() dari iterator untuk mendapatkan referensi yang bisa diubah. Contoh: 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 , periksa API untuk detailnya.bucket_size , bucket , ...). Jaminan keamanan thread sama dengan std::unordered_map (yaitu dimungkinkan untuk memiliki beberapa pembaca secara bersamaan tanpa penulis).
Perbedaan ini juga berlaku antara std::unordered_set dan tsl::ordered_set .
Jika tidak disebutkan sebaliknya, fungsi memiliki jaminan pengecualian yang kuat, lihat detailnya. Di bawah ini kami mencantumkan kasus-kasus di mana jaminan ini tidak diberikan.
Jaminan hanya diberikan jika ValueContainer::emplace_back memiliki jaminan pengecualian yang kuat (yang berlaku untuk std::vector dan std::deque selama tipe T bukan tipe move-only dengan konstruktor move yang dapat memunculkan pengecualian, lihat detailnya).
Fungsi tsl::ordered_map::erase_if dan tsl::ordered_set::erase_if hanya memiliki jaminan berdasarkan prasyarat yang tercantum dalam dokumentasinya.
Untuk menggunakan peta yang dipesan, cukup tambahkan direktori penyertaan ke jalur penyertaan Anda. Ini adalah perpustakaan khusus header .
Jika Anda menggunakan CMake, Anda juga dapat menggunakan target yang diekspor tsl::ordered_map dari CMakeLists.txt dengan 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) Jika proyek telah diinstal melalui make install , Anda juga dapat menggunakan find_package(tsl-ordered-map REQUIRED) alih-alih add_subdirectory .
Kode ini harus bekerja dengan kompiler yang memenuhi standar C++11 dan telah diuji dengan GCC 4.8.4, Clang 3.5.0, dan Visual Studio 2015.
Untuk menjalankan pengujian, Anda memerlukan pustaka Boost Test dan 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 API dapat ditemukan di sini.
# 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;
} Kelebihan beban heterogen memungkinkan penggunaan tipe lain selain Key untuk operasi pencarian dan penghapusan selama tipe yang digunakan dapat di-hash dan sebanding dengan Key .
Untuk mengaktifkan kelebihan beban heterogen di tsl::ordered_map/set , ID yang memenuhi syarat KeyEqual::is_transparent harus valid. Cara kerjanya sama seperti untuk std::map::find . Anda dapat menggunakan std::equal_to<> atau menentukan objek fungsi Anda sendiri.
Baik KeyEqual dan Hash harus mampu menangani tipe yang berbeda.
# 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;
} Pustaka menyediakan cara yang efisien untuk membuat serialisasi dan deserialisasi peta atau kumpulan sehingga dapat disimpan ke file atau dikirim melalui jaringan. Untuk melakukannya, pengguna harus menyediakan objek fungsi untuk serialisasi dan deserialisasi.
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 ()();
};Perhatikan bahwa implementasinya meninggalkan kompatibilitas biner (endianness, representasi biner float, ukuran int, ...) dari tipe yang diserialkan/deserialisasi di tangan objek fungsi yang disediakan jika kompatibilitas diperlukan.
Detail lebih lanjut mengenai metode serialize dan deserialize dapat ditemukan di 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);
}
} Dimungkinkan untuk menggunakan perpustakaan serialisasi untuk menghindari boilerplate.
Contoh berikut menggunakan Boost Serialization dengan aliran kompresi Boost zlib untuk mengurangi ukuran file serial yang dihasilkan. Contoh ini memerlukan C++20 karena penggunaan sintaks daftar parameter templat di lambda, tetapi dapat disesuaikan ke versi yang lebih baru.
# 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);
}
}Kode ini dilisensikan di bawah lisensi MIT, lihat file LISENSI untuk detailnya.
