ordered-map, 保留插入顺序的C++ 哈希映射和哈希集

分享于 

11分钟阅读

GitHub

  繁體 雙語
C++ hash map/set which preserves the order of insertion
  • 源代码名称:ordered-map
  • 源代码网址:http://www.github.com/Tessil/ordered-map
  • ordered-map源代码文档
  • ordered-map源代码下载
  • Git URL:
    git://www.github.com/Tessil/ordered-map.git
    Git Clone代码到本地:
    git clone http://www.github.com/Tessil/ordered-map
    Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/Tessil/ordered-map
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
    

    Build StatusBuild status

    保留插入顺序的 C++ 哈希映射和哈希集

    有序映射库提供一个哈希映射和哈希集,它保持插入顺序与 OrderedDict 类似。 当遍历映射时,值将按它的插入的顺序返回。

    这些值连续存储在底层结构中,即使在清除操作之后,值之间也没有任何漏洞。 默认情况下,std::deque 用于这里结构,但也可以使用 std::vector。 这种结构可以通过 values_container() 方法直接访问,如果结构是 std::vector,也可以提供 data() 方法,以便轻松与api交互。

    为了解决散列的冲突,库使用了罗宾汉探测,并向后移删除。

    库提供一个类似于 std::deque/std::vector的行为,但是用于查找的O(1) 平均时间复杂度和 O(1)的amortised时间复杂度。 这是一个更高的内存占用( 如果加载因子为,每个条目为 16字节,对于 0.5个加载因子,每个条目大约为个字节)的价格。

    提供了两个类:tsl::ordered_maptsl::ordered_set

    注意 : 库使用两个大小为 array的幂,以利用快速模值。 为了获得良好性能,它需要哈希表具有良好的分布式哈希函数。 如果遇到性能问题,请检查哈希函数。

    关键特性

    • 只要将项目添加到包含路径,就可以将该项目添加到你的包含路径中。
    • 值以与插入顺序相同的顺序存储。 库提供了对存储值的底层结构的直接访问。
    • 查找与 std::unordered_map 相似但插入速度快且内存使用率降低的查找的平均时间复杂度。
    • 提供随机访问迭代器和反向迭代器。
    • 支持异构查找( 比如。 如有使用 std::unique_ptr<int> 作为键的映射,则可以使用 int* 或者 std::uintptr_t 作为 find的关键参数,参见示例2 )。
    • 库可以与禁用的异常( 通过Clang和GCC上的-fno-exceptions 选项,在 MSVC 上没有 /EH 选项,或者仅仅通过定义 TSL_NO_EXCEPTIONS ) 一起使用。 std::terminate 在禁用异常时用于替换 throw 指令。
    • API与 std::unordered_mapstd::unordered_set 非常相似。

    std::unordered_map的差异

    • 迭代器是 RandomAccessIterator
    • 迭代器失效的行为方式接近于 std::vectorstd::deque ( 有关详细信息,请参见 API )。 如果使用 std::vector 作为 ValueTypeContainer,可以使用 reserve() 来预分配一些空间,并避免插入器上的迭代器失效。
    • erase() 操作,它具有 O(n)的复杂性。 存在更快的O(1) 版本 unordered_erase(),但它破坏了插入顺序( 有关详细信息,请参见 API )。 还可以使用 O(1) pop_back()
    • 对于迭代器,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}
    • 映射只能容纳 232 1个值,即 4 294 967 295值。
    • 不支持某些桶相关方法( 比如bucket_size桶。)。

    线程安全保证与 std::unordered_map ( 可能有多个读者) 相同。 对于强异常保证,只有在 ValueContainer::emplace_back 具有强异常保证( 如果类型T 不是只能引发异常的移动构造函数,则为 true 为 std::vectorstd::deque,只要类型T 可能引发异常,请参见详细信息。)的情况下才。

    这些差异也适用于 std::unordered_settsl::ordered_set

    安装

    要使用有序映射,只需将项目添加到包含路径。 它是一个头 header library库。

    代码应该与符合C++11标准的编译器一起工作,并且已经用 GCC 4.8.4.Clang 3.5.0和 Visual Studio 2015进行了测试。

    要运行测试,你将需要Boost测试库和插件。

    git clone https://github.com/Tessil/ordered-map.gitcd ordered-map
    mkdir buildcd build
    cmake.. 
    make
    ./test_ordered_map

    用法

    这个API可以在这里找到

    示例

    #include<iostream>#include<string>#include<cstdlib>#include<tsl/ordered_map.h>#include<tsl/ordered_set.h>intmain() {
     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(constauto& 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(constauto& key_value : map) {
     std::cout <<"{" <<key_value.first <<", " <<key_value.second <<"}" <<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 用于查找和擦除操作,只要使用的类型为hashable和 Key

    要激活 tsl::ordered_map/set 中的异构重载,必须有效的限定 id KeyEqual::is_transparent。 它的工作方式与 std::map::find 相同。 你既可以使用 std::equal_to<>,也可以定义自己的函数对象。

    KeyEqualHash 都需要能够处理不同的类型。

    #include<functional>#include<iostream>#include<string>#include<tsl/ordered_map.h>structemployee {
     employee(int id, std::string name) : m_id(id), m_name(std::move(name)) {
     }
     friendbooloperator==(const employee& empl, int empl_id) {
     return empl.m_id == empl_id;
     }
     friendbooloperator==(int empl_id, const employee& empl) {
     return empl_id == empl.m_id;
     }
     friendbooloperator==(const employee& empl1, const employee& empl2) {
     return empl1.m_id == empl2.m_id;
     }
     int m_id;
     std::string m_name;
    };structhash_employee {
     std::size_toperator()(const employee& empl) const {
     return std::hash<int>()(empl.m_id);
     }
     std::size_toperator()(int id) const {
     return std::hash<int>()(id);
     }
    };structequal_employee {
     using is_transparent = void;
     booloperator()(const employee& empl, int empl_id) const {
     return empl.m_id == empl_id;
     }
     booloperator()(int empl_id, const employee& empl) const {
     return empl_id == empl.m_id;
     }
     booloperator()(const employee& empl1, const employee& empl2) const {
     return empl1.m_id == empl2.m_id;
     }
    };intmain() {
     // 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 2003auto 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;
    } 

    许可证

    代码是在MIT许可下获得许可的,参见许可文件( )。


    SET  PRE  哈希  插入  ord  Insertion  
    相关文章