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 许可证的许可，有关详细信息，请参阅许可证文件。
