FX::QDictBase< keytype, type > Class Template Reference
#include <qdictbase.h>
Detailed Description
template<class keytype, class type>
class FX::QDictBase< keytype, type >
Base implementation class for all QTL dictionary classes.
Some notes on observed behaviour deduced by real-world testing:
- Dictionary is a
std::vectorofstd::mapof item key to pair of key hash andstd::vectorof pointers to items. Therefore, each entry minimally consumes an entry instd::map, a wholestd::vectorplus a copy of the key. - Lookup time as well as insertion and deletion time should approach O(1) when dictionary table is 50% greater or more than item count. As
std::mapis O(log N), it approaches that as dictionary table size becomes relatively lower. - Empirical testing shows an interesting abberation on MSVC (Dinkumware STL) and GCC (SGI STL) - it's about 40% quicker to insert & delete within a
std::mapthan to add a new entry (which involves constructing a newstd::vectorand more importantly, copy constructing it a number of times). If the default memory allocator is used on Win32 the difference gets much worse. - dictionaryBias() is lookups less insert/removes - therefore to be biased in favour of lookups they must outnumber inserts by twice.
Public Types | |
| enum | { HasSlowKeyCompare } |
| typedef keytype | KeyType |
| typedef type | ItemType |
Public Member Functions | |
| QDictBase (uint _size, bool wantAutoDel=false) | |
| QDictBase (const QDictBase< keytype, type > &o) | |
| QDictBase< keytype, type > & | operator= (const QDictBase< keytype, type > &o) |
| bool | autoDelete () const |
| void | setAutoDelete (bool a) |
| uint | count () const |
| bool | isEmpty () const |
| uint | size () const |
| void | clear () |
| void | append (const QDictBase< keytype, type > &o) |
| QDictBase< keytype, type > & | operator+= (const QDictBase< keytype, type > &o) |
| void | resize (uint newsize) |
| void | safeResize (uint newsize) throw () |
| void | spread (float *full, float *slotsspread, float *avrgkeysperslot, float *spread) const |
| void | statistics () const |
| FXint | dictionaryBias () const throw () |
Protected Types | |
|
typedef std::map< keytype, hashitemlist > | keyitemlist |
| typedef keyitemlist::value_type | keyitem |
Protected Member Functions | |
| keyitem * | findKey (FXuint h, const keytype &k) |
| const keyitem * | findKey (FXuint h, const keytype &k) const |
| void | insert (FXuint h, const keytype &k, type *d) |
| void | replace (FXuint h, const keytype &k, type *d) |
| bool | remove (FXuint h, const keytype &k) |
| type * | take (FXuint h, const keytype &k) |
| type * | find (FXuint h, const keytype &k) const |
| virtual void | deleteItem (type *d)=0 |
Friends | |
| class | QDictBaseIterator< keytype, type > |
Member Typedef Documentation
| typedef keytype FX::QDictBase< keytype, type >::KeyType |
The type of the key.
| typedef type FX::QDictBase< keytype, type >::ItemType |
The type of the container's item.
Member Function Documentation
| bool FX::QDictBase< keytype, type >::autoDelete | ( | ) | const [inline] |
Returns if auto-deletion is enabled.
| void FX::QDictBase< keytype, type >::setAutoDelete | ( | bool | a | ) | [inline] |
Sets if auto-deletion is enabled.
| uint FX::QDictBase< keytype, type >::count | ( | ) | const [inline] |
Returns the number of items in the list.
| bool FX::QDictBase< keytype, type >::isEmpty | ( | ) | const [inline] |
Returns true if the list is empty.
| uint FX::QDictBase< keytype, type >::size | ( | ) | const [inline] |
Returns the size of the hash table.
| void FX::QDictBase< keytype, type >::clear | ( | ) | [inline] |
Clears the list of items, auto-deleting if enabled.
| void FX::QDictBase< keytype, type >::append | ( | const QDictBase< keytype, type > & | o | ) | [inline] |
Appends the contents of another dictionary.
Referenced by FX::QDictBase< FX::FXString, type >::operator+=().
| QDictBase<keytype, type>& FX::QDictBase< keytype, type >::operator+= | ( | const QDictBase< keytype, type > & | o | ) | [inline] |
| void FX::QDictBase< keytype, type >::resize | ( | uint | newsize | ) | [inline] |
Resizes the hash table (see QDICTDYNRESIZE()). Invalidates all iterators.
| void FX::QDictBase< keytype, type >::safeResize | ( | uint | newsize | ) | throw () [inline] |
Resizes the hash table with no threat of memory full exceptions. Invalidates all iterators.
| void FX::QDictBase< keytype, type >::spread | ( | float * | full, | |
| float * | slotsspread, | |||
| float * | avrgkeysperslot, | |||
| float * | spread | |||
| ) | const [inline] |
Returns statistics useful for dynamic balancing of the table. If full exceeds 100%, then there are more items than slots and the table is no longer performing at maximum efficiency. If slotsspread is less than 50% then the hash function is broken. Ideally for performance purposes avrgkeysperslot should be near 1.0 and finally spread is slotsspread divided by avrgskeysperslot which is an overall indication of spread and thus efficiency of the table. Of course maximum efficiency is pointless for very large sets of data where avrgkeysperslot could be as much as eight - but slotsspread should always be near 100%
Referenced by FX::QDictBase< FX::FXString, type >::statistics().
| void FX::QDictBase< keytype, type >::statistics | ( | ) | const [inline] |
Prints some statistics about the hash table (only debug builds).
Reimplemented in FX::FXLRUCache< FX::QIntDict< type > >, and FX::FXLRUCache< FX::QDict< type > >.
| FXint FX::QDictBase< keytype, type >::dictionaryBias | ( | ) | const throw () [inline] |
Returns a number indicating how biased between lookups and insert/removals the usage of this dictionary has been so far. Is negative for more insert/removals than lookups and positive for the opposite.
The documentation for this class was generated from the following file:
