<!-- Link to source file download -->

<!-- Add the rest of your HTML here -->

## Introduction

This source code contains five STL compliant container classes with the following names:

index_list<T>
index_set<T,Cmp>
index_multiset<T,Cmp>
index_map<Key,T,Cmp>
index_multimap<Key,T,Cmp>

Each of these implements the same interface as the STL class in the second part of its name. In addition,
each one also implements the STL interface for the `vector<T>`

class, providing fast array access via
`operator[]`

and `at()`

. `T`

is the type of the contained class. `Key`

is the type of the
lookup key for pair-associative containers. Cmp is the comparison predicate and must be a binary predicate
with arguments of type `T`

for `set`

and type `Key`

for `map`

. If you do not provide a comparison
predicate, it will default to `std::less<Arg>`

.

The classes are all derived from an AVL tree that I borrowed form Adreas Jager (copyright included) and modified
to allow for the indexed access. Each tree node contains an extra long integer that holds the number of child nodes
below it. The algorithm to update these counts does not add to the complexity of any of the original tree algorithms.
Since the interfaces are documented in the STL, I will simply provide the complexity analysis below. I believe I
have covered the most-used functions of these containers, but some functions may not be included. Please contact
me if you wish to add another STL function and I will be glad to update the source.

## Complexity Analysis

index_list<T>

An `index_list`

is a sequence which combines the interfaces of `array`

, `deque`

,
and `list`

.

Here are the complexity comparisons with other sequence containers:

| `array` | `deque` | `list` | `index_list` |

Indexed access | 1 | 1 | (N) | lgN |

Insert/delete | N | N | 1 | 1+ |

Front insertion | (N) | 1+ | 1 | 1+ |

Back insertion | 1+ | 1+ | 1 | 1+ |

It tends to work best for large sets (N >> 1).

It also has the extra function `insert(const T&)`

, usually used for sets,
which chooses an insert position that keeps the tree balanced with a
minimal number of rotation operations.

index_set<T,Cmp>
index_multiset<T,Cmp>
index_map<Key,T,Cmp>
index_multmap<Key,T,Cmp>

These classes implement the STL interfaces for `set`

, `multiset`

, `map`

, and `multimap`

respectively, along with the indexed access (`operator[]`

, `at()`

).
Here are the complexity comparisons with other associative containers:

| `array` | `list` | `set` | `index_set` /`map` etc. |

Indexed access | 1 | (N) | (N+) | lgN |

Insert/delete | N | 1 | 1+ | 1+ |

Search | lgN | N | lgN | lgN |

Enjoy!

## History

21 July 2002 - updated downloads

6 Aug 2002 - updated downloads