การใช้งาน Trie ตาม "HAT-trie: โครงสร้างข้อมูลแบบ Trie ที่คำนึงถึงแคชสำหรับสตริง" (Askitis Nikolas และ Sinha Ranjan, 2007) กระดาษ สำหรับตอนนี้ มีเพียง HAT-trie ล้วนเท่านั้นที่ถูกนำมาใช้ ส่วนเวอร์ชันไฮบริดอาจมาถึงในภายหลัง รายละเอียดเกี่ยวกับโครงสร้างข้อมูล HAT-trie สามารถพบได้ที่นี่
ไลบรารีจัดเตรียมวิธีที่มีประสิทธิภาพและกะทัดรัดในการจัดเก็บชุดหรือแมปของสตริงโดยการบีบอัดคำนำหน้าทั่วไป นอกจากนี้ยังช่วยให้สามารถค้นหาคีย์ที่ตรงกับคำนำหน้าได้ โปรดทราบว่าพารามิเตอร์เริ่มต้นของโครงสร้างมุ่งไปที่การปรับการค้นหาให้เหมาะสมที่สุด หากคุณค้นหาคำนำหน้าหลายครั้ง คุณอาจต้องการลดเกณฑ์การระเบิดโดยใช้เมธอด burst_threshold
เป็นโครงสร้างที่ดัดแปลงมาอย่างดีเพื่อเก็บสายได้จำนวนมาก
สำหรับส่วนแฮชของอาเรย์นั้น โปรเจ็กต์อาเรย์แฮชจะถูกใช้และรวมไว้ในที่เก็บ
ไลบรารีมีสองคลาส: tsl::htrie_map
และ tsl::htrie_set
tsl::hat_trie
จาก CMakeLists.txt ได้อีกด้วยequal_prefix_range
(มีประโยชน์สำหรับการเติมข้อความอัตโนมัติ เป็นต้น) และการลบคำนำหน้าผ่าน erase_prefix
longest_prefix
serialize/deserialize
ใน API สำหรับรายละเอียด)max_load_factor
ค่าโหลดสูงสุดที่ต่ำกว่าจะเพิ่มความเร็ว ส่วนค่าที่สูงกว่าจะลดการใช้หน่วยความจำ ค่าเริ่มต้นตั้งไว้ที่ 8.0burst_threshold
KeySizeT
การรับประกันความปลอดภัยของเธรดและข้อยกเว้นจะคล้ายกับคอนเทนเนอร์ STL
ฟังก์ชันแฮชเริ่มต้นที่ใช้โดยโครงสร้างขึ้นอยู่กับการมีอยู่ของ std::string_view
หากมีให้ใช้ std::hash<std::string_view>
มิฉะนั้นจะใช้ฟังก์ชันแฮช FNV-1a แบบธรรมดาเพื่อหลีกเลี่ยงการขึ้นต่อกันใดๆ
หากคุณไม่สามารถใช้ C++17 หรือใหม่กว่าได้ เราขอแนะนำให้แทนที่ฟังก์ชันแฮชด้วยฟังก์ชันเช่น CityHash, MurmurHash, FarmHash, ... เพื่อประสิทธิภาพที่ดีขึ้น จากการทดสอบที่เราทำ CityHash64 มีการปรับปรุงการอ่านประมาณ 20% เมื่อเทียบกับ FNV-1a
# include < city.h >
struct str_hash {
std:: size_t operator ()( const char * key, std:: size_t key_size) const {
return CityHash64 (key, key_size);
}
};
tsl::htrie_map< char , int , str_hash> map;
std::hash<std::string>
ไม่สามารถใช้งานได้อย่างมีประสิทธิภาพเนื่องจากโครงสร้างไม่ได้เก็บวัตถุ std::string
ใด ๆ เมื่อใดก็ตามที่จำเป็นต้องใช้แฮช จะต้องสร้าง std::string
ชั่วคราว
การวัดประสิทธิภาพประกอบด้วยการแทรกชื่อเรื่องทั้งหมดจากเนมสเปซหลักของไฟล์เก็บถาวร Wikipedia ลงในโครงสร้างข้อมูล ตรวจสอบพื้นที่หน่วยความจำที่ใช้หลังจากการแทรก (รวมถึงการกระจายตัวของหน่วยความจำที่อาจเกิดขึ้น) และค้นหาชื่อเรื่องทั้งหมดอีกครั้งในโครงสร้างข้อมูล การใช้งานหน่วยความจำสูงสุดในระหว่างกระบวนการแทรกจะถูกวัดตามเวลาด้วย (1)
แต่ละชื่อเชื่อมโยงกับ int (32 บิต) โครงสร้างแบบแฮชทั้งหมดใช้ CityHash64 เป็นฟังก์ชันแฮช สำหรับการทดสอบที่ทำเครื่องหมาย ด้วย Reserve ฟังก์ชัน reserve
จะถูกเรียกล่วงหน้าเพื่อหลีกเลี่ยงการทำใหม่
โปรดทราบว่า tsl::hopscotch_map
, std::unordered_map
, google::dense_hash_map
และ spp::sparse_hash_map
ใช้ std::string
เป็นคีย์ซึ่งกำหนดขนาดขั้นต่ำ 32 ไบต์ (บน x64) แม้ว่าคีย์จะมีความยาวเพียงอักขระเดียวก็ตาม โครงสร้างอื่นอาจสามารถจัดเก็บคีย์หนึ่งอักขระที่มี 1 ไบต์ + 8 ไบต์สำหรับตัวชี้ (บน x64)
เกณฑ์มาตรฐานได้รับการรวบรวมด้วย GCC 6.3 และทำงานบน Debian Stretch x64 พร้อมด้วย Intel i5-5200u และ RAM 8Go ดำเนินการดีที่สุดจาก 20 ครั้ง
รหัสของเกณฑ์มาตรฐานสามารถพบได้ใน Gist
ชุดข้อมูล enwiki-20170320-all-titles-in-ns0.gz จะถูกจัดเรียงตามตัวอักษร สำหรับการวัดประสิทธิภาพนี้ ก่อนอื่นเราจะสับเปลี่ยนชุดข้อมูลผ่าน shuf(1) เพื่อหลีกเลี่ยงไม่ให้ชุดข้อมูลที่เรียงลำดับมีอคติ
ห้องสมุด | โครงสร้างข้อมูล | หน่วยความจำสูงสุด (MiB) | หน่วยความจำ (MiB) | แทรก (ns/คีย์) | อ่าน (ns/คีย์) |
---|---|---|---|---|---|
tsl::htrie_map | แฮท-ทรี | 405.22 | 402.25 | 643.10 | 250.87 |
tsl::htrie_map max_load_factor=4 | แฮท-ทรี | 471.85 | 468.50 | 638.66 | 212.90 |
tsl::htrie_map max_load_factor=2 | แฮท-ทรี | 569.76 | 566.52 | 630.61 | 201.10 |
tsl::htrie_map max_load_factor=1 | แฮท-ทรี | 713.44 | 709.81 | 645.76 | 190.87 |
ซีดาร์::ดา | ไตรอาเรย์คู่ | 1269.68 | 1254.41 | 1102.93 | 557.20 |
ซีดาร์::ดาสั่ง=เท็จ | ไตรอาเรย์คู่ | 1269.80 | 1254.41 | 1,089.78 | 570.13 |
ซีดาร์::ดา | อาร์เรย์คู่ลดไตร | 1183.07 | 1167.79 | 1,076.68 | 645.79 |
ซีดาร์::ดาสั่ง=เท็จ | อาร์เรย์คู่ลดไตร | 1183.14 | 1167.85 | 1,065.43 | 641.98 |
ซีดาร์::ดา | คำนำหน้าอาร์เรย์คู่ | 498.69 | 496.54 | 1,096.90 | 628.01 |
ซีดาร์::ดาสั่ง=เท็จ | คำนำหน้าอาร์เรย์คู่ | 498.65 | 496.60 | 1,048.40 | 628.94 |
แฮตทรี 1 (C) | แฮท-ทรี | 504.07 | 501.50 | 917.49 | 261.00 |
คิวพี ทรี (C) | คิวพี ทรี | 941.23 | 938.17 | 1349.25 | 1281.46 |
คริตบิตไตร (C) | คริติคอลบิต | 1,074.96 | 1,071.98 | 2930.42 | 2869.74 |
จูดี้เอสแอล (C) | จูดี้ อาเรย์ | 631.09 | 628.37 | 884.29 | 803.58 |
จูดี้เอชเอส (C) | จูดี้ อาเรย์ | 723.44 | 719.47 | 476.79 | 417.15 |
tsl::array_map | ตารางแฮชอาร์เรย์ | 823.54 | 678.73 | 603.94 | 138.24 |
tsl::array_map พร้อมสำรอง | ตารางแฮชอาร์เรย์ | 564.26 | 555.91 | 249.52 | 128.28 |
tsl::hopscotch_map | ตารางแฮช | 1325.83 | 1,077.99 | 368.26 | 119.49 |
tsl::hopscotch_map พร้อมสำรอง | ตารางแฮช | 1,080.51 | 1,077.98 | 240.58 | 119.91 |
google::dense_hash_map | ตารางแฮช | 2319.40 | 1677.11 | 466.60 | 138.87 |
google::dense_hash_map พร้อมสำรอง | ตารางแฮช | 1592.51 | 1589.99 | 259.56 | 120.40 |
เอสพีพี::sparse_hash_map | ตารางแฮชกระจัดกระจาย | 918.67 | 917.10 | 769.00 | 175.59 |
เอสพีพี::sparse_hash_map พร้อมสำรอง | ตารางแฮชกระจัดกระจาย | 913.35 | 910.65 | 427.22 | 159.08 |
มาตรฐาน::unordered_map | ตารางแฮช | 1249.05 | 1246.60 | 590.88 | 173.58 |
มาตรฐาน::unordered_map พร้อมสำรอง | ตารางแฮช | 1212.23 | 1209.71 | 350.33 | 178.70 |
คีย์จะถูกแทรกและอ่านตามลำดับตัวอักษร
ห้องสมุด | โครงสร้างข้อมูล | หน่วยความจำสูงสุด (MiB) | หน่วยความจำ (MiB) | แทรก (ns/คีย์) | อ่าน (ns/คีย์) |
---|---|---|---|---|---|
tsl::htrie_map | แฮท-ทรี | 396.10 | 393.22 | 255.76 | 68.08 |
tsl::htrie_map max_load_factor=4 | แฮท-ทรี | 465.02 | 461.80 | 248.88 | 59.23 |
tsl::htrie_map max_load_factor=2 | แฮท-ทรี | 543.99 | 541.21 | 230.13 | 53.50 |
tsl::htrie_map max_load_factor=1 | แฮท-ทรี | 692.29 | 689.70 | 243.84 | 49.22 |
ซีดาร์::ดา | ไตรอาเรย์คู่ | 1269.58 | 1254.41 | 278.51 | 54.72 |
ซีดาร์::ดาสั่ง=เท็จ | ไตรอาเรย์คู่ | 1269.66 | 1254.41 | 264.43 | 56.02 |
ซีดาร์::ดา | อาร์เรย์คู่ลดไตร | 1183.01 | 1167.78 | 254.60 | 69.18 |
ซีดาร์::ดาสั่ง=เท็จ | อาร์เรย์คู่ลดไตร | 1183.03 | 1167.78 | 241.45 | 69.67 |
ซีดาร์::ดา | คำนำหน้าอาร์เรย์คู่ | 621.59 | 619.38 | 246.88 | 57.83 |
ซีดาร์::ดาสั่ง=เท็จ | คำนำหน้าอาร์เรย์คู่ | 621.59 | 619.38 | 187.98 | 58.56 |
แฮตทรี 2 (C) | แฮท-ทรี | 521.25 | 518.52 | 503.01 | 86.40 |
คิวพี ทรี (C) | คิวพี ทรี | 940.65 | 937.66 | 392.86 | 190.19 |
คริตบิตไตร (C) | คริติคอลบิต | 1,074.87 | 1,071.98 | 430.04 | 347.60 |
จูดี้เอสแอล (C) | จูดี้ อาเรย์ | 616.95 | 614.27 | 279.07 | 114.47 |
จูดี้เอชเอส (C) | จูดี้ อาเรย์ | 722.29 | 719.47 | 439.66 | 372.25 |
tsl::array_map | ตารางแฮชอาร์เรย์ | 826.98 | 682.99 | 612.31 | 139.16 |
tsl::array_map พร้อมสำรอง | ตารางแฮชอาร์เรย์ | 565.37 | 555.35 | 246.55 | 126.32 |
tsl::hopscotch_map | ตารางแฮช | 1331.87 | 1,078.02 | 375.19 | 118.08 |
tsl::hopscotch_map พร้อมสำรอง | ตารางแฮช | 1,080.51 | 1,077.97 | 238.93 | 117.20 |
google::dense_hash_map | ตารางแฮช | 2325.27 | 1683.07 | 483.95 | 137.09 |
google::dense_hash_map พร้อมสำรอง | ตารางแฮช | 1592.54 | 1589.99 | 257.22 | 113.71 |
เอสพีพี::sparse_hash_map | ตารางแฮชกระจัดกระจาย | 920.96 | 918.70 | 772.03 | 176.64 |
เอสพีพี::sparse_hash_map พร้อมสำรอง | ตารางแฮชกระจัดกระจาย | 914.84 | 912.47 | 422.85 | 158.73 |
มาตรฐาน::unordered_map | ตารางแฮช | 1249.09 | 1246.65 | 594.85 | 173.54 |
มาตรฐาน::unordered_map พร้อมสำรอง | ตารางแฮช | 1212.21 | 1209.71 | 347.40 | 176.49 |
เกณฑ์มาตรฐานประกอบด้วยการแทรกคำทั้งหมดจากชุดข้อมูล "Distinct Strings" ของ Dr. Askitis ลงในโครงสร้างข้อมูล ตรวจสอบพื้นที่หน่วยความจำที่ใช้ และค้นหาคำทั้งหมดจากชุดข้อมูล "Skew String Set 1" (โดยที่สตริงสามารถเป็นได้ นำเสนอหลายครั้ง) ในโครงสร้างข้อมูล โปรดทราบว่าสตริงในชุดข้อมูลนี้มีค่าเฉลี่ยและความยาวคีย์มัธยฐานค่อนข้างสั้น (ซึ่งอาจไม่ใช่กรณีการใช้งานจริงเมื่อเปรียบเทียบกับชุดข้อมูล Wikipedia ที่ใช้ด้านบน) มันคล้ายกับที่อยู่ในหน้าแรกของซีดาร์
โปรโตคอลการวัดประสิทธิภาพจะเหมือนกับชุดข้อมูล Wikipedia
ห้องสมุด | โครงสร้างข้อมูล | หน่วยความจำสูงสุด (MiB) | หน่วยความจำ (MiB) | แทรก (ns/คีย์) | อ่าน (ns/คีย์) |
---|---|---|---|---|---|
tsl::htrie_map | แฮท-ทรี | 604.76 | 601.79 | 485.45 | 77.80 |
tsl::htrie_map max_load_factor=4 | แฮท-ทรี | 768.10 | 764.98 | 491.78 | 75.48 |
tsl::htrie_map max_load_factor=2 | แฮท-ทรี | 1002.42 | 999.34 | 496.78 | 72.53 |
tsl::htrie_map max_load_factor=1 | แฮท-ทรี | 1344.98 | 1341.97 | 520.66 | 72.45 |
ซีดาร์::ดา | ไตรอาเรย์คู่ | 1105.45 | 1100.05 | 682.25 | 71.98 |
ซีดาร์::ดาสั่ง=เท็จ | ไตรอาเรย์คู่ | 1105.47 | 1100.05 | 668.75 | 71.95 |
ซีดาร์::ดา | อาร์เรย์คู่ลดไตร | 941.16 | 926.04 | 684.38 | 79.11 |
ซีดาร์::ดาสั่ง=เท็จ | อาร์เรย์คู่ลดไตร | 941.16 | 925.98 | 672.14 | 79.02 |
ซีดาร์::ดา | คำนำหน้าอาร์เรย์คู่ | 714.58 | 712.59 | 831.71 | 75.83 |
ซีดาร์::ดาสั่ง=เท็จ | คำนำหน้าอาร์เรย์คู่ | 714.66 | 712.31 | 786.93 | 75.89 |
แฮตทรี 3 (C) | แฮท-ทรี | 786.93 | 784.32 | 743.34 | 93.58 |
คิวพี ทรี (C) | คิวพี ทรี | 1800.02 | 1797.21 | 987.95 | 428.51 |
คริตบิตไตร (C) | คริติคอลบิต | 2210.52 | 2207.64 | 1986.19 | 1109.88 |
จูดี้เอสแอล (C) | จูดี้ อาเรย์ | 1,025.59 | 1023.11 | 535.02 | 202.36 |
จูดี้เอชเอส (C) | จูดี้ อาเรย์ | 1,002.50 | 999.97 | 456.09 | 148.36 |
tsl::array_map | ตารางแฮชอาร์เรย์ | 1308.08 | 1,031.67 | 545.82 | 46.41 |
tsl::array_map พร้อมสำรอง | ตารางแฮชอาร์เรย์ | 979.44 | 921.363 | 244.19 | 45.74 |
tsl::hopscotch_map | ตารางแฮช | 2336.39 | 1611.54 | 288.70 | 47.05 |
tsl::hopscotch_map พร้อมสำรอง | ตารางแฮช | 1614.22 | 1611.64 | 220.67 | 46.39 |
google::dense_hash_map | ตารางแฮช | 3913.64 | 2636.31 | 317.66 | 43.62 |
google::dense_hash_map พร้อมสำรอง | ตารางแฮช | 2638.19 | 2635.68 | 227.58 | 43.09 |
เอสพีพี::sparse_hash_map | ตารางแฮชกระจัดกระจาย | 1419.69 | 1417.61 | 586.26 | 56.00 |
เอสพีพี::sparse_hash_map พร้อมสำรอง | ตารางแฮชกระจัดกระจาย | 1424.21 | 1421.69 | 392.76 | 55.73 |
มาตรฐาน::unordered_map | ตารางแฮช | 2112.66 | 2110.19 | 554.02 | 105.05 |
มาตรฐาน::unordered_map พร้อมสำรอง | ตารางแฮช | 2053.95 | 2051.67 | 309.06 | 109.89 |
หากต้องการใช้ไลบรารี เพียงเพิ่มไดเร็กทอรีรวมลงในพาธรวมของคุณ มันเป็นห้องสมุด ส่วนหัวเท่านั้น
หากคุณใช้ CMake คุณยังสามารถใช้เป้าหมายที่ส่งออก tsl::hat_trie
จาก CMakeLists.txt ด้วย target_link_libraries
# Example where the hat-trie project is stored in a third-party directory
add_subdirectory (third-party/hat-trie)
target_link_libraries (your_target PRIVATE tsl::hat_trie)
รหัสควรทำงานร่วมกับคอมไพเลอร์มาตรฐาน C++11 และได้รับการทดสอบกับ GCC 4.8.4, Clang 3.5.0 และ Visual Studio 2015
หากต้องการรันการทดสอบ คุณจะต้องมีไลบรารี Boost Test และ CMake
git clone https://github.com/Tessil/hat-trie.git
cd hat-trie/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hat_trie_tests
API สามารถพบได้ที่นี่ หาก std::string_view
พร้อมใช้งาน API จะเปลี่ยนเล็กน้อยและสามารถพบได้ที่นี่
# include < iostream >
# include < string >
# include < tsl/htrie_map.h >
# include < tsl/htrie_set.h >
int main () {
/*
* Map of strings to int having char as character type.
* There is no support for wchar_t, char16_t or char32_t yet,
* but UTF-8 strings will work fine.
*/
tsl::htrie_map< char , int > map = {{ " one " , 1 }, { " two " , 2 }};
map[ " three " ] = 3 ;
map[ " four " ] = 4 ;
map. insert ( " five " , 5 );
map. insert_ks ( " six_with_extra_chars_we_ignore " , 3 , 6 );
map. erase ( " two " );
/*
* Due to the compression on the common prefixes, the letters of the string
* are not always stored contiguously. When we retrieve the key, we have to
* construct it.
*
* To avoid a heap-allocation at each iteration (when SSO doesn't occur),
* we reuse the key_buffer to construct the key.
*/
std::string key_buffer;
for ( auto it = map. begin (); it != map. end (); ++it) {
it. key (key_buffer);
std::cout << " { " << key_buffer << " , " << it. value () << " } " << std::endl;
}
/*
* If you don't care about the allocation.
*/
for ( auto it = map. begin (); it != map. end (); ++it) {
std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
}
tsl::htrie_map< char , int > map2 = {{ " apple " , 1 }, { " mango " , 2 }, { " apricot " , 3 },
{ " mandarin " , 4 }, { " melon " , 5 }, { " macadamia " , 6 }};
// Prefix search
auto prefix_range = map2. equal_prefix_range ( " ma " );
// {mandarin, 4} {mango, 2} {macadamia, 6}
for ( auto it = prefix_range. first ; it != prefix_range. second ; ++it) {
std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
}
// Find longest match prefix.
auto longest_prefix = map2. longest_prefix ( " apple juice " );
if (longest_prefix != map2. end ()) {
// {apple, 1}
std::cout << " { " << longest_prefix. key () << " , "
<< *longest_prefix << " } " << std::endl;
}
// Prefix erase
map2. erase_prefix ( " ma " );
// {apricot, 3} {melon, 5} {apple, 1}
for ( auto it = map2. begin (); it != map2. end (); ++it) {
std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
}
tsl::htrie_set< char > set = { " one " , " two " , " three " };
set. insert ({ " four " , " five " });
// {one} {two} {five} {four} {three}
for ( auto it = set. begin (); it != set. end (); ++it) {
it. key (key_buffer);
std::cout << " { " << key_buffer << " } " << std::endl;
}
}
ไลบรารีจัดเตรียมวิธีที่มีประสิทธิภาพในการซีเรียลไลซ์และดีซีเรียลไลซ์แผนที่หรือชุด เพื่อให้สามารถบันทึกเป็นไฟล์หรือส่งผ่านเครือข่าย ในการทำเช่นนั้น ผู้ใช้จำเป็นต้องจัดเตรียมออบเจ็กต์ฟังก์ชันสำหรับทั้งซีเรียลไลซ์เซชันและดีซีเรียลไลซ์เซชัน
struct serializer {
// Must support the following types for U: std::uint64_t, float and T if a map is used.
template < typename U>
void operator ()( const U& value);
void operator ()( const CharT* value, std:: size_t value_size);
};
struct deserializer {
// Must support the following types for U: std::uint64_t, float and T if a map is used.
template < typename U>
U operator ()();
void operator ()(CharT* value_out, std:: size_t value_size);
};
โปรดทราบว่าการใช้งานจะทิ้งความเข้ากันได้แบบไบนารี (endianness, การแทนไบนารีแบบลอยตัว, ขนาดของ int, ...) ของประเภทที่ทำให้เป็นอนุกรม/ดีซีเรียลไลซ์อยู่ในมือของออบเจ็กต์ฟังก์ชันที่ให้มา หากจำเป็นต้องมีความเข้ากันได้
รายละเอียดเพิ่มเติมเกี่ยวกับวิธี serialize
และ deserialize
มีอยู่ใน API
# include < cassert >
# include < cstdint >
# include < fstream >
# include < type_traits >
# include < tsl/htrie_map.h >
class serializer {
public:
serializer ( const char * file_name) {
m_ostream. exceptions (m_ostream. badbit | m_ostream. failbit );
m_ostream. open (file_name);
}
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 char * value, std:: size_t value_size) {
m_ostream. write (value, value_size);
}
private:
std::ofstream m_ostream;
};
class deserializer {
public:
deserializer ( const char * file_name) {
m_istream. exceptions (m_istream. badbit | m_istream. failbit | m_istream. eofbit );
m_istream. open (file_name);
}
template < class T ,
typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr >
T operator ()() {
T value;
m_istream. read ( reinterpret_cast < char *>(&value), sizeof (T));
return value;
}
void operator ()( char * value_out, std:: size_t value_size) {
m_istream. read (value_out, value_size);
}
private:
std::ifstream m_istream;
};
int main () {
const tsl::htrie_map< char , std:: int64_t > map = {{ " one " , 1 }, { " two " , 2 },
{ " three " , 3 }, { " four " , 4 }};
const char * file_name = " htrie_map.data " ;
{
serializer serial (file_name);
map. serialize (serial);
}
{
deserializer dserial (file_name);
auto map_deserialized = tsl::htrie_map< char , 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::htrie_map< char , std:: int64_t >:: deserialize (dserial, hash_compatible);
assert (map == map_deserialized);
}
}
คุณสามารถใช้ไลบรารีการทำให้เป็นซีเรียลไลซ์เพื่อหลีกเลี่ยงการสำเร็จรูปบางส่วนได้ หากประเภทการทำให้เป็นซีเรียลไลซ์นั้นซับซ้อนกว่า
ตัวอย่างต่อไปนี้ใช้ Boost Serialization พร้อมกับสตรีมการบีบอัด Boost zlib เพื่อลดขนาดของไฟล์ซีเรียลไลซ์ที่ได้
# 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/htrie_map.h >
template < typename Archive>
struct serializer {
Archive& ar;
template < typename T>
void operator ()( const T& val) { ar & val; }
template < typename CharT>
void operator ()( const CharT* val, std:: size_t val_size) {
ar. save_binary ( reinterpret_cast < const void *>(val), val_size* sizeof (CharT));
}
};
template < typename Archive>
struct deserializer {
Archive& ar;
template < typename T>
T operator ()() { T val; ar & val; return val; }
template < typename CharT>
void operator ()(CharT* val_out, std:: size_t val_size) {
ar. load_binary ( reinterpret_cast < void *>(val_out), val_size* sizeof (CharT));
}
};
namespace boost { namespace serialization {
template < class Archive , class CharT , class T >
void serialize (Archive & ar, tsl::htrie_map<CharT, T>& map, const unsigned int version) {
split_free (ar, map, version);
}
template < class Archive , class CharT , class T >
void save (Archive & ar, const tsl::htrie_map<CharT, T>& map, const unsigned int version) {
serializer<Archive> serial{ar};
map. serialize (serial);
}
template < class Archive , class CharT , class T >
void load (Archive & ar, tsl::htrie_map<CharT, T>& map, const unsigned int version) {
deserializer<Archive> deserial{ar};
map = tsl::htrie_map<CharT, T>:: deserialize (deserial);
}
}}
int main () {
const tsl::htrie_map< char , std:: int64_t > map = {{ " one " , 1 }, { " two " , 2 },
{ " three " , 3 }, { " four " , 4 }};
const char * file_name = " htrie_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::htrie_map< char , std:: int64_t > map_deserialized;
ia >> map_deserialized;
assert (map == map_deserialized);
}
}
รหัสนี้ได้รับอนุญาตภายใต้ใบอนุญาต MIT โปรดดูรายละเอียดในไฟล์ LICENSE