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 >:

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< iteratorreverse_iterator
 
typedef eastl::reverse_iterator< const_iteratorconst_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_iteratorequal_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_typeDoAllocateNode (const value_type &value)
 
node_typeDoAllocateNodeFromKey (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_typeDoFindNode (node_type *pNode, const key_type &k, hash_code_t c) const
 
template<typename U , typename BinaryPredicate >
node_typeDoFindNode (node_type *pNode, const U &u, BinaryPredicate predicate) const
 
node_typeDoFindNode (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

◆ rehash_policy() [1/2]

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.

◆ rehash_policy() [2/2]

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.

◆ find_as()

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.

◆ find_by_hash()

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: