Sierra Toolkit Version of the Day
eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys > Class Template Reference

#include <hashtable_eastl.h>

Inheritance diagram for eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >:
Collaboration diagram for eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >:

List of all members.

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_typeoperator= (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, iteratorequal_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

Detailed Description

template<typename Key, typename Value, typename Allocator, typename ExtractKey, typename Equal, typename H1, typename H2, typename H, typename RehashPolicy, bool bCacheHashCode, bool bMutableIterators, bool bUniqueKeys>
class eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >

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.


Member Function Documentation

template<typename Key, typename Value, typename Allocator, typename ExtractKey, typename Equal, typename H1, typename H2, typename H, typename RehashPolicy, bool bCacheHashCode, bool bMutableIterators, bool bUniqueKeys>
const rehash_policy_type& eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >::rehash_policy ( ) const [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.

template<typename K , typename V , typename A , typename EK , typename Eq , typename H1 , typename H2 , typename H , typename RP , bool bC, bool bM, bool bU>
void eastl::hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::rehash_policy ( const rehash_policy_type &  rehashPolicy) [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.

template<typename K , typename V , typename A , typename EK , typename Eq , typename H1 , typename H2 , typename H , typename RP , bool bC, bool bM, bool bU>
template<typename U , typename UHash , typename BinaryPredicate >
hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator eastl::hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::find_as ( const U &  u,
UHash  uhash,
BinaryPredicate  predicate 
) [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.

template<typename K , typename V , typename A , typename EK , typename Eq , typename H1 , typename H2 , typename H , typename RP , bool bC, bool bM, bool bU>
hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator eastl::hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::find_by_hash ( hash_code_t  c) [inline]

Implements a find whereby the user supplies the node's hash code.

Definition at line 1491 of file hashtable_eastl.h.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends