FX::QSortedList< type, allocator > Class Template Reference
[Qt Template Library]

#include <qsortedlist.h>

Inheritance diagram for FX::QSortedList< type, allocator >:

List of all members.

---

Detailed Description

template<class type, class allocator>
class FX::QSortedList< type, allocator >

An always sorted ptr list with binary searching.

This is one of probably the first five classes I wrote for Tornado and it's basically an always sorted FX::QPtrList. The list is always sorted according to the < and == operators you provide for your list item and find() performs a binary instead of a linear search. Binary searches are extremely efficient on sorted data with O(lg n) most compares as compared against O(n) for linear searches. On a 1024 item list, this means a maximum of ten compares as against 1024 compares!

Note:

This QSortedList does not bear ANY resemblance to Qt's one of the same name. This one is MUCH more useful!

Warning:

You want to be cautious of remove() and take() - this uses the same comparator as the find() function which means if your comparator is loose for easier searching, often the wrong item will get deleted. Use removeRef() and takeRef() for these situations - you still get most of the speed of the binary search but with guaranteed removal of a particular pointer.

Definition at line 52 of file qsortedlist.h.

Public Member Functions
	QSortedList (bool wantAutoDel=false)
	QSortedList (const QSortedList< type, allocator > &o)
	~QSortedList ()
QSortedList< type, allocator > &	operator= (const QSortedList< type, allocator > &l)
bool	operator== (const QSortedList< type, allocator > &list) const
virtual int	compareItems (type *a, type *b) const
bool	remove (const type *d)
bool	removeRef (const type *d)
bool	take (const type *d)
bool	takeRef (const type *d)
int	find (const type *d) const
QSortedListIterator< type, allocator >	findIter (const type *d) const
type *	findP (const type *d) const
int	findClosest (const type *d) const
QSortedListIterator< type, allocator >	findClosestIter (const type *d) const
type *	findClosestP (const type *d) const
bool	insert (const type *d)
void	merge (QSortedList< type, allocator > &list, bool exclusive=false)
template<>
int	compareItems (void *a, void *b) const

---

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

• qsortedlist.h

---

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