Sierra Toolkit
Version of the Day
|
#include <hashtable_eastl.h>
Public Types | |
enum | { kKeyAlignment = EASTL_ALIGN_OF(key_type), kKeyAlignmentOffset = 0, kValueAlignment = EASTL_ALIGN_OF(value_type), kValueAlignmentOffset = 0, kAllocFlagBuckets = 0x00400000 } |
typedef Key | key_type |
typedef Value | value_type |
typedef ExtractKey::result_type | mapped_type |
typedef hash_code_base< Key, Value, ExtractKey, Equal, H1, H2, H, bCacheHashCode > | hash_code_base_type |
typedef hash_code_base_type::hash_code_t | hash_code_t |
typedef Allocator | allocator_type |
typedef Equal | key_equal |
typedef ptrdiff_t | difference_type |
typedef eastl_size_t | size_type |
typedef value_type & | reference |
typedef const value_type & | const_reference |
typedef node_iterator< value_type, !bMutableIterators, bCacheHashCode > | local_iterator |
typedef node_iterator< value_type, true, bCacheHashCode > | const_local_iterator |
typedef hashtable_iterator< value_type, !bMutableIterators, bCacheHashCode > | iterator |
typedef hashtable_iterator< value_type, true, bCacheHashCode > | const_iterator |
typedef eastl::reverse_iterator< iterator > | reverse_iterator |
typedef eastl::reverse_iterator< const_iterator > | const_reverse_iterator |
typedef hash_node< value_type, bCacheHashCode > | node_type |
typedef type_select< bUniqueKeys, eastl::pair< iterator, bool >, iterator >::type | insert_return_type |
typedef hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys > | this_type |
typedef RehashPolicy | rehash_policy_type |
typedef ExtractKey | extract_key_type |
typedef H1 | h1_type |
typedef H2 | h2_type |
typedef H | h_type |
Public Member Functions | |
hashtable (size_type nBucketCount, const H1 &, const H2 &, const H &, const Equal &, const ExtractKey &, const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX " hashtable")) | |
template<typename FowardIterator > | |
hashtable (FowardIterator first, FowardIterator last, size_type nBucketCount, const H1 &, const H2 &, const H &, const Equal &, const ExtractKey &, const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX " hashtable")) | |
hashtable (const hashtable &x) | |
allocator_type & | get_allocator () |
void | set_allocator (const allocator_type &allocator) |
this_type & | operator= (const this_type &x) |
void | swap (this_type &x) |
iterator | begin () |
const_iterator | begin () const |
iterator | end () |
const_iterator | end () const |
local_iterator | begin (size_type n) |
local_iterator | end (size_type) |
const_local_iterator | begin (size_type n) const |
const_local_iterator | end (size_type) const |
bool | empty () const |
size_type | size () const |
size_type | bucket_count () const |
size_type | bucket_size (size_type n) const |
float | load_factor () const |
const rehash_policy_type & | rehash_policy () const |
void | rehash_policy (const rehash_policy_type &rehashPolicy) |
insert_return_type | insert (const value_type &value) |
iterator | insert (const_iterator, const value_type &value) |
template<typename InputIterator > | |
void | insert (InputIterator first, InputIterator last) |
iterator | erase (iterator position) |
iterator | erase (iterator first, iterator last) |
reverse_iterator | erase (reverse_iterator position) |
reverse_iterator | erase (reverse_iterator first, reverse_iterator last) |
size_type | erase (const key_type &k) |
void | clear () |
void | clear (bool clearBuckets) |
void | reset () |
void | rehash (size_type nBucketCount) |
iterator | find (const key_type &key) |
const_iterator | find (const key_type &key) const |
template<typename U , typename UHash , typename BinaryPredicate > | |
iterator | find_as (const U &u, UHash uhash, BinaryPredicate predicate) |
template<typename U , typename UHash , typename BinaryPredicate > | |
const_iterator | find_as (const U &u, UHash uhash, BinaryPredicate predicate) const |
template<typename U > | |
iterator | find_as (const U &u) |
template<typename U > | |
const_iterator | find_as (const U &u) const |
iterator | find_by_hash (hash_code_t c) |
const_iterator | find_by_hash (hash_code_t c) const |
size_type | count (const key_type &k) const |
eastl::pair< iterator, iterator > | equal_range (const key_type &k) |
eastl::pair< const_iterator, const_iterator > | equal_range (const key_type &k) const |
bool | validate () const |
int | validate_iterator (const_iterator i) const |
Static Public Attributes | |
static const bool | kCacheHashCode = bCacheHashCode |
Protected Member Functions | |
node_type * | DoAllocateNode (const value_type &value) |
node_type * | DoAllocateNodeFromKey (const key_type &key) |
void | DoFreeNode (node_type *pNode) |
void | DoFreeNodes (node_type **pBucketArray, size_type) |
node_type ** | DoAllocateBuckets (size_type n) |
void | DoFreeBuckets (node_type **pBucketArray, size_type n) |
eastl::pair< iterator, bool > | DoInsertValue (const value_type &value, true_type) |
iterator | DoInsertValue (const value_type &value, false_type) |
eastl::pair< iterator, bool > | DoInsertKey (const key_type &key, true_type) |
iterator | DoInsertKey (const key_type &key, false_type) |
void | DoRehash (size_type nBucketCount) |
node_type * | DoFindNode (node_type *pNode, const key_type &k, hash_code_t c) const |
template<typename U , typename BinaryPredicate > | |
node_type * | DoFindNode (node_type *pNode, const U &u, BinaryPredicate predicate) const |
node_type * | DoFindNode (node_type *pNode, hash_code_t c) const |
Protected Attributes | |
node_type ** | mpBucketArray |
size_type | mnBucketCount |
size_type | mnElementCount |
RehashPolicy | mRehashPolicy |
allocator_type | mAllocator |
hashtable
Key and Value: arbitrary CopyConstructible types.
ExtractKey: function object that takes a object of type Value and returns a value of type Key.
Equal: function object that takes two objects of type k and returns a bool-like value that is true if the two objects are considered equal.
H1: a hash function. A unary function object with argument type Key and result type size_t. Return values should be distributed over the entire range [0, numeric_limits<uint32_t>::max()].
H2: a range-hashing function (in the terminology of Tavori and Dreizin). This is a function which takes the output of H1 and converts it to the range of [0, n]. Usually it merely takes the output of H1 and mods it to n.
H: a ranged hash function (Tavori and Dreizin). This is merely a class that combines the functionality of H1 and H2 together, possibly in some way that is somehow improved over H1 and H2 It is a binary function whose argument types are Key and size_t and whose result type is uint32_t. Given arguments k and n, the return value is in the range [0, n). Default: h(k, n) = h2(h1(k), n). If H is anything other than the default, H1 and H2 are ignored, as H is thus overriding H1 and H2.
RehashPolicy: Policy class with three members, all of which govern the bucket count. nBucket(n) returns a bucket count no smaller than n. GetBucketCount(n) returns a bucket count appropriate for an element count of n. GetRehashRequired(nBucketCount, nElementCount, nElementAdd) determines whether, if the current bucket count is nBucket and the current element count is nElementCount, we need to increase the bucket count. If so, returns pair(true, n), where n is the new bucket count. If not, returns pair(false, <anything>).
Currently it is hard-wired that the number of buckets never shrinks. Should we allow RehashPolicy to change that?
bCacheHashCode: true if we store the value of the hash function along with the value. This is a time-space tradeoff. Storing it may improve lookup speed by reducing the number of times we need to call the Equal function.
bMutableIterators: true if hashtable::iterator is a mutable iterator, false if iterator and const_iterator are both const iterators. This is true for hash_map and hash_multimap, false for hash_set and hash_multiset.
bUniqueKeys: true if the return value of hashtable::count(k) is always at most one, false if it may be an arbitrary number. This is true for hash_set and hash_map and is false for hash_multiset and hash_multimap.
Note: If you want to make a hashtable never increase its bucket usage, call set_max_load_factor with a very high value such as 100000.f.
find_as In order to support the ability to have a hashtable of strings but be able to do efficiently lookups via char pointers (i.e. so they aren't converted to string objects), we provide the find_as function. This function allows you to do a find with a key of a type other than the hashtable key type. See the find_as function for more documentation on this.
find_by_hash In the interest of supporting fast operations wherever possible, we provide a find_by_hash function which finds a node using its hash code. This is useful for cases where the node's hash is already known, allowing us to avoid a redundant hash operation in the normal find path.
Definition at line 788 of file hashtable_eastl.h.
|
inline |
Generalization of get_max_load_factor. This is an extension that's not present in TR1.
Definition at line 933 of file hashtable_eastl.h.
|
inline |
Generalization of set_max_load_factor. This is an extension that's not present in TR1.
Definition at line 1373 of file hashtable_eastl.h.
|
inline |
Implements a find whereby the user supplies a comparison of a different type than the hashtable value_type. A useful case of this is one whereby you have a container of string objects but want to do searches via passing in char pointers. The problem is that without this kind of find, you need to do the expensive operation of converting the char pointer to a string so it can be used as the argument to the find function.
Example usage (namespaces omitted for brevity): hash_set<string> hashSet; hashSet.find_as("hello"); // Use default hash and compare.
Example usage (note that the predicate uses string as first type and char* as second): hash_set<string> hashSet; hashSet.find_as("hello", hash<char*>(), equal_to_2<string, char*>());
Definition at line 1417 of file hashtable_eastl.h.
|
inline |
Implements a find whereby the user supplies the node's hash code.
Definition at line 1491 of file hashtable_eastl.h.