hash_set
STL set
多半以RB-TREE为底层机制。SGI在STL标准规格之外又提供了一个所谓的hash_set
,以hashtable
为底层机制。
RB-TREE有自动排序功能而hashtable
没有,反应出来的结果就是,set
的元素有自动排序功能而hash_set
没有。
凡是hashtable
无法处理者,hash_set
也无法处理。
hash_map
SGI
在STL
标准规格之外,另提供了一个所谓的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_multiset
和hash_set
实现上唯一的差别在于,前者的元素插入操作采用底层机制hashtable
的insert_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_multimap
和hash_map
实现上唯一差别在于,前者的元素插入操作采用底层机制hashtable
的insert_equal()
,后者则是采用insert_unique()
。