Container Abilities
|
Vector |
Deque |
List |
Set |
Multiset |
Map |
Multimap |
Typical internal data structure |
Dynamic array |
Array of arrays |
Doubly linked list |
Binary tree |
Binary tree |
Binary tree |
Binary tree |
Elements |
Value |
Value |
Value |
Value |
Value |
Key/Value pair |
Key/Value pair |
Duplicates allowed |
Yes |
Yes |
Yes |
No |
Yes |
Not for the key |
Yes |
Random access available |
Yes |
Yes |
No |
No |
No |
With key |
No |
Iterator category |
Random access |
Random access |
Bidirectional |
Bidirectional |
Bidirectional |
Bidirectional |
Bidirectional |
Search/Find elements |
Slow |
Slow |
Very slow |
Fast |
Fast |
Fast for key |
Fast for key |
Inserting/Removing elements is fast |
At the end |
At the beginning and end |
Anywhere |
|
|
|
|
Jose M. Vidal
Last modified: Tue Aug 31 17:11:09 EDT 1999