SortedList_t< T, K > Class Template Reference
Template sorted list class, implemented as an array of sorted pointers to T.
More...
#include <UTLists.h>
List of all members.
Detailed Description
template<class T, class K>
class SortedList_t< T, K >
Template sorted list class, implemented as an array of sorted pointers to T. This form of list has somewhat better search efficiency than that of BTree_t, good tail addition efficiency, but the worst possible head addition, insertion, or removal efficiency.
class T must implement a Compare(K key) const function which returns a signed integer. If this comes before key, T::Compare should return a negative number. If this comes after key, T::Compare should return a positive number. If this equals key, T::Compare should return 0. The compare function can be inline. If it would be more efficient (if the key type is not a] basic type or pointer), the Compare function can and probably should be implemented as Compare(const K& key) const instead.
class T must implement a const operator K or const operator const K& (depending on which is more efficient for the node type). That operator can, and usually should, be inline. The declaration would typically be of one of these forms:
inline operator K() const;
inline operator const K&() const;
It is appropriate for use when the list will be initialized once, but after creation, searched often. If items will be added and removed dynamically, a BTree_t should definitely be used instead. Due to the poor insertion efficiency, if the list could be initialized with a large number of items which are not added in pre-sorted order, the list should be initially created using AddTail with will_sort_later being true, then sorted using the Sort function once all items have been added.
Definition at line 545 of file UTLists.h.
Constructor & Destructor Documentation
template<class T , class K >
Constructor for an empty list.
Definition at line 2822 of file UTLists.h.
template<class T, class K >
Constructor for a list which initially uses a stack-allocated buffer of the specified size. If the required size grows beyond that size, the buffer will be reallocated from the heap.
Definition at line 2832 of file UTLists.h.
template<class T , class K >
Destructor. The internal buffer will be deleted unless a stack buffer was provided in the constructor and the buffer never grew to the point of having been reallocated from the heap.
Definition at line 2841 of file UTLists.h.
Member Function Documentation
template<class T , class K>
| T * SortedList_t< T, K >::FindItem |
( |
K |
key, |
|
|
out int * |
index = NULL | |
|
) |
| | const [inline] |
Searches the list for an item with a matching key, returning it if it is found, or NULL if it is not. If index is not NULL, the index of the item found will be returned through it, where the head is index 0. If no item was found, -1 will be returned through index. If multiple items have the same key, the matching item closest to the head will be returned.
Definition at line 3042 of file UTLists.h.
template<class T , class K>
| T * SortedList_t< T, K >::FindItemAtOrBefore |
( |
K |
key, |
|
|
out int * |
index = NULL | |
|
) |
| | const [inline] |
Searches the list for an item with a matching key, returning it if it is found, the item immediately before key if an exact match was not found, or NULL if no such item exists. If index is not NULL, the index of the item found will be returned through it, where the head is index 0. If no item was found, -1 will be returned through index. If multiple items have the same key, the matching item closest to the tail will be returned.
Definition at line 3059 of file UTLists.h.
template<class T , class K>
| T * SortedList_t< T, K >::FindItemAtOrAfter |
( |
K |
key, |
|
|
out int * |
index = NULL | |
|
) |
| | const [inline] |
Searches the list for an item with a matching key, returning it if it is found, the item immediately after key if an exact match was not found, or NULL if no such item exists. If index is not NULL, the index of the item found will be returned through it, where the head is index 0. If no item was found, -1 will be returned through index. If multiple items have the same key, the matching item closest to the head will be returned.
Definition at line 3076 of file UTLists.h.
template<class T, class K >
| T * SortedList_t< T, K >::IsInList |
( |
T * |
item |
) |
const [inline] |
Searches the list for the specified item, returning a pointer to it if it is found or NULL if it is not.
Definition at line 3489 of file UTLists.h.
template<class T, class K >
| void SortedList_t< T, K >::AddItem |
( |
T * |
new_item |
) |
[inline] |
Searches for the appropriate position in the list, and adds new_item at that location. If one or more items in the list already have the same key, the new item will be added closest to the tail. When used for insertion (as opposed to addition to the tail of the list), this is an expensive operation due to the necessity of shifting the list, so use this function with discretion or consider BTree_t instead.
Definition at line 3093 of file UTLists.h.
template<class T, class K >
Adds an item at the head of the list. The item to be added must sort before or match the key of the existing head item if one exists. This is an expensive operation due to the necessity of shifting the list, so use this function with discretion or consider BTree_t instead.
Definition at line 3148 of file UTLists.h.
template<class T, class K >
| void SortedList_t< T, K >::AddTail |
( |
T * |
item, |
|
|
bool |
will_sort_later = false | |
|
) |
| | [inline] |
Adds an item at the tail of the list. The item to be added must sort after or match the key of the existing tail item if one exists unless will_sort_later is true, in which case the list must be sorted before it can be used properly.
Definition at line 3201 of file UTLists.h.
template<class T , class K >
Sorts the list, which should be done after tail items have been added in an unsorted mode. This function is implemented using the mergesort algorithm because, even though it isn't always as fast as quicksort, mergesort has a constant O(n log n) sort time, while quicksort has a worst case O(n^2) sort time if it breaks down due to poor pivot selection. Even then, quicksort, although sometimes faster, still has an average O(n log n) sort time, making mergesort the clear choice. Moreover, mergesort is a stable sort, preserving the relative order of items with an equal sorting order.
Definition at line 3249 of file UTLists.h.
template<class T, class K >
Removes and returns the specified item from the list. This is an expensive operation when removing anything other than the tail due to the necessity of shifting the list, so use this function with discretion or consider BTree_t instead.
Definition at line 3502 of file UTLists.h.
template<class T , class K >
Removes and returns the item at the head of the list. This is an expensive operation due to the necessity of shifting the list, so use this function with discretion or consider BTree_t instead.
Definition at line 3521 of file UTLists.h.
template<class T , class K >
Removes and returns the item at the end of the list.
Definition at line 3533 of file UTLists.h.
template<class T , class K >
| T * SortedList_t< T, K >::RemoveItemAt |
( |
int |
index |
) |
[inline] |
Removes and returns the item at the specified position in the list, where the head is index 0. This is an expensive operation when removing anything other than the tail due to the necessity of shifting the list, so use this function with discretion or consider BTree_t instead.
Definition at line 3543 of file UTLists.h.
template<class T, class K >
Returns the index of the specified item, or -1 if it is not found. The list must be sorted for this to work.
Definition at line 3555 of file UTLists.h.
template<class T , class K >
Returns the number of items in the list.
Definition at line 3563 of file UTLists.h.
template<class T , class K >
Returns the item at the head of the list.
Definition at line 3571 of file UTLists.h.
template<class T , class K >
Returns the item at the end of the list.
Definition at line 3581 of file UTLists.h.
template<class T , class K >
| T * SortedList_t< T, K >::ItemAt |
( |
int |
index |
) |
const [inline] |
Returns the item at the specified position in the list, where the head is index 0.
Definition at line 3591 of file UTLists.h.
template<class T , class K >
| T & SortedList_t< T, K >::operator[] |
( |
int |
index |
) |
const [inline] |
Returns the item at the specified position in the list by reference, where the head is index 0.
Definition at line 3600 of file UTLists.h.
template<class T, class K >
| void SortedList_t< T, K >::operator+= |
( |
T * |
new_item |
) |
[inline] |
Searches for the appropriate position in the list, and adds new_item at that location. If one or more items in the list already have the same key, the new item will be added closest to the tail.
Definition at line 3609 of file UTLists.h.
template<class T, class K >
Searches for and removes the specified item from the list. This is an expensive operation when removing anything other than the tail due to the necessity of shifting the list, so use this function with discretion or consider BTree_t instead.
Definition at line 3617 of file UTLists.h.
The documentation for this class was generated from the following file:
- D:/develop/svn/utlib/utlib/trunk/UT/src_UT/UTLists.h
