Xavax C++ Library | Class Index FAQ Overview |
PTree<T> can access any element of the collection by key value or position in O(log2n) time where n is the collection size. This compares favorably with containers which require O(n) time such as PDList<T>. For example, when searching a collection of 1000 elements, PDList would traverse an average of 500 elements while PTree would traverse no more than 11 elements. However, this performance comes with a price. When inserting and removing elements, rotations must be performed to keep the tree balanced. Insertion can result in a single or double rotation while removal can result in multiple rotations as the change in subtree height propagates up the tree. The following diagram illustrates the two basic rotation types.
PTree<T> is an ordered collection;
therefore, it requires a means of comparing two elements
or an element and a key.
The client may provide a
compare functor and this is
highly recommended as it can result in
improved performance.
If the client does not provide a
compare functor,
then type T must implement operator==
and operator<
so that PTree<T>
can generate a default compare functor.
Constructor Summary |
PTree(CompareFunctor<T>& compareFunctor = defaultCompareFunctor)
Construct an empty tree. |
Method Summary | |
void
|
clear()
Remove all elements in the tree. |
size_t
|
count() const
Returns the number of elements in the tree. |
void
|
insert(const T* t)
Insert object t of type T into the tree. |
T*
|
locate(const T* key)
Locate and return a pointer to the element at position p. |
T*
|
locate(size_t p)
Locate and return a pointer to the element at position p. |
void
|
remove(const T* key)
Remove the element matching key .
|
void
|
remove(size_t p)
Remove the element at position p. |
void
|
traverse(TraversalOrder order,
TraverseFunctor
Traverse the tree in the specified order calling the traverse functor for each element. |
Related Classes | |
PTreeConstIterator<T>, PTreeIterator<T>, PTree<T> |
Constructor Detail |
PTree<T>(CompareFunctor<T>& compareFunctor = defaultCompareFunctor)
compareFunctor
-
a function that compares two objects of type T.
If a compare functor is not provided,
the default compare functor is used.
Method Detail |
void clear()
size_t count() const
void insert(const T& t)
t
- the object to be inserted.T* locate(const T* key)
key
.
key
- a key which the retrieved item must match.T* locate(size_t p)
p
- the position of the object to be retrieved.void remove(const T* key)
key
.
key
- an object that matches the object to be removed.void remove(size_t p)
p
- the position of the object to be removed.
RangeException
- if the tree contains fewer than p+1 elements.
void traverse(TraversalOrder order, TraverseFunctor& tfunc);
tfunc
for each element.
The traversal ends when tfunc
returns false
or after traversing the entire tree.
order
- the order of the traversal.tfunc
- the traverse functor.data
- can be used to pass client data to proc.
Example Code |
Copyright © 2003 Xavax Inc. -- All Rights Reserved