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. |
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 |
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. |
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 | Allocation only when the vector grows. | Expands as needed by adding space for many entries at once. Shrinks only via resize() |
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. For RWSortedVector, use RWOrderedIterator to iterate over the collection. 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() |
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. |
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 |
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 |
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. |
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 |
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. |