ordered map
v1.1.0
ไลบรารี Ordered-map มีแผนที่แฮชและชุดแฮชซึ่งรักษาลำดับการแทรกในลักษณะที่คล้ายกับ OrderedDict ของ Python เมื่อวนซ้ำบนแผนที่ ค่าจะถูกส่งกลับในลำดับเดียวกับที่แทรกไว้
ค่าจะถูกจัดเก็บต่อเนื่องกันในโครงสร้างพื้นฐาน โดยไม่มีช่องว่างระหว่างค่าแม้หลังจากการดำเนินการลบแล้วก็ตาม ตามค่าเริ่มต้น std::deque จะถูกใช้สำหรับโครงสร้างนี้ แต่ก็เป็นไปได้ที่จะใช้ std::vector เช่นกัน โครงสร้างนี้สามารถเข้าถึงได้โดยตรงผ่านเมธอด values_container() และหากโครงสร้างเป็น std::vector ก็จะมีการจัดเตรียมเมธอด data() เพื่อให้โต้ตอบกับ C API ได้อย่างง่ายดาย ซึ่งให้การวนซ้ำที่รวดเร็ว แต่มีข้อเสียเปรียบของการดำเนินการลบ O(bucket_count) มีฟังก์ชัน O(1) pop_back() และ O(1) unordered_erase() หากมีการใช้คำสั่งลบบ่อยครั้ง แนะนำให้ใช้โครงสร้างข้อมูลอื่น
เพื่อแก้ไขการชนกันของแฮช ไลบรารีจะใช้การตรวจสอบโรบินฮู้ดเชิงเส้นพร้อมการลบการเลื่อนแบบย้อนกลับ
ไลบรารีมีพฤติกรรมที่คล้ายกับ std::deque/std::vector ที่มีค่าไม่ซ้ำกัน แต่มีความซับซ้อนของเวลาโดยเฉลี่ย O(1) สำหรับการค้นหา และความซับซ้อนของเวลาตัดจำหน่าย O(1) สำหรับการแทรก ซึ่งมาพร้อมกับราคาของพื้นที่หน่วยความจำที่สูงขึ้นเล็กน้อย (8 ไบต์ต่อที่ฝากข้อมูลตามค่าเริ่มต้น)
มีคลาสสองคลาส: tsl::ordered_map และ tsl::ordered_set
หมายเหตุ : ไลบรารีใช้กำลังสองสำหรับขนาดของอาร์เรย์บัคเก็ตเพื่อใช้ประโยชน์จากโมดูโลที่รวดเร็ว เพื่อการแสดงที่ดี ตารางแฮชจะต้องมีฟังก์ชันแฮชที่กระจายอย่างดี หากคุณประสบปัญหาด้านประสิทธิภาพ ให้ตรวจสอบฟังก์ชันแฮชของคุณ
tsl::ordered_map จาก CMakeLists.txt ได้อีกด้วยstd::unordered_map แต่มีการแทรกที่เร็วกว่าและลดการใช้หน่วยความจำ (ดูรายละเอียดเกณฑ์มาตรฐาน)find ด้วยประเภทที่แตกต่างจาก Key (เช่น หากคุณมีแผนที่ที่ใช้ std::unique_ptr<foo> เป็นคีย์ คุณสามารถใช้ foo* หรือ std::uintptr_t เป็นพารามิเตอร์คีย์เพื่อ find โดยไม่ต้องสร้าง std::unique_ptr<foo> ดูตัวอย่าง)precalculated_hash ใน API)serialize/deserialize ใน API สำหรับรายละเอียด)-fno-exceptions บน Clang และ GCC โดยไม่มีตัวเลือก /EH บน MSVC หรือเพียงแค่กำหนด TSL_NO_EXCEPTIONS ) std::terminate ใช้แทนคำสั่ง throw เมื่อข้อยกเว้นถูกปิดใช้งานstd::unordered_map และ std::unordered_set อย่างใกล้ชิดstd::unordered_map tsl::ordered_map พยายามที่จะมีส่วนต่อประสานที่คล้ายกับ std::unordered_map แต่มีความแตกต่างบางประการ
RandomAccessIteratorstd::vector และ std::deque (ดู API สำหรับรายละเอียด) หากคุณใช้ std::vector เป็น ValueTypeContainer คุณสามารถใช้ reserve() เพื่อจัดสรรพื้นที่ล่วงหน้าและหลีกเลี่ยงการทำให้ตัววนซ้ำบนส่วนแทรกเป็นโมฆะerase() มีความซับซ้อนเท่ากับ O (bucket_count) มีเวอร์ชัน O(1) ที่เร็วกว่า unordered_erase() แต่จะทำลายลำดับการแทรก (ดู API สำหรับรายละเอียด) นอกจากนี้ยังมี O(1) pop_back() อีกด้วยoperator== และ operator!= ขึ้นอยู่กับลำดับ tsl::ordered_map สองรายการที่มีค่าเดียวกันแต่แทรกในลำดับอื่นเปรียบเทียบกันไม่เท่ากันoperator*() และ operator->() ส่งคืนการอ้างอิงและตัวชี้ไปที่ const std::pair<Key, T> แทน std::pair<const Key, T> ทำให้ค่า T ไม่สามารถแก้ไขได้ ในการแก้ไขค่าคุณต้องเรียกใช้เมธอด value() ของตัววนซ้ำเพื่อรับการอ้างอิงที่ไม่แน่นอน ตัวอย่าง: 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 โปรดตรวจสอบ API เพื่อดูรายละเอียดbucket_size , bucket , ... ) การรับประกันความปลอดภัยของเธรดจะเหมือนกับ std::unordered_map (เช่น เป็นไปได้ที่จะมีตัวอ่านหลายตัวพร้อมกันโดยไม่มีตัวเขียน)
ความแตกต่างเหล่านี้ยังใช้ระหว่าง std::unordered_set และ tsl::ordered_set
หากไม่ได้กล่าวถึงเป็นอย่างอื่น ฟังก์ชันจะมีการรับประกันข้อยกเว้นที่เข้มงวด โปรดดูรายละเอียด เราแสดงรายการกรณีที่ไม่ได้ให้การรับประกันนี้ไว้ด้านล่าง
การรับประกันจะมีให้เฉพาะในกรณีที่ ValueContainer::emplace_back มีการรับประกันข้อยกเว้นที่เข้มงวด (ซึ่งเป็นจริงสำหรับ std::vector และ std::deque ตราบใดที่ประเภท T ไม่ใช่ประเภทการย้ายอย่างเดียวที่มีตัวสร้างการย้ายที่อาจโยน ข้อยกเว้น โปรดดูรายละเอียด)
ฟังก์ชัน tsl::ordered_map::erase_if และ tsl::ordered_set::erase_if มีการรับประกันภายใต้เงื่อนไขเบื้องต้นที่ระบุไว้ในเอกสารประกอบเท่านั้น
หากต้องการใช้ orderd-map เพียงเพิ่มไดเร็กทอรีรวมลงในพาธรวมของคุณ มันเป็นห้องสมุด ส่วนหัวเท่านั้น
หากคุณใช้ CMake คุณยังสามารถใช้เป้าหมายที่ส่งออก tsl::ordered_map จาก CMakeLists.txt พร้อมด้วย 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) หากโปรเจ็กต์ได้รับการติดตั้งผ่าน make install คุณยังสามารถใช้ find_package(tsl-ordered-map REQUIRED) แทน add_subdirectory
รหัสควรทำงานร่วมกับคอมไพเลอร์มาตรฐาน C++11 และได้รับการทดสอบกับ GCC 4.8.4, Clang 3.5.0 และ Visual Studio 2015
หากต้องการรันการทดสอบ คุณจะต้องมีไลบรารี Boost Test และ 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 สามารถพบได้ที่นี่
# 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;
} การโอเวอร์โหลดที่แตกต่างกันทำให้สามารถใช้ประเภทอื่นนอกเหนือจาก Key ในการค้นหาและลบได้ ตราบใดที่ประเภทที่ใช้นั้นสามารถแฮชได้และเทียบเคียงได้กับ Key
หากต้องการเปิดใช้งานโอเวอร์โหลดต่างกันใน tsl::ordered_map/set รหัสที่ผ่านการรับรอง KeyEqual::is_transparent จะต้องถูกต้อง มันทำงานในลักษณะเดียวกับ std::map::find คุณสามารถใช้ std::equal_to<> หรือกำหนดวัตถุฟังก์ชันของคุณเองได้
ทั้ง KeyEqual และ Hash จะต้องสามารถจัดการกับประเภทที่แตกต่างกันได้
# 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;
} ไลบรารีจัดเตรียมวิธีที่มีประสิทธิภาพในการซีเรียลไลซ์และดีซีเรียลไลซ์แผนที่หรือชุด เพื่อให้สามารถบันทึกเป็นไฟล์หรือส่งผ่านเครือข่าย ในการทำเช่นนั้น ผู้ใช้จำเป็นต้องจัดเตรียมออบเจ็กต์ฟังก์ชันสำหรับทั้งซีเรียลไลซ์เซชันและดีซีเรียลไลซ์เซชัน
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 ()();
};โปรดทราบว่าการใช้งานจะทิ้งความเข้ากันได้แบบไบนารี (endianness, การแทนไบนารีแบบลอยตัว, ขนาดของ int, ...) ของประเภทที่ทำให้เป็นอนุกรม/ดีซีเรียลไลซ์อยู่ในมือของออบเจ็กต์ฟังก์ชันที่ให้มา หากจำเป็นต้องมีความเข้ากันได้
รายละเอียดเพิ่มเติมเกี่ยวกับวิธี serialize และ deserialize มีอยู่ใน 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);
}
} คุณสามารถใช้ไลบรารีการทำให้เป็นซีเรียลไลซ์ได้เพื่อหลีกเลี่ยงไม่ให้มีการสร้างซีเรียลไลซ์
ตัวอย่างต่อไปนี้ใช้ Boost Serialization พร้อมกับสตรีมการบีบอัด Boost zlib เพื่อลดขนาดของไฟล์ซีเรียลไลซ์ที่ได้ ตัวอย่างต้องใช้ C++20 เนื่องจากการใช้ไวยากรณ์รายการพารามิเตอร์เทมเพลตใน lambdas แต่สามารถปรับให้เข้ากับเวอร์ชันล่าสุดได้
# 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);
}
}รหัสนี้ได้รับอนุญาตภายใต้ใบอนุญาต MIT โปรดดูรายละเอียดในไฟล์ LICENSE
