CVC3
2.4.1
|
#include <hash_table.h>
template to instante to hash map and hash set
based on the sgi implementation: http://www.sgi.com/tech/stl/HashedAssociativeContainer.html
_Key: hash key type _Data: key + value data to store _HashFcn: functional class providing a hash function: int(_Key) Note: in some STL implementations hash is already part of some extension an in namespace std or stdext, in some it is not. So we assume that it is not available. :TODO: _EqualKey: functional class providing a comparison function: bool(_Key, _Key) returns true iff two keys are considered to be equal _ExtractKey: extracts key from _Data: _Key(_Data)
types
Definition at line 127 of file hash_table.h.
typedef _Key Hash::hash_table::key_type |
Definition at line 128 of file hash_table.h.
typedef _Value Hash::hash_table::value_type |
Definition at line 129 of file hash_table.h.
typedef _HashFcn Hash::hash_table::hasher |
Definition at line 130 of file hash_table.h.
typedef _EqualKey Hash::hash_table::key_equal |
Definition at line 131 of file hash_table.h.
typedef BucketNode Hash::hash_table::Bucket [protected] |
Definition at line 147 of file hash_table.h.
typedef std::vector<Bucket*> Hash::hash_table::Data [protected] |
Definition at line 150 of file hash_table.h.
typedef Data::iterator Hash::hash_table::data_iter [protected] |
Definition at line 151 of file hash_table.h.
typedef Data::const_iterator Hash::hash_table::data_const_iter [protected] |
Definition at line 152 of file hash_table.h.
Hash::hash_table::hash_table | ( | ) | [inline] |
constructors
Definition at line 277 of file hash_table.h.
Hash::hash_table::hash_table | ( | size_type | initial_capacity | ) | [inline] |
Definition at line 285 of file hash_table.h.
Hash::hash_table::hash_table | ( | size_type | initial_capacity, |
const _HashFcn & | hash | ||
) | [inline] |
Definition at line 293 of file hash_table.h.
Hash::hash_table::hash_table | ( | size_type | initial_capacity, |
const _HashFcn & | hash, | ||
const _EqualKey & | equal | ||
) | [inline] |
Definition at line 301 of file hash_table.h.
Hash::hash_table::hash_table | ( | const hash_table & | other | ) | [inline] |
Definition at line 310 of file hash_table.h.
Hash::hash_table::~hash_table | ( | ) | [inline] |
Definition at line 317 of file hash_table.h.
methods
template parameters
Definition at line 194 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::getBucketIndex(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::resize().
bool Hash::hash_table::equal | ( | const key_type & | key1, |
const key_type & | key2 | ||
) | const [inline, protected] |
Definition at line 199 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find_or_insert(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::erase().
const key_type& Hash::hash_table::extractKey | ( | const value_type & | value | ) | const [inline, protected] |
Definition at line 204 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::resize(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find_or_insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::erase(), Hash::hash_table::iterator::operator++(), and Hash::hash_table::const_iterator::operator++().
bucket retrieval
Definition at line 213 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::getBucketByKey(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find_or_insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::erase(), Hash::hash_table::iterator::operator++(), and Hash::hash_table::const_iterator::operator++().
Definition at line 217 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find().
Definition at line 221 of file hash_table.h.
Definition at line 225 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::getBucketByKey(), Hash::hash_table::iterator::operator++(), and Hash::hash_table::const_iterator::operator++().
Definition at line 230 of file hash_table.h.
void Hash::hash_table::resize | ( | ) | [inline, protected] |
resize
Definition at line 240 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::insert(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find_or_insert().
hash_table& Hash::hash_table::operator= | ( | const hash_table & | other | ) | [inline] |
Definition at line 322 of file hash_table.h.
void Hash::hash_table::assignTable | ( | const Data & | data | ) | [inline] |
Definition at line 338 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::hash_table(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::operator=().
void Hash::hash_table::swap | ( | hash_table & | other | ) | [inline] |
Definition at line 370 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::swap(), Hash::hash_set< ExprValue *, HashEV, EqEV >::swap(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::swap().
void Hash::hash_table::init | ( | ) | [inline] |
Definition at line 379 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::hash_table().
void Hash::hash_table::clear | ( | ) | [inline] |
Definition at line 386 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::clear(), Hash::hash_set< ExprValue *, HashEV, EqEV >::clear(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::~hash_table(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::operator=().
operations
Definition at line 406 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::find(), Hash::hash_set< ExprValue *, HashEV, EqEV >::find(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::contains().
const_iterator Hash::hash_table::find | ( | const key_type & | key | ) | const [inline] |
Definition at line 416 of file hash_table.h.
std::pair<iterator, bool> Hash::hash_table::insert | ( | const value_type & | value | ) | [inline] |
Definition at line 428 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::insert(), and Hash::hash_set< ExprValue *, HashEV, EqEV >::insert().
value_type& Hash::hash_table::find_or_insert | ( | const value_type & | value | ) | [inline] |
Definition at line 451 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::operator[]().
Definition at line 475 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::erase(), and Hash::hash_set< ExprValue *, HashEV, EqEV >::erase().
const_iterator Hash::hash_table::erase | ( | const const_iterator & | iter | ) | [inline] |
Definition at line 504 of file hash_table.h.
bool Hash::hash_table::contains | ( | const key_type & | key | ) | const [inline] |
status
Definition at line 539 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::contains(), Hash::hash_set< ExprValue *, HashEV, EqEV >::contains(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::count().
size_type Hash::hash_table::count | ( | const _Key & | key | ) | const [inline] |
Definition at line 545 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::count(), and Hash::hash_set< ExprValue *, HashEV, EqEV >::count().
bool Hash::hash_table::empty | ( | ) | const [inline] |
Definition at line 555 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::empty(), and Hash::hash_set< ExprValue *, HashEV, EqEV >::empty().
size_type Hash::hash_table::size | ( | ) | const [inline] |
Definition at line 560 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::size(), Hash::hash_set< ExprValue *, HashEV, EqEV >::size(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::resize().
size_type Hash::hash_table::bucket_count | ( | ) | const [inline] |
Definition at line 565 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::bucket_count(), and Hash::hash_set< ExprValue *, HashEV, EqEV >::bucket_count().
float Hash::hash_table::load_factor | ( | ) | const [inline] |
Definition at line 570 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::load_factor(), Hash::hash_set< ExprValue *, HashEV, EqEV >::load_factor(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::resize().
iterator Hash::hash_table::begin | ( | ) | [inline] |
iterators
Definition at line 579 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::begin(), and Hash::hash_set< ExprValue *, HashEV, EqEV >::begin().
const_iterator Hash::hash_table::begin | ( | ) | const [inline] |
Definition at line 595 of file hash_table.h.
iterator Hash::hash_table::end | ( | ) | [inline] |
Definition at line 612 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::end(), Hash::hash_set< ExprValue *, HashEV, EqEV >::end(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::contains(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::begin(), Hash::hash_table::iterator::operator++(), and Hash::hash_table::const_iterator::operator++().
const_iterator Hash::hash_table::end | ( | ) | const [inline] |
Definition at line 617 of file hash_table.h.
friend class iterator [friend] |
Definition at line 157 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::begin(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::end().
friend class const_iterator [friend] |
Definition at line 159 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::erase(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::begin(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::end().
hasher Hash::hash_table::d_hash [protected] |
variables
template parameters
Definition at line 170 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::hash(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::operator=(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::swap().
key_equal Hash::hash_table::d_equal [protected] |
Definition at line 173 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::equal(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::operator=(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::swap().
_ExtractKey Hash::hash_table::d_extractKey [protected] |
Definition at line 176 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::extractKey(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::operator=(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::swap().
size_type Hash::hash_table::d_size [protected] |
Definition at line 180 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::operator=(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::swap(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::clear(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find_or_insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::erase(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::empty(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::size(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::load_factor(), and Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::begin().
Data Hash::hash_table::d_data [protected] |
Definition at line 183 of file hash_table.h.
Referenced by Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::getBucketIndex(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::getBucketByIndex(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::resize(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::assignTable(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::swap(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::init(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::clear(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::find_or_insert(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::erase(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::bucket_count(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::load_factor(), Hash::hash_table< _Key, _Key, _HashFcn, _EqualKey, _Identity< _Key > >::begin(), Hash::hash_table::iterator::operator++(), and Hash::hash_table::const_iterator::operator++().