An unordered data structure mapping keys to values. More...

Classes
class	Entry
	The pairs returned by iterator. More...

class	Iterator
	C++ STL style iterator variable. More...

Public Member Functions
	Table ()
	Creates an empty hash table using the default MemoryManager. More...

	Table (const ThisType &h)
	Uses the default memory manager. More...

virtual	~Table ()
	Destroys all of the memory allocated by the table, but does not call delete on keys or values if they are pointers. More...

Iterator	begin () const
	C++ STL style iterator method. More...

void	clear ()
	Removes all elements. More...

void	clearAndSetMemoryManager (const shared_ptr< MemoryManager > &m)
	Changes the internal memory manager to m. More...

bool	containsKey (const Key &key) const
	Returns true if key is in the table. More...

bool	containsValue (const Value &value) const
	Returns true if any key maps to value using operator==. More...

float	debugGetAverageBucketSize () const
	Returns the average size of non-empty buckets. More...

size_t	debugGetDeepestBucketSize () const
	Returns the length of the deepest m_bucket. More...

double	debugGetLoad () const
	A small load (close to zero) means the hash table is acting very efficiently most of the time. More...

size_t	debugGetNumBuckets () const
	Returns the number of buckets. More...

void	debugPrintStatus ()

void	deleteKeys ()
	Calls delete on all of the keys and then clears the table. More...

void	deleteValues ()
	Calls delete on all of the values. More...

const Iterator	end () const
	C++ STL style iterator method. More...

Value &	get (const Key &key) const
	Returns the value associated with key. More...

bool	get (const Key &key, Value &val) const
	If the key is present in the table, val is set to the associated value and returns true. More...

Value &	getCreate (const Key &key)
	Returns the current value that key maps to, creating it if necessary. More...

Value &	getCreate (const Key &key, bool &created)

Entry &	getCreateEntry (const Key &key, bool &created)
	Called by getCreate() and set() More...

Entry &	getCreateEntry (const Key &key)

const Key *	getKeyPointer (const Key &key) const
	If a value that is EqualsFunc to member is present, returns a pointer to the version stored in the data structure, otherwise returns nullptr. More...

Array< Key >	getKeys () const
	Returns an array of all of the keys in the table. More...

void	getKeys (Array< Key > &keyArray) const

Value *	getPointer (const Key &key) const
	Returns a pointer to the element if it exists, or nullptr if it does not. More...

bool	getRemove (const Key &key, Key &removedKey, Value &removedValue)
	If member is present, sets removed to the element being removed and returns true. More...

void	getValues (Array< Value > &valueArray) const
	Will contain duplicate values if they exist in the table. More...

template<class H , class E >
bool	operator!= (const Table< Key, Value, H, E > &other) const

Table &	operator= (const ThisType &h)

template<class H , class E >
bool	operator== (const Table< Key, Value, H, E > &other) const

Value &	operator[] (const Key &key) const
	Short syntax for get. More...

bool	remove (const Key &key)
	Removes an element from the table if it is present. More...

void	set (const Key &key, const Value &value)
	If you insert a pointer into the key or value of a table, you are responsible for deallocating the object eventually. More...

void	setSizeHint (size_t n)
	Recommends that the table resize to anticipate at least this number of elements. More...

size_t	size () const
	Returns the number of keys. More...

Detailed Description

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>
class G3D::Table< Key, Value, HashFunc, EqualsFunc >

An unordered data structure mapping keys to values.

There are two ways of definining custom hash functions (G3D provides built-in ones for most classes):

class Foo {
public:
    String     name;
    int             index;
    static size_t hashCode(const Foo& key) {
         return HashTrait<String>::hashCode(key.name) + key.index;
    }
 };

 template<> struct HashTrait<class Foo> {
      static size_t hashCode(const Foo& key) { return HashTrait<String>::hashCode(key.name) + key.index; }
 };

 // Use Foo::hashCode
 Table<Foo, String, Foo> fooTable1;

 // Use HashTrait<Foo>
 Table<Foo, String>      fooTable2;

Key must be a pointer, an int, a String or provide overloads for:

   template<> struct HashTrait<class Key> {
       static size_t hashCode(const Key& key) { return reinterpret_cast<size_t>( ... ); }
   };

and one of

   template<> struct EqualsTrait<class Key>{
        static bool equals(const Key& a, const Key& b) { return ... ; }
   };

   bool operator==(const Key&, const Key&);

G3D pre-defines HashTrait specializations for common types (like int and String). If you use a Table with a different type you must write those functions yourself. For example, an enum would use:

   template<> struct HashTrait<MyEnum> {
       static size_t hashCode(const MyEnum& key) const { return reinterpret_cast<size_t>( key ); }
   };

And rely on the default enum operator==.

Periodically check that debugGetLoad() is low (> 0.1). When it gets near 1.0 your hash function is badly designed and maps too many inputs to the same output.

Constructor & Destructor Documentation

◆ Table() [1/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

G3D::Table< Key, Value, HashFunc, EqualsFunc >::Table ( )

inline

Creates an empty hash table using the default MemoryManager.

◆ ~Table()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

virtual G3D::Table< Key, Value, HashFunc, EqualsFunc >::~Table ( )

inlinevirtual

Destroys all of the memory allocated by the table, but does not call delete on keys or values if they are pointers.

If you want to deallocate things that the table points at, use getKeys() and Array::deleteAll() to delete them.

◆ Table() [2/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

G3D::Table< Key, Value, HashFunc, EqualsFunc >::Table ( const ThisType & h )

inline

Uses the default memory manager.

Member Function Documentation

◆ begin()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Iterator G3D::Table< Key, Value, HashFunc, EqualsFunc >::begin ( ) const

inline

C++ STL style iterator method.

Returns the first Entry, which contains a key and value. Use preincrement (++entry) to get to the next element. Do not modify the table while iterating.

Referenced by G3D::Set< size_t >::begin(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::begin(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::begin(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::clear(), G3D::Table< String, double >::containsValue(), G3D::Table< String, double >::operator==(), and G3D::Pathfinder< Node, HashFunc >::PriorityQueue< Key, Value >::removeMin().

◆ clear()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::clear ( )

inline

Removes all elements.

Guaranteed to free all memory associated with the table.

Referenced by G3D::WeakCache< G3D::Sampler, shared_ptr< G3D::GLSamplerObject > >::clear(), G3D::Set< size_t >::clear(), G3D::OrderedTable< Key, Value >::clear(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clear(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::clear(), G3D::Table< String, double >::clearAndSetMemoryManager(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clearData(), G3D::UniformTable::clearUniformBindings(), G3D::Table< String, double >::deleteKeys(), and G3D::Pathfinder< Node, HashFunc >::findPath().

◆ clearAndSetMemoryManager()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::clearAndSetMemoryManager ( const shared_ptr< MemoryManager > & m )

inline

Changes the internal memory manager to m.

Referenced by G3D::categorizeByDerivedType(), and G3D::Set< size_t >::clearAndSetMemoryManager().

◆ containsKey()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

bool G3D::Table< Key, Value, HashFunc, EqualsFunc >::containsKey ( const Key & key ) const

inline

Returns true if key is in the table.

Referenced by G3D::Set< size_t >::contains(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::contains(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::contains(), G3D::XML::containsAttribute(), G3D::OrderedTable< Key, Value >::containsKey(), G3D::UniformTable::hasUniform(), G3D::Pathfinder< Node, HashFunc >::PriorityQueue< Key, Value >::insert(), G3D::WeakCache< G3D::Sampler, shared_ptr< G3D::GLSamplerObject > >::operator[](), and G3D::WeakCache< G3D::Sampler, shared_ptr< G3D::GLSamplerObject > >::remove().

◆ containsValue()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

bool G3D::Table< Key, Value, HashFunc, EqualsFunc >::containsValue ( const Value & value ) const

inline

Returns true if any key maps to value using operator==.

◆ debugGetAverageBucketSize()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

float G3D::Table< Key, Value, HashFunc, EqualsFunc >::debugGetAverageBucketSize ( ) const

inline

Returns the average size of non-empty buckets.

Referenced by G3D::Table< String, double >::debugPrintStatus().

◆ debugGetDeepestBucketSize()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

size_t G3D::Table< Key, Value, HashFunc, EqualsFunc >::debugGetDeepestBucketSize ( ) const

inline

Returns the length of the deepest m_bucket.

Referenced by G3D::Table< String, double >::debugPrintStatus().

◆ debugGetLoad()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

double G3D::Table< Key, Value, HashFunc, EqualsFunc >::debugGetLoad ( ) const

inline

A small load (close to zero) means the hash table is acting very efficiently most of the time.

A large load (close to 1) means the hash table is acting poorly– all operations will be very slow. A large load will result from a bad hash function that maps too many keys to the same code.

Referenced by G3D::Table< String, double >::debugPrintStatus().

◆ debugGetNumBuckets()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

size_t G3D::Table< Key, Value, HashFunc, EqualsFunc >::debugGetNumBuckets ( ) const

inline

Returns the number of buckets.

◆ debugPrintStatus()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::debugPrintStatus ( )

inline

◆ deleteKeys()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::deleteKeys ( )

inline

Calls delete on all of the keys and then clears the table.

◆ deleteValues()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::deleteValues ( )

inline

Calls delete on all of the values.

This is unsafe– do not call unless you know that each value appears at most once.

Does not clear the table, so you are left with a table of nullptr pointers.

◆ end()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

const Iterator G3D::Table< Key, Value, HashFunc, EqualsFunc >::end ( ) const

inline

C++ STL style iterator method.

Returns one after the last iterator element.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::clear(), G3D::Set< size_t >::end(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::end(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::end().

◆ get() [1/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Value& G3D::Table< Key, Value, HashFunc, EqualsFunc >::get ( const Key & key ) const

inline

Returns the value associated with key.

Deprecated:: Use get(key, val) or getPointer(key)

◆ get() [2/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

bool G3D::Table< Key, Value, HashFunc, EqualsFunc >::get	(	const Key &	key,
		Value &	val
	)		const

inline

If the key is present in the table, val is set to the associated value and returns true.

If the key is not present, returns false.

◆ getCreate() [1/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Value& G3D::Table< Key, Value, HashFunc, EqualsFunc >::getCreate ( const Key & key )

inline

Returns the current value that key maps to, creating it if necessary.

Referenced by G3D::categorizeByDerivedType(), G3D::Pathfinder< Node, HashFunc >::findPath(), G3D::Set< size_t >::insert(), and G3D::OrderedTable< Key, Value >::set().

◆ getCreate() [2/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Value& G3D::Table< Key, Value, HashFunc, EqualsFunc >::getCreate	(	const Key &	key,
		bool &	created
	)

inline

Parameters

created True if the element was created.

◆ getCreateEntry() [1/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Entry& G3D::Table< Key, Value, HashFunc, EqualsFunc >::getCreateEntry	(	const Key &	key,
		bool &	created
	)

inline

Called by getCreate() and set()

Parameters

created Set to true if the entry was created by this method.

Referenced by G3D::Table< String, double >::getCreate(), G3D::Table< String, double >::getCreateEntry(), and G3D::Table< String, double >::set().

◆ getCreateEntry() [2/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Entry& G3D::Table< Key, Value, HashFunc, EqualsFunc >::getCreateEntry ( const Key & key )

inline

◆ getKeyPointer()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

const Key* G3D::Table< Key, Value, HashFunc, EqualsFunc >::getKeyPointer ( const Key & key ) const

inline

If a value that is EqualsFunc to member is present, returns a pointer to the version stored in the data structure, otherwise returns nullptr.

Referenced by G3D::Set< size_t >::getPointer(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getPointer().

◆ getKeys() [1/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Array<Key> G3D::Table< Key, Value, HashFunc, EqualsFunc >::getKeys ( ) const

inline

Returns an array of all of the keys in the table.

You can iterate over the keys to get the values.

Deprecated:

Referenced by G3D::Table< String, double >::getKeys(), G3D::Set< size_t >::getMembers(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::getMembers(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getMembers(), and G3D::WeakCache< G3D::Sampler, shared_ptr< G3D::GLSamplerObject > >::getValues().

◆ getKeys() [2/2]

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::getKeys ( Array< Key > & keyArray ) const

inline

◆ getPointer()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Value* G3D::Table< Key, Value, HashFunc, EqualsFunc >::getPointer ( const Key & key ) const

inline

Returns a pointer to the element if it exists, or nullptr if it does not.

Note that if your value type is a pointer, the return value is a pointer to a pointer. Do not remove the element while holding this pointer.

It is easy to accidentally mis-use this method. Consider making a Table<Value*> and using get(key, val) instead, which makes you manage the memory for the values yourself and is less likely to result in pointer errors.

Referenced by G3D::UniversalMaterial::constant(), G3D::OrderedTable< Key, Value >::findIndexOfKey(), G3D::XML::get(), G3D::Table< String, double >::get(), G3D::SmallTable< Key, Value, HashFunc, EqualsFunc >::operator==(), and G3D::Table< String, double >::operator==().

◆ getRemove()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

bool G3D::Table< Key, Value, HashFunc, EqualsFunc >::getRemove	(	const Key &	key,
		Key &	removedKey,
		Value &	removedValue
	)

inline

If member is present, sets removed to the element being removed and returns true.

Otherwise returns false and does not write to removed.

Referenced by G3D::Set< size_t >::getRemove().

◆ getValues()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::getValues ( Array< Value > & valueArray ) const

inline

Will contain duplicate values if they exist in the table.

This array is parallel to the one returned by getKeys() if the table has not been modified.

◆ operator!=()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

template<class H , class E >

bool G3D::Table< Key, Value, HashFunc, EqualsFunc >::operator!= ( const Table< Key, Value, H, E > & other ) const

inline

◆ operator=()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Table& G3D::Table< Key, Value, HashFunc, EqualsFunc >::operator= ( const ThisType & h )

inline

◆ operator==()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

template<class H , class E >

bool G3D::Table< Key, Value, HashFunc, EqualsFunc >::operator== ( const Table< Key, Value, H, E > & other ) const

inline

◆ operator[]()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

Value& G3D::Table< Key, Value, HashFunc, EqualsFunc >::operator[] ( const Key & key ) const

inline

Short syntax for get.

◆ remove()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

bool G3D::Table< Key, Value, HashFunc, EqualsFunc >::remove ( const Key & key )

inline

Removes an element from the table if it is present.

Returns: true if the element was found and removed, otherwise false

◆ set()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::set	(	const Key &	key,
		const Value &	value
	)

inline

If you insert a pointer into the key or value of a table, you are responsible for deallocating the object eventually.

Inserting key into a table is O(1), but may cause a potentially slow rehashing.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::cloneTree(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::cloneTree(), G3D::Pathfinder< Node, HashFunc >::findPath(), G3D::Pathfinder< Node, HashFunc >::PriorityQueue< Key, Value >::insert(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::insert(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::insert(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::makeNode(), G3D::WeakCache< G3D::Sampler, shared_ptr< G3D::GLSamplerObject > >::set(), and G3D::UniversalMaterial::Specification::setConstant().

◆ setSizeHint()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

void G3D::Table< Key, Value, HashFunc, EqualsFunc >::setSizeHint ( size_t n )

inline

Recommends that the table resize to anticipate at least this number of elements.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::insert().

◆ size()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>

size_t G3D::Table< Key, Value, HashFunc, EqualsFunc >::size ( ) const

inline

Returns the number of keys.

Referenced by G3D::Table< String, double >::debugGetAverageBucketSize(), G3D::Table< String, double >::debugGetLoad(), G3D::Args::hasStreamArgs(), G3D::Pathfinder< Node, HashFunc >::PriorityQueue< Key, Value >::length(), G3D::XML::numAttributes(), G3D::SmallTable< Key, Value, HashFunc, EqualsFunc >::operator==(), G3D::Table< String, double >::operator==(), G3D::Set< size_t >::size(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::size(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::size().

Classes

Public Member Functions

Detailed Description

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>> class G3D::Table< Key, Value, HashFunc, EqualsFunc >

Constructor & Destructor Documentation

◆ Table() [1/2]

◆ ~Table()

◆ Table() [2/2]

Member Function Documentation

◆ begin()

◆ clear()

◆ clearAndSetMemoryManager()

◆ containsKey()

◆ containsValue()

◆ debugGetAverageBucketSize()

◆ debugGetDeepestBucketSize()

◆ debugGetLoad()

◆ debugGetNumBuckets()

◆ debugPrintStatus()

◆ deleteKeys()

◆ deleteValues()

◆ end()

◆ get() [1/2]

◆ get() [2/2]

◆ getCreate() [1/2]

◆ getCreate() [2/2]

◆ getCreateEntry() [1/2]

◆ getCreateEntry() [2/2]

◆ getKeyPointer()

◆ getKeys() [1/2]

◆ getKeys() [2/2]

◆ getPointer()

◆ getRemove()

◆ getValues()

◆ operator!=()

◆ operator=()

◆ operator==()

◆ operator[]()

◆ remove()

◆ set()

◆ setSizeHint()

◆ size()

template<class Key, class Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>>
class G3D::Table< Key, Value, HashFunc, EqualsFunc >