|
|
AVL ArrayFrequently Asked Questions (FAQs) |
Download |
avl_array a substitute for
list, vector and
deque? avl_array
everywhere instead of spending my time deciding between
list, vector and
deque? avl_array like a
map with an integer key? avl_array: with [] with
++, or with +=? [] or +=? stable_sort()? stable_sort() when they are not
wanted? std::reverse_iterator template? avl_array class? avl_array inherit from
avl_array_node_tree_fields instead of having
a member of that class, or a simple pointer? avl_array a substitute for
list, vector and deque?Not at all.
avl_array everywhere
instead of spending my time deciding between list,
vector and deque?No! Please, go on reading.
First, follow the wise, wide spread, official recommendations.
Choose list when you are planning to insert/erase everywhere
in the sequence and you don't need random access.
Choose vector when you are planning to use random access
and you only need fast insert/erase at the end of the sequence.
Choose deque when you are planning to use random access
and you need fast insert/erase at both ends of the sequence
(but not in the middle).
When none of these fits, that is, when you
are planning to use intensely both random access and insert/erase
everywhere in the sequence (not only in the ends), then choose
avl_array.
Because avl_array has logarithmic time complexity (O(log N))
at both random access and insert/erase.
See Big O notation in the Wikipedia or the introduction to this documentation.
avl_array like a
map with an integer key?
Not at all. Unlike map, avl_array is a sequence
container. In a map, insert/erase of one element doesn't
affect the keys of the other elements. In avl_array,
insert/erase of one element alters the indexes (call them keys if
you prefer, but they are not ;) of all following elements in the
sequence.
avl_array:
with [] with ++,
or with +=?It's faster with ++. Do it like this:
for (it=container.begin(); it!=container.end(); it++) // BTW, use !=, not <
{ /* do something with *it */ }
for (i=0; i<container.size(); i++)
{ /* do something with container[i] */ }
== or != is
also faster than with <, >,
<= or >=.
[]
or +=?
No. While every iterator++ only needs a single step,
the number of steps needed for iterator+=n or
iterator[n] is at least 2*log2(|n|)
(larger on average, and up to 2*log2(size) in the worst
case). For container[n], the average number of steps is
about log2(size). Make your numbers.
NPSV stands for "Non-Proportional Sequence View". It is a mechanism that
provides one or more additional random access indices. These indices
are affected by insert/erase operations in the same way as the ordinary
random access index (numbers from 0 to size-1). The difference is that
they are not necessarily integers and they don't necessarily grow on a
constant basis (by one in the ordinary random access index). See
avl_array.hpp
and the NPSV-related examples for more information.
For storing the data of text editors, text processors or internet browsers. You are using one right now (or you used it for printing what you have in your hands). In fact, this idea is already in use in GTK:
struct _GtkTextBTreeNode {
//...
int num_lines; /* Total number of lines (leaves) in
* the subtree rooted here. */
int num_chars; /* Number of chars below here */
//...
};
stable_sort()?
Stable sort requires one extra unsigned integer per element, so it
is disabled by default. Just specify std::size_t in the
fourth parameter of the avl_array template instantiation.
You will need to fill the previous parameters too (allocator and NPSV
width type). Use the default values if you don't need them. For
example:
avl_array<employee, // Your class
std::allocator<employee>, // Default allocator for your class
mkr::detail::empty_number, // No NPSV
std::size_t> // Enable stable sort
staff;
stable_sort() when they are not wanted?None. All compilers should optimize them away when the corresponding template parameters are set to their default values. See rationale.
std::reverse_iterator template?
Because it would spoil, for reverse iterators, a valuable property:
they remain valid, referring the same element until it is erased (or
the iterator modified, of course).
The std::reverse_iterator template is based on embedding
a normal iterator referring the next element, thus making the validity
of the reverse iterator dependent on what happens to that next
element.
See rationale.
It has an obvious memory cost, but it slightly simplifies the maintenance of the tree balance, and more important: it lows down the average and worst case time complexity of many operations, like iterators ++ and --, or massive insert/erase/move operations. See rationale.
Because they provide random access, but not with constant time
complexity (O(1)). The specializations of generic algorithms for
random access assume O(1) random access. This assumption (wrong
in the case of avl_array) would make far slower than
their bidirectional counterparts. Not only proportionally slower,
but of a higher complexity order. A perfect example of this are the
implementations of reverse() shown in the
SGI STL iterator tags
overview.
See rationale.
avl_array class?
As those in list (see
splice,
unique, reverse, merge and
sort in the SGI STL implementation),
they support operations otherwise prohibitive or even impossible.
They work in-place, without moving or copying the contained objects,
and they benefit from the internal structure of the implementation
to achieve a better performance (not only proportionally, but with
a lower complexity order).
See rationale.
There are two ways for multiple insert/erase/move operations: 1) repeating single insert/erase/move operations, maintaining the tree(s) integrity and restoring balance every time; and 2) ignoring the tree structure, working with the list, and rebuilding the tree(s) only in the end.
The first way has a cost of O(n log N), where n is the number of elements to insert/erase/move, and N is the total number of elements in the container. The second way has a cost of O(N). A fast estimation is made to decide which way is better in each case. See rationale.
It has no loops and it uses integer arithmetic only. Therefore, the cost is almost null compared with both the total time consumed by the operation and the gain achieved in extreme cases. The estimation will be possibly wrong in a small interval near the critical point (where both ways take the same time), but it will work well with the big numbers, thus saving a lot of execution time. See rationale.
Because they don't need to. Maintaining it would be a waste of space and time (in the case of tree nodes), or it would spoil valuable properties (in the case of iterators). See rationale.
avl_array inherit from
avl_array_node_tree_fields instead of having
a member of that class, or a simple pointer?Because that way the container object can be reached from the tree nodes by following the parent pointers until a NULL pointer is found. See rationale.
Just because. Well, I find them easier to understand (and implement, and maintain...) than Red-Black trees, which have more corner cases. AVL trees have better lookup time, because they guarantee better balance. On the other hand, for the same reason, one can expect Red-Black trees to make fewer rotations. This should be considered as a matter of implementation. It affects neither the interface nor the algorithmic complexity of any operation.
Revised 22 November, 2006
Copyright © Universidad de Alcalá 2006. See accompanying license.