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