FX::QDictBase< keytype, type > Class Template Reference

#include <qdictbase.h>

Inheritance diagram for FX::QDictBase< keytype, type >:

List of all members.

---

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::vector of std::map of item key to pair of key hash and std::vector of pointers to items. Therefore, each entry minimally consumes an entry in std::map, a whole std::vector plus 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::map is 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::map than to add a new entry (which involves constructing a new std::vector and 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.

Definition at line 70 of file qdictbase.h.

Public Types
typedef keytype	KeyType
typedef type	ItemType
	HasSlowKeyCompare
enum	{ HasSlowKeyCompare }
Public Member Functions
	QDictBase (uint _size, bool wantAutoDel=false)
	~QDictBase ()
	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 >

---

The documentation for this class was generated from the following file:

• qdictbase.h

---

(C) 2002-2009 Niall Douglas. Some parts (C) to assorted authors.