Time and Space Considerations

Click on the banner to return to the user guide home page.

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 Tools.h++ 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:

N is the number of items in the collection;
M is the current size of the collection;
t is the size of the item being stored (possibly a pointer);
i is the size of an integer;
p is the size of a pointer
C is a "constant value".
Time costs for each pointer dereference, copy, destroy, allocate, or comparison are considered equal.
Container overhead is as space cost that consists of two terms. The left term is the size of an empty container, while the right term shows the added cost for N items.
Space cost is indicated both for insertions and deletions. Space cost that is marked "(recovered)" indicates that the space has been handed back to the heap allocator.

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.

Key to the comparison tables

`N`	`M`	`t`	`i`	`p`	`C`
count of items	count of space for items	`sizeof` (`item`)	`sizeof` (`int`)	`sizeof` (`void*`)	a constant

RWGVector, RWGBitVec, RWBitVec<size>, RWTPtrVector, and RWTValVector

operation	time cost	space cost
Insert at an end	`C`	`0`
Insert in middle	`C`	`0`
Find (average item)	`N/2`	`0`
Change/replace item	`C`	`0`
Remove first	`C`	`0`
Remove last	`C`	`0`
Remove in middle	`C`	`0`
Container overhead		`Mt + 0`
Comments	Simple wrapper around an array of T (except `bitvec: array` of byte)	Resize only if told to.

Singly Linked Lists

operation	time cost;	space cost
Insert at an 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

Doubly Linked Lists

operation	time cost;	space cost
Insert at an 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`

Ordered Vectors

operation	time cost;	space cost
Insert at 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()`

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()`

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.

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

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

(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.

RWBTree, RWBTreeDictionary [32]

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 2`ORDER` 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

Hash-based Collections [33]

operation	time cost;	space cost
Insert	`C`	`p+t`
Find (average item)	`C`	`0`
Change/replace item	`C` or `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.