CVC3
|
#include <hash_table.h>
Classes | |
struct | BucketNode |
class | const_iterator |
class | iterator |
inner classes More... | |
Public Types | |
typedef Hash::size_type | size_type |
types | |
typedef _Key | key_type |
typedef _Value | value_type |
typedef _HashFcn | hasher |
typedef _EqualKey | key_equal |
Public Member Functions | |
hash_table () | |
constructors | |
hash_table (size_type initial_capacity) | |
hash_table (size_type initial_capacity, const _HashFcn &hash) | |
hash_table (size_type initial_capacity, const _HashFcn &hash, const _EqualKey &equal) | |
hash_table (const hash_table &other) | |
~hash_table () | |
hash_table & | operator= (const hash_table &other) |
void | assignTable (const Data &data) |
void | swap (hash_table &other) |
void | init () |
void | clear () |
iterator | find (const key_type &key) |
operations | |
const_iterator | find (const key_type &key) const |
std::pair< iterator, bool > | insert (const value_type &value) |
value_type & | find_or_insert (const value_type &value) |
size_type | erase (const key_type &key) |
const_iterator | erase (const const_iterator &iter) |
bool | contains (const key_type &key) const |
status | |
size_type | count (const _Key &key) const |
bool | empty () const |
size_type | size () const |
size_type | bucket_count () const |
float | load_factor () const |
iterator | begin () |
iterators | |
const_iterator | begin () const |
iterator | end () |
const_iterator | end () const |
Protected Types | |
typedef BucketNode | Bucket |
typedef std::vector< Bucket * > | Data |
typedef Data::iterator | data_iter |
typedef Data::const_iterator | data_const_iter |
Protected Member Functions | |
size_type | hash (const key_type &key) const |
methods | |
bool | equal (const key_type &key1, const key_type &key2) const |
const key_type & | extractKey (const value_type &value) const |
size_type | getBucketIndex (const key_type &key) const |
bucket retrieval | |
Bucket * | getBucketByKey (const key_type &key) |
const Bucket * | getBucketByKey (const key_type &key) const |
Bucket * | getBucketByIndex (const size_type index) |
const Bucket * | getBucketByIndex (const size_type index) const |
void | resize () |
resize | |
Protected Attributes | |
hasher | d_hash |
variables | |
key_equal | d_equal |
_ExtractKey | d_extractKey |
size_type | d_size |
Data | d_data |
Friends | |
class | iterator |
class | const_iterator |
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)
Definition at line 121 of file hash_table.h.
typedef Hash::size_type Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::size_type |
types
Definition at line 127 of file hash_table.h.
typedef _Key Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::key_type |
Definition at line 128 of file hash_table.h.
typedef _Value Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::value_type |
Definition at line 129 of file hash_table.h.
typedef _HashFcn Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::hasher |
Definition at line 130 of file hash_table.h.
typedef _EqualKey Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::key_equal |
Definition at line 131 of file hash_table.h.
|
protected |
Definition at line 147 of file hash_table.h.
|
protected |
Definition at line 150 of file hash_table.h.
|
protected |
Definition at line 151 of file hash_table.h.
|
protected |
Definition at line 152 of file hash_table.h.
|
inline |
constructors
Definition at line 277 of file hash_table.h.
|
inline |
Definition at line 285 of file hash_table.h.
|
inline |
Definition at line 293 of file hash_table.h.
|
inline |
Definition at line 301 of file hash_table.h.
|
inline |
Definition at line 310 of file hash_table.h.
|
inline |
Definition at line 317 of file hash_table.h.
|
inlineprotected |
methods
template parameters
Definition at line 194 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::getBucketIndex(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::resize().
|
inlineprotected |
Definition at line 199 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::erase(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find_or_insert(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::insert().
|
inlineprotected |
Definition at line 204 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::erase(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find_or_insert(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::insert(), Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::iterator::operator++(), Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::const_iterator::operator++(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::resize().
|
inlineprotected |
bucket retrieval
Definition at line 213 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::erase(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find_or_insert(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::getBucketByKey(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::insert(), Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::iterator::operator++(), and Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::const_iterator::operator++().
|
inlineprotected |
Definition at line 217 of file hash_table.h.
|
inlineprotected |
Definition at line 221 of file hash_table.h.
|
inlineprotected |
Definition at line 225 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::getBucketByKey(), Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::iterator::operator++(), and Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::const_iterator::operator++().
|
inlineprotected |
Definition at line 230 of file hash_table.h.
|
inlineprotected |
resize
Definition at line 240 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find_or_insert(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::insert().
|
inline |
Definition at line 322 of file hash_table.h.
|
inline |
Definition at line 338 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::hash_table(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::operator=().
|
inline |
Definition at line 370 of file hash_table.h.
Referenced by Hash::hash_set< Var >::swap(), and Hash::hash_map< long, int >::swap().
|
inline |
Definition at line 379 of file hash_table.h.
|
inline |
Definition at line 386 of file hash_table.h.
Referenced by Hash::hash_set< Var >::clear(), Hash::hash_map< long, int >::clear(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::operator=(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::~hash_table().
|
inline |
operations
Definition at line 406 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::contains(), Hash::hash_set< Var >::find(), and Hash::hash_map< long, int >::find().
|
inline |
Definition at line 416 of file hash_table.h.
|
inline |
Definition at line 428 of file hash_table.h.
Referenced by Hash::hash_set< Var >::insert(), and Hash::hash_map< long, int >::insert().
|
inline |
Definition at line 451 of file hash_table.h.
Referenced by Hash::hash_map< long, int >::operator[]().
|
inline |
Definition at line 475 of file hash_table.h.
Referenced by Hash::hash_set< Var >::erase(), and Hash::hash_map< long, int >::erase().
|
inline |
Definition at line 504 of file hash_table.h.
|
inline |
status
Definition at line 539 of file hash_table.h.
Referenced by Hash::hash_set< Var >::contains(), Hash::hash_map< long, int >::contains(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::count().
|
inline |
Definition at line 545 of file hash_table.h.
Referenced by Hash::hash_set< Var >::count(), and Hash::hash_map< long, int >::count().
|
inline |
Definition at line 555 of file hash_table.h.
Referenced by Hash::hash_set< Var >::empty(), and Hash::hash_map< long, int >::empty().
|
inline |
|
inline |
Definition at line 565 of file hash_table.h.
Referenced by Hash::hash_set< Var >::bucket_count(), and Hash::hash_map< long, int >::bucket_count().
|
inline |
|
inline |
iterators
Definition at line 579 of file hash_table.h.
Referenced by Hash::hash_set< Var >::begin(), and Hash::hash_map< long, int >::begin().
|
inline |
Definition at line 595 of file hash_table.h.
|
inline |
Definition at line 612 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::begin(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::contains(), Hash::hash_set< Var >::end(), Hash::hash_map< long, int >::end(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::insert(), Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::iterator::operator++(), and Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::const_iterator::operator++().
|
inline |
Definition at line 617 of file hash_table.h.
|
friend |
Definition at line 157 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::begin(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::end(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::insert().
|
friend |
Definition at line 159 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::begin(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::end(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::erase(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find().
|
protected |
variables
template parameters
Definition at line 170 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::hash(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::operator=(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::swap().
|
protected |
Definition at line 173 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::equal(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::operator=(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::swap().
|
protected |
Definition at line 176 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::extractKey(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::operator=(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::swap().
|
protected |
Definition at line 180 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::begin(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::clear(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::empty(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::erase(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find_or_insert(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::insert(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::load_factor(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::operator=(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::size(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::swap().
|
protected |
Definition at line 183 of file hash_table.h.
Referenced by Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::assignTable(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::begin(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::bucket_count(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::clear(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::erase(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::find_or_insert(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::getBucketByIndex(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::getBucketIndex(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::hash_table(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::init(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::insert(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::load_factor(), Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::iterator::operator++(), Hash::hash_table< _Key, _Value, _HashFcn, _EqualKey, _ExtractKey >::const_iterator::operator++(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::operator=(), Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::resize(), and Hash::hash_table< long, std::pair< const long, bool >, hash< long >, std::equal_to< long >, _Select1st< std::pair< const long, bool > > >::swap().