FX::QDict< type > Class Template Reference
[Qt Template Library]
#include <qdict.h>
Detailed Description
template<class type>
class FX::QDict< type >
An implementation of Qt's QDict.
This implements a hash dictionary based on the STL but not using hash_multimap which comes with an average complexity approaching O(1) - however there is significantly more overhead to search this than a simple list and so it only really shines when it contains a lot of items. It should be near-optimum as when a collision occurs it uses a binary search through a sorted list to maximise efficiency even when the dictionary is extremely full. This means this container is suitable for very small hash table sizes or putting it another way, if the hash table is sized one then the container becomes a pure binary searched (O(log n) complexity) container.
When choosing a list size, choose a prime number and one not close to a power of two when possible. Always choose an odd number. See FX::fx2powerprimes().
Like Qt's QDict, ours maintains a list of all iterators traversing it. The reason a list must be maintained is to handle removals during iteration - without updating the iterators, the complex internal structure would require all iterators to become invalid (which would be very inefficient with large dictionaries never mind tricky to have disparate iterator owners inform each other of iterator invalidation).
Unlike Qt's QDict, removing items can invalidate iterators if you have lots of items stored per key. This could be fixed with extra implementational overhead (ask if you need it).
You may find the QDICTDYNRESIZE() and QDICTDYNRESIZEAGGR() macros useful but bear in mind iterators are thrown away when resize() is performed.
- Note:
- When case insensitive compares are enabled, all keys returned by QDictIterator will be lower case. This results from std::map not permitting a user value to be passed to the sort function and thus it can't determine whether to do a case insensitive comparison :(
Public Types | |
| enum | { HasSlowKeyCompare } |
| enum | { HasSlowKeyCompare } |
| typedef keytype | KeyType |
| typedef type | ItemType |
Public Member Functions | |
| QDict (int size=13, bool caseSensitive=true, bool wantAutoDel=false) | |
| QDict (const QDict< type > &o) | |
| bool | caseSensitive () const throw () |
| void | setCaseSensitive (bool c) throw () |
| void | insert (const FXString &k, const type *d) |
| void | replace (const FXString &k, const type *d) |
| bool | remove (const FXString &k) |
| type * | take (const FXString &k) |
| type * | find (const FXString &k) const |
| type * | operator[] (const FXString &k) const |
| template<> | |
| void | deleteItem (void *) |
| 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 | |
| virtual void | deleteItem (type *d) |
| 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 |
Member Typedef Documentation
typedef keytype FX::QDictBase< keytype, type >::KeyType [inherited] |
The type of the key.
typedef type FX::QDictBase< keytype, type >::ItemType [inherited] |
The type of the container's item.
Constructor & Destructor Documentation
| FX::QDict< type >::QDict | ( | int | size = 13, |
|
| bool | caseSensitive = true, |
|||
| bool | wantAutoDel = false | |||
| ) | [inline, explicit] |
Creates a hash table indexed by FXString's. Choose a prime for size.
Member Function Documentation
| bool FX::QDict< type >::caseSensitive | ( | ) | const throw () [inline] |
Returns if case sensitive key comparisons is enabled.
| void FX::QDict< type >::setCaseSensitive | ( | bool | c | ) | throw () [inline] |
Sets if case sensitive key comparisons is enabled.
Deletes the most recently placed item in the dictionary under key k.
References FX::FXString::lower().
Removes the most recently placed item in the dictionary under key k without auto-deletion.
References FX::FXString::lower().
Finds the most recently placed item in the dictionary under key k.
References FX::FXString::lower().
| bool FX::QDictBase< keytype, type >::autoDelete | ( | ) | const [inline, inherited] |
Returns if auto-deletion is enabled.
| void FX::QDictBase< keytype, type >::setAutoDelete | ( | bool | a | ) | [inline, inherited] |
Sets if auto-deletion is enabled.
| uint FX::QDictBase< keytype, type >::count | ( | ) | const [inline, inherited] |
Returns the number of items in the list.
| bool FX::QDictBase< keytype, type >::isEmpty | ( | ) | const [inline, inherited] |
Returns true if the list is empty.
| uint FX::QDictBase< keytype, type >::size | ( | ) | const [inline, inherited] |
Returns the size of the hash table.
| void FX::QDictBase< keytype, type >::clear | ( | ) | [inline, inherited] |
Clears the list of items, auto-deleting if enabled.
| void FX::QDictBase< keytype, type >::append | ( | const QDictBase< keytype, type > & | o | ) | [inline, inherited] |
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, inherited] |
| void FX::QDictBase< keytype, type >::resize | ( | uint | newsize | ) | [inline, inherited] |
Resizes the hash table (see QDICTDYNRESIZE()). Invalidates all iterators.
| void FX::QDictBase< keytype, type >::safeResize | ( | uint | newsize | ) | throw () [inline, inherited] |
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, inherited] |
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, inherited] |
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, inherited] |
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:
