Click here to Skip to main content
Click here to Skip to main content

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

, 5 Aug 2002
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 -->

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:

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

Enjoy!

History

21 July 2002 - updated downloads

6 Aug 2002 - updated downloads

License

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

Share

About the Author

Ray Virzi

United States United States
No Biography provided

Comments and Discussions

 
GeneralMy vote of 5 PinmemberDemonS7728-Oct-10 0:13 
Questionis this still supported Pinmembermaciekboni20-Jun-09 5:37 
AnswerRe: is this still supported PinmemberRay Virzi20-Jun-09 8:18 
GeneralRe: is this still supported Pinmembermaciekboni30-Jun-09 18:54 
GeneralRe: is this still supported PinmemberRay Virzi30-Jun-09 19:45 
GeneralRe: is this still supported Pinmembermaciekboni1-Jul-09 0:31 
GeneralI'm stumped PinmemberJörgen Sigvardsson8-Nov-04 12:57 
GeneralRe: I'm stumped PinmemberRay Virzi8-Nov-04 16:01 
GeneralRe: I'm stumped PinmemberJörgen Sigvardsson9-Nov-04 9:19 
GeneralRe: I'm stumped Pinmemberlathot25-May-05 9:02 
QuestionHow about Judy Arrays? PinsussAnonymous8-Sep-03 4:53 
AnswerRe: How about Judy Arrays? PinmemberRay Virzi8-Sep-03 6:02 
QuestionDoesn't compile in Visual Studio .NET 2003? PinmemberChris Coble9-Jun-03 9:41 
AnswerRe: Doesn't compile in Visual Studio .NET 2003? PinmemberRay Virzi11-Jun-03 20:35 
GeneralRe: Doesn't compile in Visual Studio .NET 2003? [modified] PinmemberStefan Gebauer18-Aug-07 23:10 
Questionwhere is the source code ? Pinmembermwdev4-Apr-03 18:55 
AnswerRe: where is the source code ? PinmemberRay Virzi4-Apr-03 20:59 
Generalsome small extensions PinmemberGeorge Anescu4-Oct-02 3:51 
GeneralRe: some small extensions PinmemberRay Virzi4-Oct-02 20:06 
GeneralRe: some small extensions PinmemberGeorge Anescu7-Oct-02 5:55 
GeneralRe: some small extensions PinmemberRay Virzi7-Oct-02 16:35 
Generalperformance issues Pinsussm.6-Aug-02 1:25 
GeneralRe: performance issues PinsussMaxim Locktyukhin6-Aug-02 5:20 
GeneralRe: performance issues PinmemberRay Virzi7-Aug-02 15:11 
GeneralRe: performance issues PinsussMaxim Locktyukhin8-Aug-02 6:43 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    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 | Mobile
Web03 | 2.8.140902.1 | Last Updated 6 Aug 2002
Article Copyright 2001 by Ray Virzi
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid