Introduction to the Standard Template Library (STL)

The C++ standard committee added the Standard Template Library (STL) to the C++ Standard Library due to the importance of the software reuse benefits. The STL defines powerful, template-based, reusable components that implement many common data structures and algorithms used to process those data structures. The STL offers proof of concept for generic programming with templates. It is very important to keep in mind that in industry, the features presented are often referred to as the Standard Template Library or STL. However, these terms are not used in the C++ standard document, because these features are simply considered to be part of the C++ Standard Library.

The STL was developed by Alexander Stepanov and Meng Lee at Hewlett-Packard (hp) and is based on their research in the field of generic programming, with significant contributions from David Musser. The STL was conceived and designed for performance and flexibility. In this article, the main three components of STL (containers, iterators and algorithms) will be discussed. STL containers, iterators and algorithms are shown in the tables given below.

Standard Library Containers

Standard Library Container Class	Description
Sequence containers
vector	Rapid insertions and deletions at back. Direct access to any element.
deque	Rapid insertions and deletions at front or back. Direct access to any element.
list	Doubly linked list, rapid insertion and deletion anywhere.
Associative containers
set	Rapid lookup, no duplicates allowed.
multiset	Rapid lookup, duplicates allowed.
map	One-to-one mapping, no duplicates allowed, rapid key-based lookup.
multimap	One-to-one mapping, duplicates allowed, rapid key-based lookup.
Container adapters
stack	Last-in, first-out (LIFO).
queue	First-in, first-out (FIFO).
priority_queue	Highest-priority element is always the first element out.

Standard Library Common Member Functions

Member Function	Description
default constructor	A constructor to create an empty container. Normally, each container has several constructors that provide different initialization methods for the container.
copy constructor	A constructor that initializes the container to be a copy of an existing container of the same type.
destructor	Destructor function for cleanup after a container is no longer needed.
empty	Returns true if there are no elements in the container, otherwise, returns false.
insert	Inserts an item in the container.
size	Returns the number of elements currently in the container.
operator=	Assigns one container to another.
operator<	Returns true if the first container is less than the second one, otherwise, returns false.
operator<=	Returns true if the first container is less than or equal to the second one, otherwise, returns false.
operator>	Returns true if the first container is greater than the second one, otherwise, returns false.
operator>=	Returns true if the first container is greater than or equal to the second one, otherwise, returns false.
operator==	Returns true if the first container is equal to the second one, otherwise, returns false.
operator!=	Returns true if the first container is not equal to the second one, otherwise, returns false.
swap	Swap the elements of the two containers.
max_size	Returns the maximum number of elements for a container.
begin	The two versions of this function return either an iterator or a const_iterator that refers to the first element of the container.
end	The two versions of this function return either an iterator or a const_iterator that refers to the next position after the end of the container.
rbegin	The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the last element of the container.
rend	The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the next position after the last element of the reversed container.
erase	Erases one or more elements from the container.
clear	Erases all the elements from the container.

Standard Library Container Header Files

Header File	Description
	Contains both queue and priority_queue.
	Contains both map and multimap.
	Contains both set and multiset.

typedefs Found in First-Class Containers

typedef	Description
allocator_type	The type of the object used to allocate the container’s memory.
value_type	The type of the element stored in the container.
reference	A reference to the type of element stored in the container.
const_reference	A constant reference to the type of element stored in the container. Such a reference can be used only for reading elements in the container and for performing const operations.
pointer	A pointer to the type of element stored in the container.
const_pointer	A pointer to a constant of the container’s element type.
iterator	An iterator that points to an element of the container’s element type.
const_iterator	A constant iterator that points to the type of element stored in the container and can be used only to read elements.
reverse_iterator	A reverse iterator that points to the type of element stored in the container. This type of iterator is for iterating through a container in reverse.
const_reverse_iterator	A constant reverse iterator that points to the type of element stored in the container and can be used only to read elements. This type of iterator is for iterating through a container in reverse.
difference_type	The type of the result of subtracting two iterators that refer to the same container (operator - is not defined for iterators of lists and associative containers).
size_type	The type used to count items in a container and index through a sequence container (cannot index through a list).

STL Iterator Categories

Iterator Category	Description
input	Used to read an element from a container. An input iterator can move only in the forward direction (i.e., from the beginning of the container to the end) one element at a time. Input iterators support only one-pass algorithms - the same input iterator cannot be used to pass through a sequence twice.
output	Used to write an element to a container. An output iterator can move only in the forward direction one element at a time. Output iterators support only one-pass algorithms - the same output iterator cannot be used to pass through a sequence twice.
forward	Combines the capabilities of input and output iterators and retains their position in the container (as state information).
bidirectional	Combines the capabilities of a forward iterator with the ability to move in the backward direction (i.e., from the end of the container towards the beginning). Bidirectional iterators support multipass algorithms.
random access	Combines the capabilities of a bidirectional iterator with the ability to directly access any element of the container (i.e., to jump forward or backward by an arbitrary number of elements).

Iterator Category Hierarchy

Iterator Type Supported by each Container

Container	Type of Iterator Supported
Sequence containers (first class)
vector	random access
deque	random access
list	bidirectional
Associative containers (first class)
set	bidirectional
multiset	bidirectional
map	bidirectional
multimap	bidirectional
Container adapters
stack	no iterators supported
queue	no iterators supported
priority_queue	no iterators supported

Iterator typedefs

Predefined typedefs for iterator types	Direction of ++	Capability
iterator	forward	read / write
const_iterator	forward	read
reverse_iterator	backward	read / write
const_reverse_iterator	backward	read

Iterator Operation for each Type of Iterator

Iterator Operation	Description
All iterators
++p	Pre-increment an iterator.
p++	Post-increment an iterator.
Input iterators
*p	Dereference an iterator.
p = p1	Assign one iterator to another.
p == p1	Compare iterators for equality.
p != p1	Compare iterators for inequality.
Output iterators
*p	Dereference an iterator.
p = p1	Assign one iterator to another.
Forward iterators	Forward iterators provide all the functionality of both input iterators and output iterators.
Bidirectional iterators
--p	Pre-decrement an iterator.
p--	Post-decrement an iterator.
Random access iterators
p += i	Increment the iterator p by i positions.
p -= i	Decrement the iterator p by i positions.
p + i or i + p	Expression value is an iterator positioned at p incremented by i positions.
p - i	Expression value is an iterator positioned at p decremented by i positions.
p - p1	Expression value is an integer representing the distance between two elements in the same container.
p[ i ]	Return a reference to the element offset from p by i positions.
p < p1	Return true if iterator p is less than iterator p1 (i.e., iterator p is after iterator p1 in the container); otherwise, return false.
p <= p1	Return true if iterator p is less than or equal to iterator p1 (i.e., iterator p is before iterator p1 or at the same location as iterator p1 in the container); otherwise, return false.
p > p1	Return true if iterator p is greater than iterator p1 (i.e., iterator p is after iterator p1 in the container); otherwise, return false.
p >= p1	Return true if iterator p is greater than or equal to iterator p1 (i.e., iterator p is after iterator p1 or at the same location as iterator p1 in the container); otherwise, return false.

Mutating-Sequence Algorithms

copy	partition	replace_copy	stable_partition
copy_backward	random_shuffle	replace_copy_if	swap
fill	remove	replace_if	swap_ranges
fill_n	remove_copy	reverse	transform
generate	remove_copy_if	reverse_copy	unique
generate_n	remove_if	rotate	unique_copy
iter_swap	replace	rotate_copy

Non-Modifying Sequence Algorithms

adjacent_find	equal	find_end	mismatch
count	find	find_first_of	search
count_if	find_each	find_if	search_n

Numerical Algorithms from Header File

accumulate	partial_sum
inner_product	adjacent_difference

Some STL Exception Types

STL Exception Types	Description
out_of_range	Indicates when subscript is out of range - e.g., when an invalid subscript is specified to vector member function at.
invalid_argument	Indicates an invalid argument was passed to a function.
length_error	Indicates an attempt to create too long a container, string, etc..
bad_alloc	Indicates that an attempt to allocate memory with new (or with an allocator) failed because not enough memory was available.

Other Standard Template Library Algorithms

Algorithm	Description
inner_product	Calculate the sum of the products of two sequences by taking corresponding elements in each sequence, multiplying those elements and adding the result to a total.
adjacent_difference	Beginning with the second element in a sequence, calculate the difference (using operator -) between the current and previous elements and store the result. The first two input iterators arguments indicate the range of elements in the container  and the third indicates where the results should be stored. A second version of this algorithm takes as a fourth argument a binary function to perform a calculation between the current element and the previous element.
partial_sum	Calculate a running total (using operator -) of the values in a sequence. The first two input iterators arguments indicate the range of elements in the container and the third indicates where the results should be stored. A second version of this algorithm takes as a fourth argument a binary function that performs a calculation between the current value in the sequence and the running total.
nth_element	Use three random-access iterators to partition a range of elements. The first and last arguments represent the range of elements. The second argument is the partitioning element’s location. After this algorithm executes, all elements before the partitioning element are less than that element and all elements after the partitioning element are greater than or equal to that element. A second version of this algorithm takes as a fourth argument a binary comparison function.
partition	This algorithm is similar to nth_element, but requires less powerful bidirectional iterators, making it more flexible. It requires two bidirectional iterators indicating the range of elements to partition. The third argument is a unary predicate function that helps partition the elements so that all elements for which the predicate is true are to the left (toward the beginning of the sequence) of those for which the predicate is false. A bidirectional iterator is returned indicating the first element in the sequence for which the predicate returns false.
stable_partition	Similar to partition except that this algorithm guarantees that equivalent elements will be maintained in their original order.
next_permutation	Next lexicographical permutation of a sequence.
prev_permutation	Previous lexicographical permutation of a sequence.
rotate	Use three forward iterator arguments to rotate the sequence indicated by the first and last argument by the number of positions indicated by subtracting the first argument from the second argument. e.g., the sequence 1,2,3,4,5 rotated by two positions would be 4,5,1,2,3.
rotate_copy	This algorithm is identical to rotate except that the results are stored in a separate sequence indicated by the fourth argument - an output iterator. The two sequences must have the same number of elements.
adjacent_find	This algorithm returns an input iterator indicating the first of two identical adjacent elements in a sequence. If there are no identical adjacent elements, the iterator is positioned at the end of the sequence.
search	This algorithm searches for a subsequence of elements within a sequence of elements and, if such a subsequence is found, returns a forward iterator that indicates the first element of that subsequence. If there are no matches, the iterator is positioned at the end of the sequence to be searched.
search_n	This algorithm searches a sequence of elements looking for a subsequence in which the values of a specified number of elements have a particular value and, if such a subsequence is found, returns a forward iterator that indicates the first element of that subsequence. If there are no matches, the iterator is positioned at the end of the sequence to be searched.
partial_sort	Use three random-access iterators to sort part of a sequence. The first and last arguments indicate the sequence of elements. The second argument indicates the ending location for the sorted part of the sequence. By default, elements are ordered using operator < (a binary predicate function can also be supplied). The elements from the second argument iterator to the end of the sequence are in an undefined order.
partial_sort_copy	Use two input iterators and two random-access iterators to sort part of a sequence indicated by the two input iterator arguments. The results are stored in the sequence indicated by the two random-access iterator arguments. By default, elements are ordered using operator < (a binary predicate function can also be supplied). The number of elements sorted is the smallest of the number of elements in the result and the number of elements in the original sequence.
stable_sort	The algorithm is similar to sort except that all equivalent elements are maintained in their original order. This sort is O(n log n) if enough memory is available; otherwise, it’s O(n(log n)2).

Function Objects in Standard Library

STL Function Objects	Type	STL Function Objects	Type
divides< T >	arithmetic	logical_or< T >	logical
equal_to< T >	relational	minus< T >	arithmetic
greater< T >	relational	modulus< T >	arithmetic
greater_equal< T >	relational	negate< T >	arithmetic
less< T >	relational	not_equal_to< T >	relational
less_equal< T >	relational	plus< T >	arithmetic
logical_and< T >	logical	multiplies< T >	arithmetic
logical_not< T >	logical