AVL Array Examples

Download

Simple test

NPSV example

Simple test

The code listed in simpletest.cpp is rough, simple test. It shows that AVL Arrays outperform vector and list under very particular conditions. AVL Arrays are the best choice in cases where both kinds of operations (random access and insert/erase at any point) are performed frequently in highly populated containers.

The test consists in populating a container by inserting random numbers in random positions, and then removing elements from random positions until only one remains. The final element is shown as a proof that all containers execute the same operations. The next table shows some results:

NPSV example

The code listed in npsvexample.cpp is an example of the experimental feature "Non-Proportional Sequence View" (NPSV). This feature exploits, in a more general form, the same principle that AVL Array uses for indexing the sequence with natural numbers.

The difference is that in the normal sequence view every element counts as 1, while in the NPSV each element can count as a 'width' that can be changed. The position of every element is the sum of the widths of the previous elements in the sequence order. Negative widths are forbidden, but zero width is allowed.

When an element has zero width, the next one seems to be in the same position from the NPSV point of view. In these cases the lookup at this shared position always returns the first element of the 'same position' group.

The type of the width is a parameter of the avl_array template, providing a lot of possibilities: unsigned, double, or any class providing some overloaded operators =, +, -, +=, -=, ==, !=, >, <, <=, >= and a conversion from int, which will be used for 0 and 1.

The output of the program is shown in comments along the code.

Revised 22 November, 2006

Copyright © Universidad de Alcalá 2006. See accompanying license.