hash_set
STL set mostly takes RB-TREE as the underlying mechanism. SGI provides a so-called hash in addition to the STL Standard Specification_ Set, with hashtable as the underlying mechanism.
RB-TREE has the function of automatic sorting, but hashtable does not. The result is that the elements of set have the function of automatic sorting, but hash_set No.
For those hashtable cannot handle, hash_set cannot process either.
hash_map
SGI provides a so-called hash in addition to the STL Standard Specification_ Map, with hashtable as the underlying mechanism. Due to hash_ Hashtable provides all the operation interfaces provided by map, so almost all hashes_ Map operation behavior is just the operation behavior of calling hashtable.
Map is used to quickly search for elements according to key values. RB-TREE has the function of automatic sorting instead of hashtable. The result is that the elements of map have the function of automatic sorting instead of hash_ No.
The characteristic of map is that each element has a real value and a key value at the same time, which is in hash_ The same is true in map. hash_map is used in exactly the same way as map.
For those hashtable cannot handle, hash_map cannot be processed.
//The following hash < > is a function object defined in < STL_ hash_ fun. h> Medium
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; //The underlying mechanism is completed by 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:
//The default size of the table is 100, and the hash table will be adjusted to the nearest and larger prime number
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) {}
//In the following, insert is used for all insertion operations_ Unique, duplicate key values are not allowed
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:
//Almost all operations have the corresponding version of hash table. Just pass the call
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_ The characteristics of multiset are exactly the same as multiset. The only difference is that its underlying mechanism is hashtable. Therefore, hash_ The elements of a multiset are not automatically sorted.
hash_multiset and hash_ The only difference in the implementation of set is that the element insertion operation of the former adopts the underlying mechanism hashtable insert_equal(), which uses insert_unique().
Hashtable has some types that cannot be handled (unless the user writes hash function s for those types). For those hashtable cannot handle, hash_multiset also cannot handle.
hash_multimap
hash_ The characteristics of multimap are exactly the same as those of multimap. The only difference is that its underlying mechanism is hashtable. Therefore, hash_ The elements of a multimap are not automatically sorted.
hash_multimap
hash_ The characteristics of multimap are exactly the same as those of multimap. The only difference is that its underlying mechanism is hashtable. Therefore, hash_ The elements of a multimap are not automatically sorted.
hash_multimap and hash_ The only difference in map implementation is that the element insertion operation of the former adopts the underlying mechanism hashtable insert_equal(), which uses insert_unique().