C++ Notes: STL: Containers: Introduction

The STL (Standard Template Library) provides a number of predefined containers (data structures), most of which are generalize as templates to hold any type element. By far the most commonly used are string and vector.

Sequence containers

These containers hold sequences of data elements.

vector provides a dynamic array structure with fast random access to any element. Inserting and deleting elements at the end is fast. Can do subscript bounds checking.
deque also provides a dynamic array structure with random access and adds fast insertion and deletion of elements at front as well as from the back. Very slightly slower than vector because of an extra level of indirection.
list is usually implemented as a doubly linked list. There is no random access to the elements. Insertion and deletion anywhere is fast.

Associative containers

Associative containers contain key/value pairs, providing access to each value using a key. The elements are sorted by the key. Usually implemented as a balanced binary tree.

map provides access to elements using any type of key. This is a generalization of the idea of accessing a vector with an integer subscript.
multimap is the same as map, but allows a key to map into more than one element.

Ordered sets

The set containers keep the elements in them in order, and are usually implemented as balanced binary trees. They do not implement standard set operations (union, intersection, ...) as you might expect from the name.

set orders the elements that are added to it. A set contains only one copy of any value added to it.
multiset is like set but allows more than one entry with the same value.

Container adapters

These are based on other containers, and are used only to enforce access rules. Because there are special access restrictions, they have no iterators.

stack allows only LIFO (Last In, First Out) access.
queue allows only FIFO (First In, First Out) access.
priority_queue always returns the element with the highest priority.

Specialized containers

The following containers are specialized in some ways: specific data type, special utility routines, limited, but fast, implementations.

string holds character strings - similar to vector<char>, but with many useful utility functions.
bitset is a storage-efficient data structure for bits. By defining the bit operations, it effectively implements set operations.
valarray is an especially efficient implementation of arrays, but it doesn't have all the standard container behavior.