hash_set, hash_map,hash_multiset,hash_multimap

hash_set

STL set多半以RB-TREE为底层机制。SGI在STL标准规格之外又提供了一个所谓的hash_set,以hashtable为底层机制。

RB-TREE有自动排序功能而hashtable没有,反应出来的结果就是,set的元素有自动排序功能而hash_set没有。

凡是hashtable无法处理者,hash_set也无法处理。

hash_map

SGISTL标准规格之外,另提供了一个所谓的hash_map,以hashtable为底层机制。由于hash_map所供应的操作接口,hashtable都提供了,所以几乎所有的hash_map操作行为,都只是转调用hashtable的操作行为而已。

运用map,为的是能够根据键值快速搜寻元素。RB-TREE由自动排序功能而hashtable没有,反映出来的结果就是,map的元素有自动排序功能而hash_map没有。

map的特性是,每一个元素都同时拥有一个实值和一个键值,这一点在hash_map中也是一样的。hash_map的使用方式和map完全相同。

凡是hashtable无法处理者,hash_map也无法处理。

//以下的hash<>是个function object,定义于<stl_hash_fun.h>中
template<class Key, class T,
		class HashFcn = hash<Key>
        class EqualKey = equal_to<Key>
        class Alloc = alloc>
class hash_map{
private:
    typedef hashtable<pair<const Key, T>, Key,
        HashFcn, select1st<pair<const Key, T>>
            EqualKey,Alloc> ht;
    ht rep;		//底层机制以hash table完成
public:
   	typedef typename ht::key_type key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef typename ht::value_type value_type;
    typedef typename ht::hash hasher;
    typedef typename ht::key_equal key_equal;
    
    typedef typename ht::size_type size_type;
    typedef typename ht::difference_type difference_type;
    typedef typename ht::pointer pointer;
    typedef typename ht::const_ponter const_pointer;
    typedef typename ht::reference reference;
    typedef typename ht::const_reference const_reference;
    
    typedef typename ht::iterator iterator;
    typedef typename ht::const_iterator const_iterator;
    
    hasher hash_funct() const { return rep.hash_funct(); }
    key_equal key_eq() const { return rep.key_eq(); }
    
public:
    //缺省使用大小为100的表格,将由hash table调整为最接近且较大的质数
    hash_map() : rep(100, hasher(), key_equal()) {}
    explicit hash_map(size_type n) : rep(n, hasher(), key_equal()) {}
    hash_map(size_type n, const hasher& hf) : rep(n,hf,key_equal()) {}
    hash_map(size_type n, const hasher& hf,const key_equal& eql) 
        : rep(n,hf,eql) {}
    //以下,插入操作全部使用insert_unique,不允许键值重复
    template<class InputIterator>
    hash_map(InputIterator f, InputIterator l) :
    	rep(100,hasher(),key_equal()) {
            rep.insert_unique(f,l);
        } 
    template<class InputIterator>
    hash_map(InputIterator f, InputIterator l, size_type n) :
    	rep(n,hasher(),key_equal()) {
            rep.insert_unique(f,l);
        }
    template<class InputIterator>
    hash_map(InputIterator f, InputIterator l, size_type n, 
             const hasher& hf, const key_equal& eql) :
    	rep(n,hf,key_equal()) {
            rep.insert_unique(f,l);
        }
    template<class InputIterator>
    hash_map(InputIterator f, InputIterator l, size_type n, 
             const hasher& hf, const key_equal& eql) :
    	rep(n,hf,eql) {
            rep.insert_unique(f,l);
        }
public:
    //所有操作几乎都有hash table对应版本,传递调用就行
    size_type size() const { return rep.size(); }
    size_type max_size() const { return rep.max_size(); }
    bool empty() const { return rep.empty(); }
    void swap(hash_map& hs) { rep.swap(hs.rep); }
    friend bool 
    operator==__STL_NULL_TMPL_ARGS(const hash_map&, const hash_map&);
    
    iterator begin() { return rep.begin(); }
    iterator end() { return rep.end(); }
    const_iterator begin() const { return rep.begin(); }
    const_iterator end() const { return rep.end(); }
public:
    pair<iterator, bool> insert(const value_type& obj)
    { return rep.insert_unique(obj); }
    
    template<class InputIterator>
    void insert(InputIterator f,InputIterator l) { rep.insert_unique(f,l); }
    
    pair<iterator, bool> insert_noresize(const value_type& obj)
    { return rep.insert_unique_noresize(obj); }
    
    iterator find(const key_type& key) { return rep.find(key); }
    const_iterator find(const key_type& key) const { return rep.find(key); }
    
    T& operator[](const key_type& key){
        return rep.find_or_insert(value_type(key, T())).second;
    }
    size_type 
};

hash_multiset

hash_multiset的特性与multiset完全相同,唯一的差别在于它的底层机制是hashtable。也因此,hash_multiset的元素并不会被自动排序。

hash_multisethash_set实现上唯一的差别在于,前者的元素插入操作采用底层机制hashtableinsert_equal(),后者则是采用insert_unique()

hashtable有一些无法处理的类型(除非用户为那些类型攥写hash function)。凡是hashtable无法处理者,hash_multiset也无法处理。

hash_multimap

hash_multimap的特性与multimap完全相同,唯一的差别在于它的底层机制是hashtable。因此,hash_multimap的元素并不会被自动排序。

hash_multimap

hash_multimap的特性与multimap完全相同,唯一的差别在于它的底层机制是hashtable。因此,hash_multimap的元素并不会被自动排序。

hash_multimaphash_map实现上唯一差别在于,前者的元素插入操作采用底层机制hashtableinsert_equal(),后者则是采用insert_unique()

上一篇:Codeforces Round #715 (Div. 2)


下一篇:Luogu P7445「EZEC-7」线段树