欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL源码剖析-hash_map / hash_multimap

程序员文章站 2022-03-23 10:49:18
...

类似于标准的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(不允许插入重复值)。