ordered map
v1.1.0
ordered-map 函式庫提供了一個哈希映射和一個哈希集，它們以類似於 Python 的 OrderedDict 的方式保留插入順序。迭代映射時，值將按照插入的順序傳回。
這些值連續儲存在底層結構中，即使在擦除操作之後，值之間也沒有空洞。預設情況下，此結構使用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 。
注意：此函式庫使用 2 的冪作為其儲存桶數組的大小，以利用快速模數。為了獲得良好的性能，要求雜湊表具有分佈良好的雜湊函數。如果您遇到效能問題，請檢查您的雜湊函數。
tsl::ordered_map匯出目標。std::unordered_map類似，但插入速度更快並減少了內存使用量（有關詳細信息，請參閱基準測試）。Key不同的類型的find （例如，如果您有一個使用std::unique_ptr<foo>作為鍵的映射，則可以使用foo*或std::uintptr_t作為鍵參數find而不構造std::unique_ptr<foo> ，請參閱範例）。precalculated_hash參數）。serialize/deserialize方法）。-fno-exceptions選項，在 MSVC 上沒有/EH選項或簡單地透過定義TSL_NO_EXCEPTIONS ）。 std::terminate用於在停用異常時取代throw指令。std::unordered_map和std::unordered_set非常相似。std::unordered_map相比的差異tsl::ordered_map嘗試擁有與std::unordered_map類似的接口，但存在一些差異。
RandomAccessIterator 。std::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函數僅在其文件中列出的前提條件下才有保證。
要使用有序映射，只需將包含目錄新增至包含路徑即可。它是一個僅包含頭檔的庫。
如果您使用 CMake，也可以將 CMakeLists.txt 中的tsl::ordered_map匯出目標與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中的異質重載，qualified-id 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 ()();
};請注意，如果需要相容性，則實作會將其序列化/反序列化類型的二進位相容性（位元組序、浮點二進位表示、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 壓縮流來減少產生的序列化檔案的大小。由於在 lambda 中使用模板參數清單語法，因此此範例需要 C++20，但它可以適應較新的版本。
# 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 許可證的許可，有關詳細信息，請參閱許可證文件。
