Rogue Wave banner
Previous fileTop of DocumentContentsIndex pageNext file
Essential Tools Module User's Guide

A.3 Time and Space Considerations

This section presents a very approximate analysis and comparison of the time and space requirements for a variety of common operations on different specific collections and collection families. We've presented the information as a set of tables that lists the operation, the time cost and the space cost. Any applicable comments appear at the bottom of the table. A key to the abbreviations used in the tables appears at the bottom of each page.

As you read these analyses, keep in mind that various processors, operating systems, compilation optimizations, and many other factors will affect the exact values. The point of these tables is to provide you with some idea of how the behaviors of the various collections will compare, all other things being equal. For more details on algorithm complexity, refer to Knuth, Sedgewick, or any number of other books.

Because many of the Essential Tools Module collections have essentially similar interfaces, it is easy to experiment and discover what effect a different choice of collection will have on your program.

For each of the following tables:

Whenever an allocation is mentioned, you should be aware that memory allocation policies differ radically among various implementations. However, it is generally true that a heap allocation (or deallocation) that translates to a system call is more expensive than most of the other constant costs. "Amortized" cost is averaged over the life of the collection. Any individual action may have a higher or lower cost than the amortized value.

A.3.1 RWGVector, RWGBitVec, RWTBitVec<Size>, RWTPtrVector, and RWTValVector<T>

Table 23: Time and space requirements for RWGVector, RWGBitVec, RWTBitVec<Size>, RWTPtrVector, and RWTValVector 

operation time cost space cost

Find (average item)

N/2

0

Change/replace item

C

0

Container overhead

 

(Mt+2i) + 0

Comments

Simple wrapper around an array of T (except bitvec: array of byte)

Resize only if told to.

A.3.2 Singly Linked Lists

Table 24: Time and space requirements for singly linked lists 

operation

time cost

space cost

Insert at either end

C

t + p

Insert in middle

C (assumes that you have an iterator in position)

t + p

Find (average item)

N/2

0

Change/replace item

C

0

Remove first

C

t + p (recovered)

Remove last

C

t + p (recovered)

Remove in middle

C (assumes that you have an iterator in position)

t + p (recovered)

Container overhead

 

(2p+i) + N(t+p)

Comments

Allocation with each insert

Iterators go forward only

Grows or shrinks with each item.

Smaller than doubly-linked list

A.3.3 Doubly Linked Lists

Table 25: Time and space requirements for doubly linked lists 

operation

time cost

space cost

Insert at either end

C

t + 2p

Insert in middle

C (assumes that you have an iterator in position)

t + 2p

Find (average item)

N/2

0

Change/replace item

C

0

Remove first

C

t + 2p (recovered)

Remove last

C

t + 2p (recovered)

Remove in middle

C (assumes that you have an iterator in position)

t + 2p (recovered)

Container overhead

 

(2p+i) + N(t+2p)

Comments

Allocation with each insert

Iterate in either direction

Grows or shrinks with each item

Larger than Slist

A.3.4 Ordered Vectors

Table 26: Time and space requirements for ordered vectors 

operation

time cost

space cost

Insert at the end

C (amortized)

t (amortized)

Insert in middle

N/2

t (amortized)

Find (average item)

N/2

0

Change/replace item

C

0

Remove first

N

0

Remove last

C

0

Remove in middle

N/2

0

Container overhead

 

(Mt+ p + 2i) + 0

Comments

No iterators (use size_t index)

Allocation only when the vector grows.

Expands as needed by adding space for many entries at once. Shrinks only via resize()

A.3.5 Sorted Vectors

Table 27: Time and space requirements for sorted vectors 

operation

time cost

space cost

Insert

logN + N/2 (average)

t (amortized)

Find (average item)

logN

0

Change/replace item

N

0

Remove first

N

0

Remove last

C

0

Remove in middle

N/2

0

Container overhead

 

(Mt + p + 2i) + 0

Comments

Insertion happens based on sort order.

No iterators (use size_t index)

replace requires remove/add sequence to maintain sorting

Allocation only when the vector grows.

Expands as needed by adding space for many entries at once. Shrinks only via resize()

A.3.6 Stacks and Queues

Table 28: Time and space requirements for stacks and queues 

operation

time cost

space cost

Insert at end

C

t + p

Remove (pop)

C

t + p (recovered)

Container overhead

 

(2p+i) + N(t+p)

Comments

Implemented as singly-linked list.

Templatized version allows choice of container: time and space costs will reflect that choice.

 

A.3.7 Deques

Table 29: Time and space requirements for deques 

operation

time cost

space cost

Insert at end

C

t (amortized)

Find (average item)

N/2

0

Change/replace item

C

0

Remove first

C

t (amortized, recovered)

Remove last

C

t (amortized, recovered)

Remove in middle

N/2

t (amortized, recovered)

Container overhead

 

(Mt + p + i) + 0

Comments

Implemented as circular queue in an array.

Allocation only when collection grows

Expands and shrinks as needed, caching extra expansion room with each increase in size

A.3.8 Binary Tree

Table 30: Time and space requirements for binary tree 

operation

time cost;

space cost

Insert

logN+C

2p+t

Find (average item)

logN

0

Change/replace item

2(logN + C)

0

Remove first

logN + C

2p+t (recovered)

Remove last

logN + C

2p+t (recovered)

Remove in middle

logN + C

2p+t (recovered)

Container overhead

 

(p+i) + N(2p+t)

Comments

Insertion happens based on sort order.

Allocation with each insert

Replace requires remove/add sequence to maintain order

Does not automatically remain balanced. Numbers above assume a balanced tree.

Costs same as doubly linked list per item

A.3.9 (multi)map and (multi)set family

Table 31: Time and space requirements for (multi)map and (multi)set family 

operation

time cost

space cost

Insert

logN+C

2p+t

Find (average item)

logN

0

Change/replace item

2(logN+C) or C

0

Remove first

logN (worst case)

2p+t (recovered)

Remove last

logN (worst case)

2p+t (recovered)

Remove in middle

logN (worst case)

2p+t (recovered)

Container overhead

re-balance may occur at each insert or remove

(3p+i) + N(2p+t)

Comments

Insertion happens based on sort order.

Allocation with each insert

Replace for sets requires remove/insert. For maps the value is copied in place.

implemented as balanced (red-black) binary tree.

 

A.3.10 RWBTree, RWBTreeDictionary

RWBTreeOnDisk has complexity similar to RWBTreeDictionary, but the time overhead is much greater since "following linked nodes" becomes "disk seek;" and the size overhead has a much greater impact on disk storage than on core memory.

Table 32: Time and space requirements for RWBTree and RWBTreeDictionary 

operation

time cost

space cost

Insert

logN+C

2p + t + small (fully amortized)

Find (average item)

logN

0

Change/replace item

2logN+2 or C

0

Remove first

2logN(log2(ORDER))+C (worst case)

2p+t (recovered)

Remove last

2logN(log2(ORDER))+C (worst case)

2p+t (recovered)

Remove in middle

2logN(log2(ORDER))+C (worst case)

2p+t (recovered)

Container overhead

Re-balance may occur at each insert or remove. However it will happen less often than for a balanced binary tree.

This depends on how fully the nodes are packed. Each node costs ORDER(2p+t+1)+i and there will be no more than 2N/ORDER, and no fewer than min(N/ORDER,1) nodes. Inserting presorted items will tend to maximize the size.

Sedgewick says the size is close to 1.44 N/ORDER for random data

Comments

Insertion based on sort order.

The logarithm is approximately base ORDER which is the splay of the b-tree. (In fact the base is between ORDER and 2ORDER depending on the actual loading of the b-tree)

Replace for b-tree requires remove then insert. For btreedictionary the value is copied in place

 

A.3.11 Hash-based Collections

RWSet and RWIdentitySet as well as collections with "Hash" in their names.

Table 33: Time and space requirements for hashed-based collections 

operation

time cost

space cost

Insert

C

p+t

Find (average item)

C

0

Change/replace item

2C

0

Remove

C

p+t (recovered)

Container overhead

 

((M+2)p+i) + N(p+t) (1) (Mp+(2p+i)b_used) + N(p+t) (2)

1: standard compliant version

2: b_used is "number of used slots" for the "V6.1" hashed collections

Comments

Insertion happens based on the hashing function.

Constant time costs assume that the items are well scattered in the hash slots. Worst case is linear in the number of items per slot.

Replace for dictionary or map: The new value is copied in place. Otherwise, requires remove then insert.

Does not automatically resize.

We recommend that the number of items be between one half and double the number of slots for most uses.



Previous fileTop of DocumentContentsIndex pageNext file

©2004 Copyright Quovadx, Inc. All Rights Reserved.
Rogue Wave and SourcePro are registered trademarks of Quovadx, Inc. in the United States and other countries. All other trademarks are the property of their respective owners.
Contact Rogue Wave about documentation or support issues.