Professional C++ by Marc Gregoire

Author:Marc Gregoire
Language: eng
Format: epub, pdf
ISBN: 9781118858134
Published: 2014-08-20T00:00:00+00:00

Summary of STL Containers

The following table summarizes the containers provided by the STL. It uses the big-O notation introduced in Chapter 4 to present the performance characteristics on a container of N elements. An N/A entry in the table means that the operation is not part of the container semantics.

CONTAINER CLASS NAME CONTAINER TYPE INSERTION PERFORMANCE DELETION PERFORMANCE LOOKUP PERFORMANCE

vector Sequential Amortized O(1) at end; O(N-p) for an insert at position p O(1) at end; O(N-p) for a delete at position p O(1)

When to Use: Need quick lookup. Don’t mind slower insertion/deletion. Whenever you would use a standard C-style array that should dynamically grow/shrink in size.

list Sequential O(1) once you are at the position where to insert the element O(1) once you are at the position where to delete the element O(N); Statistically O(N/2)

When to Use: Need quick insertion/deletion. Don’t mind slower lookup.

forward_list Sequential O(1) once you are at the position where to insert the element O(1) once you are at the position where to delete the element O(N); Statistically O(N/2)

When to Use: When you need the benefits of a list but require only forward iteration.

deque Sequential Amortized O(1) at beginning or end; O(min(N-p, p)) for an insert at position p O(1) at beginning or end; O(min(N-p, p)) for a delete at position p O(1)

When to Use: Not usually needed; use a vector or list instead.

array Sequential N/A N/A O(1)

When to Use: When you need a fixed-size array to replace a standard C-style array.

queue Container Adapter Depends on the underlying container; O(1) for list, amortized O(1) for deque Depends on the underlying container; O(1) for list and deque N/A

When to Use: When you want a FIFO structure

priority_queue Container Adapter Depends on the underlying container; amortized O(log(N )) for vector and deque Depends on the underlying container; O(log(N)) for vector and deque N/A

When to Use: When you want a queue with priority.

stack Container Adapter Depends on the underlying container; O(1) for list, amortized O(1) for vector and deque Depends on the underlying container; O(1) for list, vector and deque N/A

When to Use: When you want a FILO/LIFO structure.

set

multiset Sorted Associative O(log(N)) O(log(N)) O(log(N))

When to Use: When you want a sorted collection of elements with equal lookup, insertion, and deletion times.

map

multimap Sorted Associative O(log(N)) O(log(N)) O(log(N))

When to Use: When you want a sorted collection to associate keys with values with equal lookup, insertion, and deletion times.

unordered_map

unordered_multimap Unordered associative / hash table Average case O(1); worst case O(N) Average case O(1); worst case O(N) Average case O(1); worst case O(N)

When to Use: When you want to associate keys with values with equal lookup, insertion, and deletion times and don’t require the elements to be sorted. Performance can be better than with a normal map but that depends on the elements.

unordered_set

unordered_multiset Unordered associative / hash table Average case O(1); worst case O(N) Average case O(1); worst case O(N) Average case O(1); worst case O(N)

When to Use: When you want a collection of elements with equal lookup, insertion, and deletion times and don’t require the elements to be sorted.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.