STL in Brief

by iDog

Header files

• algorighm: defines algorithms
• deque
• functional
• iterator: includes xutility, containing all iterators.
• list
• map
• memory: contains memory management related stuffs, like allocators and auto_ptr, etc.
• numeric: some math related operations that are not put in <algorithm>. Of course, we can also make them to do something else, like to make accumulate() concatenate strings.
• queue
• set
• stack
• utility: contains pair and related functions.
• vector

Iterator

Iterator is the glue in STL to connect different parts together (algorithms and containers). It's a generized pointer.

Output Iterator:

An output iterator is used to write data, for example, to write data to a container, or to a file. It should have things below:

• copy constructor
• destructor
• assignment operator
• increment operators (pre/post)
• dereference operator (for write)

Usage:

for(; <not_done>; ++outIt)
    *outIt = <value>;

// or traditional C style
while(<not_done>)
    *outIt++ = <value>;

Input Iterator:

An input iterator is used to generate a new sequence. If it's done by accessing existing data, we can read from a container or a file. It should have following things:

• copy constructor
• destructor
• assignment operator
• increment operators (pre/post)
• dereference operator (for read)
• ==, !=
• -> (when the T has members, we use this: inIt->member1)

Note that the == and != comparison only makes sense if at least one of the two operands is end-of-sequence.

Usage:

// both 'first' and 'last' are of type InIt
for(InIt inIt = first; inIt != last; ++inIt)
    my_function(*inIt);  // *inIt returns a value of type 'T'

// or traditional C style
while(first != last)
    my_function(*first++);

Forward Iterator:

A forward iterator is similar to a pointer to a linked list. It's used to iterate through a sequence to access all elements from head to tail. We can also make bookmarks in the middle. It should have following things:

• default constructor
• copy constructor
• destructor
• assignment operator
• increment operators (pre/post)
• dereference operator (for read & write)
• ==, !=
• -> (when the T has members, we use this: inIt->member1)

Here the == and != can have any operands (including the case of neither of them is end-of-sequence).

Bidirectional Iterator:

A bidirectional iterator is similar to a pointer to a double linked list. It supports following operations besides all of those in a forward iterator:

• decrement operators (pre/post)

Random Access Iterator:

A random access iterator also supports comparison, addition and subtraction, in order to access elements at any given position. So it supports all operations of a bidirectional iterator, as well as follows:

• <, >, <=, >=
• +=, -= (operand is a number)
• + (raIt + n, n + raIt)
• - (raIt - n, raIt1 - raIt2)
• [] (raIt[i] returns a value of type T)

Notes:

• Output Iterator: used to write data. After writing the data, we have to increment it.
• Input Iterator: used to read data. We need to increment it in order to read the next data. After the increment, the copy of the previous value of the input iterator becomes invalid.
• Forward Iterator: a forward iterator can be used as an input iterator, or an output iterator (if the value it points to is writable). We can have many copies of the forward iterator, any of them can increment and accessing data in their own pace.
• Bidirectional Iterator: It can be used as a forward iterator. It can also move to the opposite direction.
• Random Access Iterator: It can be used as a bidirectional iterator. It also supports integer calculations (like a pointer). A pointer can be used as a random access iterator.

<utility>

This header file defines template class pair, as well as operations related to pair.

Pair is used to combine two objects into one. This helps to return two values from a function, or storing two values as a pair in a container.

Usage:

typedef pair<int, string> my_pair;
pair<int, string> d1;  // 0, ""
my_pair d2(0, "string 0");
my_pair d3 = make_pair((my_pair::first_type)1, (my_pair::second_type)"string 1");
int n = d3.first;
assert(d2 < d3);
assert(d1 != d2);
assert(d3 >= d2);

<Algorithm>

Work on two elements

max

get the bigger one in two.

min

get the smaller one in two.

swap

swap two values.

iter_swap

swap two values pointed by two iterators.

Scan sequences

max_element

get the max one in a sequence.

min_element

...

equal

check if two sequences are equal.

lexicographical_compare

check if one sequence is ahead of the other.

mismatch

get the first different place in two sequences.

find

find the first element in a sequence that equals to a given value.

find_if

use a functon to evaluate if two elements are equal.

adjacent_find

find the first adjacent elements that are equal.

count

get number of elements in a sequence.

count_if

...

search

find the first occurrence of a sequence in another sequence.

search_n

find the first place where an element equal to a given value occurs continuously for n times.

find_end

find the last place where a sequence occurs in another sequence.

find_first_of

find the first place where any element of a sequence occurs in another sequence.

Operate on each of elements

for_each

call op(x) for any element x in a sequence.

generate

assign func() to all elements in a sequence.

generate_n

only assign to first n elements.

transform

for each of element x in a sequence, calc op(x) and assign the result to another sequence; or, for each pair of elements (x, y) in two sequences, call op(x, y) and assign the result to another sequence.

Assign one sequence to another

copy

copy one sequence to another

copy_backward

copy from tail to head.

fill

assign a value to all elements in a sequence.

fill_n

only fill first n elements.

swap_ranges

swap values in two sequences.

Replace

replace

replace all elements that equals to a given value to another value.

replace_if

use a function to evaluate if two values equal.

replace_copy

copy a sequence, and replace all values equal to a given value to another value.

replace_copy_if

...

Remove elements

remove

remove all elements that equal to a given value

remove_if

...

remove_copy

copy a sequence and remove all elements that equal to a given value.

remvoe_copy_if

...

unique

remove all duplicated elements in a sequence.

unique_copy

copy only unique elements in a sequence.

reverse

reverse a sequence.

reverse_copy

copy the sequence and reverse it.

rotate

rotate a sequence at a given place.

rotate_copy

...

random_shuffle

...

Sort

partition

put all element x in a sequence that makes pr(x) return true to the beginning.

stable_partition

sort

sort elements in a sequence in ascending order.

stable_sort

'stable' means that if two elements are equal, after the sorting, their relationship won't change.

partial_sort

only sort middle-first elements that are less than any of the other elements.

partial_sort_copy

the minimum k=min{last1-first1, last2-first2} elements in first sequence get sorted and copied to second sequence.

nth_element

re-arrange the sequence, to make all elements ahead of the n-th element not greater than it, while all elements behind it not less than it.

Merge

merge

merge two sequences into a new one.

inplace_merge

...

Scan ascending sequence

lower_bound

find the first place where the element is not less than a given value.

upper_bound

find the last place where the element is not less than a given value.

equal_range

get the first & last place where elements are not less than a given value

binary_search

check if there is an element that has equivalent ordering with the given value.

Take two ascending sequences as input

includes

check if one sequence contains another.

set_union

merge two sequences into one, having the duplicated (equivalent ordering) elements in the second sequence excluded.

set_intersection

get the intersection of the two sequences and make it a new sequence.

set_difference

produce a new sequence with only elements in the first one but not in the second one.

set_symmetric_difference

produce a new sequence with elements only in one of the two sequences.

Processing heap

make_heap

re-arrange a sequence to make it a heap

push_heap

add a new element in a heap

pop_heap

remove the greatest element from heap.

sort_heap

sort a heap to produce an ascending sequence.

Sort (again)

next_permutation

sort the sequence to make its elements in ascending order. Return true only when it modified the sequence.

prev_permutation

(descending).

<numeric>

accumulate

use operator+ to accumulate all elements.

inner_product

multiply respective elements in two sequences then sum them up.

partial_sum

produce a new sequence, where any element is the respective element in another sequence adding the accumulated number.

adjacent_difference

produce a new sequence storing the differences of elements in two sequences.

<functional>

Here functional objects are defined.

// unary
negate<T>, logical_not<T>

// binary
plus<T>, minus<T>, multiplies<T>, divides<T>, modulus<T>

equal_to<T>, not_equals_to<T>, greater<T>, less<T>, greater_equal<T>, less_equal<T>

logical_and<T>, logical_or<T>

// compound

...

// pointer

...

Containers

.	vector	deque	list	set/map
insert/remove	N	N	const	log N
insert from front	N (1)	const	const	log N (1)
find(value)	N (1)	N (1)	N (1)	log N
X(N)	const	const	N (1)	N (1)
pointer(s) (2)	0	1	2	3

(1) means that the operation is not supported by member functions.

(2) pointer(s) means number of pointers needed for a new element.

Container adaptors

• stack
• queue
• priority_queue: the element with the highest priority will be delivered first.

Common functions

• begin(): return the 'first' iterator
• end(): return the 'last' iterator
• rbegin(): reversed iterator
• rend()
• erase(): delete one or more element(s) with a iterator or a range.
• clear(): clear all elements in a container.
• empty: check if it's empty
• max_size(): max size of the container.
• get_allocator: rarely used...
• swap():