Click here to Skip to main content
11,926,380 members (62,313 online)
Click here to Skip to main content
Add your own
alternative version


38 bookmarked

STL containers map, set, and list with fast array access

, 5 Aug 2002 CPOL
Rate this:
Please Sign up or sign in to vote.
Source code for STL compliant container classes that add fast indexing capability to existing container types
<!-- Link to source file download --> <!-- Add the rest of your HTML here -->


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


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


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.


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:

arraylistsetindex_set/map etc.
Indexed access 1 (N) (N+) lgN
Insert/delete N 1 1+ 1+
Search lgNN lgN lgN



21 July 2002 - updated downloads

6 Aug 2002 - updated downloads


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Ray Virzi
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

GeneralI'm stumped Pin
Jörgen Sigvardsson8-Nov-04 13:57
memberJörgen Sigvardsson8-Nov-04 13:57 
GeneralRe: I'm stumped Pin
Ray Virzi8-Nov-04 17:01
memberRay Virzi8-Nov-04 17:01 
GeneralRe: I'm stumped Pin
Jörgen Sigvardsson9-Nov-04 10:19
memberJörgen Sigvardsson9-Nov-04 10:19 
GeneralRe: I'm stumped Pin
lathot25-May-05 10:02
memberlathot25-May-05 10:02 
QuestionHow about Judy Arrays? Pin
Anonymous8-Sep-03 5:53
sussAnonymous8-Sep-03 5:53 
AnswerRe: How about Judy Arrays? Pin
Ray Virzi8-Sep-03 7:02
memberRay Virzi8-Sep-03 7:02 
QuestionDoesn't compile in Visual Studio .NET 2003? Pin
Chris Coble9-Jun-03 10:41
memberChris Coble9-Jun-03 10:41 
AnswerRe: Doesn't compile in Visual Studio .NET 2003? Pin
Ray Virzi11-Jun-03 21:35
memberRay Virzi11-Jun-03 21:35 
GeneralRe: Doesn't compile in Visual Studio .NET 2003? [modified] Pin
Stefan Gebauer19-Aug-07 0:10
memberStefan Gebauer19-Aug-07 0:10 
Questionwhere is the source code ? Pin
mwdev4-Apr-03 19:55
membermwdev4-Apr-03 19:55 
AnswerRe: where is the source code ? Pin
Ray Virzi4-Apr-03 21:59
memberRay Virzi4-Apr-03 21:59 
Generalsome small extensions Pin
George Anescu4-Oct-02 4:51
memberGeorge Anescu4-Oct-02 4:51 
GeneralRe: some small extensions Pin
Ray Virzi4-Oct-02 21:06
memberRay Virzi4-Oct-02 21:06 
Interesting extensions to the standard library. I must point out that the GetIndex() function does not work for the _endnode marker, so you must check for that condition. What is 'index' set to when the item is not found or cannot be inserted? Perhaps -1?

I think the conventional way to get the index is to take the iterator returned by both find() and insert() and subtract it from the beginning of the container, like so:

index_set<T> myset;
index_set<T>::iterator at;
unsigned index;

at = myset.insert(T()).first;   (or at = myset.find(T());)
index = myset.begin() - at;

This should give you the 0-based index. If the function fails, at is set to myset.end() and index will be the total size of the container, so this condition must still be checked for.

But I have also noticed a bug in my code as well. The insert function won't work this way for set and map if the item cannot be inserted. This is because the end maker must point to _endnode. My last line of the insert function should read:

return std::make_pair(AVLTree_Iterator(*this, (pos ? pos : _endnode)), found);

I will upload a corrected version of the code when I get a chance.

GeneralRe: some small extensions Pin
George Anescu7-Oct-02 6:55
memberGeorge Anescu7-Oct-02 6:55 
GeneralRe: some small extensions Pin
Ray Virzi7-Oct-02 17:35
memberRay Virzi7-Oct-02 17:35 
Generalperformance issues Pin
m.6-Aug-02 2:25
sussm.6-Aug-02 2:25 
GeneralRe: performance issues Pin
Maxim Locktyukhin6-Aug-02 6:20
sussMaxim Locktyukhin6-Aug-02 6:20 
GeneralRe: performance issues Pin
Ray Virzi7-Aug-02 16:11
memberRay Virzi7-Aug-02 16:11 
GeneralRe: performance issues Pin
Maxim Locktyukhin8-Aug-02 7:43
sussMaxim Locktyukhin8-Aug-02 7:43 
GeneralRe: performance issues Pin
Jörgen Sigvardsson8-Nov-04 13:29
memberJörgen Sigvardsson8-Nov-04 13:29 
GeneralRe: performance issues Pin
Ray Virzi7-Aug-02 16:23
memberRay Virzi7-Aug-02 16:23 
Generalindex_multimap->count() function return invalid result Pin
Longbird4-Aug-02 16:04
sussLongbird4-Aug-02 16:04 
GeneralAn example would be helpful Pin
Matt Philmon2-May-02 6:43
memberMatt Philmon2-May-02 6:43 
GeneralRe: An example would be helpful Pin
Ray Virzi2-May-02 22:10
memberRay Virzi2-May-02 22:10 
GeneralRe: An example would be helpful Pin
Carl Berg6-Aug-02 3:55
memberCarl Berg6-Aug-02 3:55 
QuestionUpdates? Pin
Ernesto Perales Soto3-Dec-01 11:52
memberErnesto Perales Soto3-Dec-01 11:52 
AnswerRe: Updates? Pin
Ray Virzi27-Feb-02 16:50
memberRay Virzi27-Feb-02 16:50 Pin
James Curran3-Dec-01 9:33
memberJames Curran3-Dec-01 9:33 
AnswerRe: Pin
Ray Virzi27-Feb-02 16:52
memberRay Virzi27-Feb-02 16:52 
GeneralMissing map operator = Pin
Ernesto Perales Soto8-Mar-01 12:47
memberErnesto Perales Soto8-Mar-01 12:47 
GeneralRe: Missing map operator = Pin
Ray Virzi8-Mar-01 17:44
memberRay Virzi8-Mar-01 17:44 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.151126.1 | Last Updated 6 Aug 2002
Article Copyright 2001 by Ray Virzi
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid