STL源码剖析-hash_map / hash_multimap

bear_fish

发布于 2018-09-14 09:42:46

6510

发布于 2018-09-14 09:42:46

类似于标准的map以rb_tree为底层实现，hash_map以hashtable为底层实现，hash_map的底层操作也是由hashtabe提供。

运用map，为的是能够快速的根据key搜索元素。这一点无论其底层是rb_tree或是hashtable，都可以达成任务。但是rb_tree有自动排序的功能，而hashtable是没有，反应的结果是map元素有自动排序功能，而hash_map没有。

如下主要给出hash_map的成员变量，以及构造函数，插入函数，通过这几个部分我们就可以在大体上理解hash_map.

template<typename Key, typename Value, class HashFun = std::hash<Key>>
class hash_map{
    private:
        typedef hashtable<Key, Value, HashFun> ht;

        // 成员，底层以hash table完成
        ht rep;

    public:
        hash_map():rep(100){};

        template<typename InputIterator>
        hash_map(InputIterator first, InputIterator last):
            rep(100){rep.insert_equal(first, last);}
};

hash_multimap的特性和hash_map完全相同，唯一的区别在于插入的时候使用的insert_equal函数(允许插入重复值)而不是insert_unique(不允许插入重复值)。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年07月01日，如有侵权请联系 cloudcommunity@tencent.com 删除

其他