The C++ Standad Template Library (STL) Containers

Containers implement Abstract Data Types such as arrays, queues, linked lists, and so on. They are classified into:

Sequence containers, such as vector's (1-dimensional arrays), deque's (double ended queues), list's (doubly linked lists), and so on. They provide access to sequences of elements.
Associative containers: std::set, std::multisetstd::map and std::multimap. std::map and std::multimap provide lookup based on a key.

Each container has its own advantages and disadvantages. Some aspects are:

ease of insertion and deletion not at the back: lists perform best, whereas std::vector's perform worst
access by index: only array-like containers (std::vector, std::deque, std::array) support it

Not-Quite Containers

In addition, the standard library provides types of objects that hold elements while not offering all of the facilities of sequence containers or associative containers:

Container adaptors provide specialized access to underlying containers. They are

stack
queue
prority queue

bitmaps
valarrays

The (Mostly) Common Containers Interface

Each container class makes some type definitions of integer types (size and index types etc), and pointer, iterator and reference types. Some common ones are:

size_type: Some integral type roughly equivalent to size_t.
difference_type: Can represent the difference between two addresses.
value_type: The same type as the type of the values stored in a container object (i.e., the same as T for sequential containers and container adaptors, but pair<const KType, VType> for stl::map and stl::multimap.
reference (const_reference): A (constant) reference to an element.
pointer (const_pointer): A (constant) pointer to a component of a (first-class) container object (i.e., same as T*, where T is the component type of the container object).
iterator: An iterator.
const_iterator: A const iterator.
reverse_iterator: A reverse iterator.
const_reverse_iterator: A const reverse iterator.
allocator_type: The type of the allocator used for the container class (Allocators are the most infrequently used feature of the STL by the average C++ programmer. It is almost always OK to go with the default allocator for whatever container you are using.)

Additionally, container adaptors stack, queue, and priority_queue define container_type. The associative containers (set, multiset, map, and multimap) define key_type and key_compare. Only map and multimap define mapped_type, whereas set and multiset define value_compare.

Elements held in containers are meant to be accessed sequentally through iterators, which are generalizations of pointers and support as much iterator arithmetic as makes sense. Each container defines functions producing an iterators pointing to the first element and to the element past the last one:

begin() and rbegin() produce an iterator to the first element and a reverse iterator to the last element, and
end() and rend() produce an iterator to a would-be element past the last one or a reverse iterator to another before the first one. They are meant to be used like this in for loops and such:
```
for(iterator it = begin(); it != end(); ++it) {
  // body of the for-loop
}
```

Other members commonly found in STL containers are:

default, copy and range constructors (container(iterator beg, iterator past_end));
void clear() and bool empty() for making a container empty or finding if it is empty;
insert(...) and erase(...) member functions for inserting an element given an element or range of elements and an iterator to its destination, or a destination iterator and a reference. These are some common prototypes:
```
iterator insert(iterator i, const T &val = T( ));
void insert(iterator i, size_type num, const T & val);
template <class InIter> void insert(iterator i, InIter start, InIter end);
```
Warning: Random-access insertions and deletions are slow in containers based on C arrays, such as std::vector and std::deque.
size() and max_size() return the current number of elements and the maximum number of elements that can be held;
std::vector and std::string provide a capacity() member function that returns how many elements the container can hold before resizing and thereby invalidating references to its members or underlying C-array, which we are not advised to take anyway; we can anticipate this by calling reserve(size_type n=0), though;
swap(const container_type&) exchanges the container's elements and those of its parameter, a facility that is used by some algorithms.

The Iterator Interface

STL containers are meant to be handled through iterators. For a new, alternative way, see Ranges (C++20).

Several typedef's are provided: iterator, const_iterator, reverse_iterator, const_reverse_iterator and difference_type

Functions returning iterators are provided, too: begin() and end(), their reverse versions rbegin() and rend(), and the constant versions of all preceding four: cbegin(), cend(), crbegin() and crend()

Global `std::begin(CONT)` and `std::end(CONT)`

Globals functions std::begin(CONT) and std::end(CONT) return the begin and end interator of their container parameter.

They are also (partially-)specialized for C-style arrays.

Requirement `Compare`

Compare is a set of requirements expected by some of the standard library facilities from the user-provided function object types.

The return value of the function call operation applied to an object of a type satisfying Compare, when contextually converted to bool, yields true if the first argument of the call appears before the second in the strict weak ordering relation induced by this type, and false otherwise.

As with any BinaryPredicate, evaluation of that expression is not allowed to call non-const functions through the dereferenced iterators.

The associative containers std::set, std::map, std::multiset, and std::multimap as well as std::priority_queue expect a Compare type.

The following standard library functions or algorithms expect a Compare type, too:

sort: sorts a range into ascending order (function template)
sort: sorts the elements (public member function of std::forward_list<T,Allocator>)
sort: sorts the elements (public member function of std::list<T,Allocator>)
stable_sort: sorts a range of elements while preserving order between equal elements (function template)
partial_sort: sorts the first N elements of a range (function template)
partial_sort_copy: copies and partially sorts a range of elements (function template)
is_sorted (C++11): checks whether a range is sorted into ascending order (function template)
is_sorted_until (C++11): finds the largest sorted subrange (function template)
nth_element: partially sorts the given range making sure that it is partitioned by the given element (function template)
lower_bound: returns an iterator to the first element not less than the given value (function template)
upper_bound: returns an iterator to the first element greater than a certain value (function template)
binary_search: determines if an element exists in a certain range (function template)
equal_range: returns range of elements matching a specific key (function template)
merge: merges two sorted ranges (function template)
merge: merges two sorted lists (public member function of std::forward_list<T,Allocator>)
merge: merges two sorted lists (public member function of std::list<T,Allocator>)
inplace_merge: merges two ordered ranges in-place (function template)
includes: returns true if one set is a subset of another (function template)
set_difference: computes the difference between two sets (function template)
set_intersection: computes the intersection of two sets (function template)
set_symmetric_difference: computes the symmetric difference between two sets (function template)
set_union: computes the union of two sets (function template)
push_heap: adds an element to a max heap (function template)
pop_heap: removes the largest element from a max heap (function template)
make_heap: creates a max heap out of a range of elements (function template)
sort_heap: turns a max heap into a range of elements sorted in ascending order (function template)
is_heap (C++11): checks if the given range is a max heap (function template)
is_heap_until (C++11): finds the largest subrange that is a max heap (function template)
max: returns the greater of the given values (function template)
max_element: returns the largest element in a range (function template)
min: returns the smaller of the given values (function template)
min_element: returns the smallest element in a range (function template)
minmax (C++11): returns the smaller and larger of two elements (function template)
minmax_element (C++11): returns the smallest and the largest elements in a range (function template)
lexicographical_compare: returns true if one range is lexicographically less than another (function template)
next_permutation: generates the next greater lexicographic permutation of a range of elements (function template)
prev_permutation: generates the next smaller lexicographic permutation of a range of elements (function template)

Container Adaptors

These are based on another, full container and reduce or adapt their capabilities to suite an interface.

Stack

A stack implements a stack or FILO (First In Last Out) queue and is based on a deque by default, although it might use a vector just as well.

Queue

A queue implements a (First In Last Out) queue and is based on a deque by default, although it might use a vector just as well.

Prority Queue

A prority_queue keeps its elements sorted and produces the smallest element according to some comparison function object. It is otherwise called a heap and is based on a vector by default because it requires random access and swapping elements.

You can write a customized priority queue by availing yourself of the following STL algorithms, which rely on random-access iterators, as found in vector and queue:

template <class RandIter>
void make_heap(RandIter start, RandIter end);
template <class RandIter, class Comp>
void make_heap(RandIter start, RandIter end, Comp cmpfn);
//
template <class RandIter>
void push_heap(RandIter start, RandIter end);
template <class RandIter, class Comp>
void push_heap(RandIter start, RandIter end, Comp cmpfn);
//
template <class RandIter>
void pop_heap(RandIter start, RandIter end);
template <class RandIter, class Comp>
void pop_heap(RandIter start, RandIter end, Comp cmpfn);

Or you can turn a sequence into a heap all at once by calling:

template <class RandIter>
void sort_heap(RandIter start, RandIter end);
template <class RandIter, class Comp>
void sort_heap(RandIter start, RandIter end, Comp cmpfn);

Sequence Containers

Lists with `std::list` and `std::forward_list`

A list is a sequence optimized for insertion and deletion of elements. When you insert into a list or delete an element from a list , the locations of other elements of the list are not affected. In particular, iterators referring to other elements are not affected.

The STL provides two linked-list types:

list: a doubly-linked list, and
forward_list: a singly-linked list introduced in recent revisions (C++11)

These are implemented in container std::list<>.

With the exception of subscripting, capacity management, and size() for forward_list, the STL lists provide the member types and operations offered by vector<>. In addition, list<> and forward_list<> provide specific list member functions:

Doubly-Linked Lists with `std::list`

st.push_front(x)	Add x to lst (using copy or move) before the first element
`lst`.pop_front()	Remove the first element from lst
`lst`.emplace_front(args)	Add T{args} to lst before the first element
`lst`.remove(v)	Remove all elements of lst with value v
`lst`.remove_if(f)	Remove all elements of lst for which f(x)==true
`lst`.unique()	Remove adjacent duplicate elements of lst
`lst`.unique(f)	Remove adjacent duplicate elements of lst using f for equality
`lst`.merge(lst2)	Merge the ordered lists lst and lst2 using < as the order; lst2 is merged into lst and emptied in the process
`lst`.merge(lst2,f)	Merge the ordered lists lst and lst2 using f as the order; lst2 is merged into lst and emptied in the process
`lst`.sort()	Sort lst using < as the order
`lst`.sort(f)	Sort lst using f as the order
`lst`.reverse()	Reverse the order of the elements of lst ; noexcept

Singly-Linked Lists with `std::forward_list`*

Vectors

std::vectors are automatic arrays which keep track of their size, that is how many places have been occupied (pressumably in an integer variable), as well as their capacity, which is the total number of objects of the given type that they can accomodate. Further, when they have filled up, they reallocate their sequence of objects in a larger chunk of memory, the start of this run of memory is updated (in a pointer variable), and the new, larger capacity is updated, too. This means that indeces into the array-like structure remain valid, but pointers are invalidated, so they must never be taken in the first place.

Unlike with linked lists, insertions (or deletions) are either meaningless or demand that all objects after the one inserted be shifted one place, which is done in linear time, whereas lists perform insertions and deletions in constant time. Furthermore, insertions and deletions would invalidate all subsequent indeces...

Deques

A deque (pronounced "deck") is very similar to a vector. It manages its elements with a dynamic array, provides random access, and has almost the same interface as a vector. The difference is that with a deque the dynamic array is open at both ends. Thus, a deque is fast for insertions and deletions at both the end and the beginning.

Deques have the following differences compared with the abilities of vectors:

Inserting and removing elements is fast both at the beginning and at the end (for vectors it is only fast at the end). These operations are done in amortized constant time.
The internal structure has one more indirection to access the elements, so element access and iterator movement of deque's are usually a bit slower.
Iterators must be smart pointers of a special type rather than ordinary pointers because they must jump between different blocks.
In systems that have size limitations for blocks of memory (for example, some PC systems), a deque might contain more elements because it uses more than one block of memory. Thus, max_size() might be larger for deque's.
Deques provide no support to control the capacity and the moment of reallocation. In particular, any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque.
However, reallocation may perform better than for vectors, because according to their typical internal structure, deque's don't have to copy all elements on reallocation.
Blocks of memory might get freed when they are no longer used, so the memory size of a deque might shrink (however, whether and how this happens is implementation specific).

Bitmap's*

Random Access Returning Reference

Sequence containers based on an array offer access through indeces. They will declare:

reference operator[](size_type idx);
const_reference operator[](size_type idx) const;

These are fast but do not perform bound checking. Trying to access beyond the end of the underlying array may, well, crash the program or yield the wrong result. If unsure, use:

      reference at(size_type idx);
const_reference at(size_type idx) const;

Member function at(size_type idx) returns a reference or const_reference all right, but will throw an out_of_range exception. Use at(size_type idx) inside a try {...} block.

If you write a container in the STL tradition that returns references to elements of an array, write the body of your at(size_type idx) like this:

if(idx >= size())
  throw out_of_range("Container::at() used with idx past the end");
else
  return the_array[idx];

Find and Replace Operations

Functions find(...) returns a size_type variable, actually an integer representing an index to the element found. A string's find() operation may return npos, for no position, which should be defined as -1.

Some Prototypes for Sequence and Associative Containers

This is the prototype of a would-be sequence_container class to derive containers from. There are no private members since this class is used as an interface.

template <class T, class Allocator=allocator<T> >
class sequence_container {
public:
  // some type definitions:
  typedef unsigned int size_type;
  typedef T value_type;
  typedef       T *       iterator;
  typedef const T * const_iterator;
  typedef       T &       reference;
  typedef const T & const_reference;
  // this is the type of function that compares two values:
  typedef bool (*) (const T&, const T&) value_compare;
  // some more obscure type definitions:
  typedef       T *       reverse_iterator;
  typedef const T * const_reverse_iterator;
  typedef Allocator allocator_type;
  // some iterator-related member functions:
  iterator       begin();
  const_iterator begin() const;
  iterator       end();
  const_iterator end()   const;
  reverse_iterator       rbegin();
  const_reverse_iterator rbegin() const;
  reverse_iterator       rend();
  const_reverse_iterator rend()   const;
  // some other member functions:
  size_type size() const;
  reference       front();
  const_reference front() const;
  void pop_back();
  void push_back(const T& val);
  void clear();
  bool empty() const;
  allocator_type get_allocator() const;
  // constructors:
  sequence_container(const Allocator &ca = Allocator()));
  sequence_container(size_type num, const T& val = T(), const Allocator &ca = Allocator()));
  sequence_container(const sequence_container<T,Allocator>& obj);
  template <class InIter>
  sequence_container(InIter start, InIter end, const Allocator& ca = Allocator());
};

Pushing and Emplacing

These are two slightly different ways of adding an element to a container such as a std::vector. Whereas pushing entails copying a value, emplacing causes the value to be constructed in place from some arguments that are passed in.

Pushing (`push_back()`)

Prototype:

void push_back (const value_type& val);
void push_back (value_type&& val);

Emplacing

The emplace() operation inserts a new element, which is constructed in place using args as the arguments for its constructor.

template <class... Args>
void emplace_back (Args&&... args);

template <class... Args>
iterator emplace (const_iterator position, Args&&... args);

Now, the second prototype (iterator emplace (const_iterator position, Args&&... args);) constructs the new element after position.

Emplacing is used when it is either notationally awkward or potentially inefficient to first create an object and then copy (or move) it into a container, as is the case with pushing.