C++ Iterators & Algorithms Cheat Sheet

Iterators

Category	Tag	Valid operations	Notes
Input Iterator	`input_iterator_tag`	`I i(j); i=j; i==j; j; j->m; ++j; j++; j++;`	`i==j` does not imply `++i==++j;` single pass only
Output Iterator	`output_iterator_tag`	`I i(j); i=j; ++j; j++; j=t; j++=t;`	`t=*j;` is not valid single pass only
Forward Iterator	`forward_iterator_tag`	`I i; I i(j); i=j; i==j; j; j->m; ++j; j++; j++; j=t; j++=t;`
Bidirectional Iterator	`bidirectional_iterator_tag`	In addition to those for Forward Iterator `--j; j--; *j--;`
Random Access Iterator	`random_access_iterator_tag`	In addition to those for Bidirectional Iterator `j+=n; j+n; n+j; n=i-j; j[n]; i<j; i>j; i>=j; i<=j;`

Useful Iterator Templates

template <class Category, class Tp, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&> struct iterator { typedef Category iterator_category; typedef T value_type; typedef Distance difference_type; typedef Pointer pointer; typedef Reference reference; }

template <class I> struct iterator_traits { typedef typename I::iterator_category iterator_category; typedef typename I::value_type value_type; typedef typename I::difference_type difference_type; typedef typename T::pointer pointer; typedef typename I::reference reference; }; template <class T> struct iterator_traits<T*>; template <class T> struct iterator_traits<const T*>;

Iterator Adaptors

Adaptor Description

template <class Iter> class reverse_iterator Iterates in the reverse direction to the iterator it adapts

reverse_iterator(Iter I) Constructor

template <class Seq> class back_insert_iterator Does a.push_back(t) into the sequence with every assignment

front_insert_iterator<Seq> back_inserter(Seq& x) Helper creation function

template <class Seq> class front_insert_iterator Does a.push_front(t) into the sequence with every assignment

front_insert_iterator<Seq> front_inserter(Seq& x) Helper creation function

insert_iterator <class Container, class I> class insert_iterator Does a.insert(i, t) into the sequence with every assignment

inserter<Container> inserter<Container& x, I i) Helper creation function

template <class T, class Ch=char, class Traits=char_traits<Ch>, class Dist=ptrdiff_t> class istream_iterator; Each reference reads T objects from an input stream

istream_iterator(basic_istream<Ch, Traits>& s); Constructor

template <class T, class Ch=char, class Traits=char_traits<Ch> > class ostream_iterator Each assignment writes to an output stream

ostream_iterator(basic_istream<Ch, Traits>& s, const Ch* delim) Constructor

template<class CharT, class Traits> class istreambuf_iterator Each reference reads from an input stream

template<class CharT, class Traits> class ostreambuf_iterator Each reference writes to an input stream

template <class ForwardIter, class T> class raw_storage_iterator Raw memory iterator

Adaptor	Description
`template <class Iter> class reverse_iterator`	Iterates in the reverse direction to the iterator it adapts
`reverse_iterator(Iter I)`	Constructor
`template <class Seq> class back_insert_iterator`	Does a.push_back(t) into the sequence with every assignment
`front_insert_iterator<Seq> back_inserter(Seq& x)`	Helper creation function
`template <class Seq> class front_insert_iterator`	Does a.push_front(t) into the sequence with every assignment
`front_insert_iterator<Seq> front_inserter(Seq& x)`	Helper creation function
`insert_iterator <class Container, class I> class insert_iterator`	Does a.insert(i, t) into the sequence with every assignment
`inserter<Container> inserter<Container& x, I i)`	Helper creation function
`template <class T, class Ch=char, class Traits=char_traits<Ch>, class Dist=ptrdiff_t> class istream_iterator;`	Each reference reads T objects from an input stream
`istream_iterator(basic_istream<Ch, Traits>& s);`	Constructor
`template <class T, class Ch=char, class Traits=char_traits<Ch> > class ostream_iterator`	Each assignment writes to an output stream
`ostream_iterator(basic_istream<Ch, Traits>& s, const Ch* delim)`	Constructor
`template<class CharT, class Traits> class istreambuf_iterator`	Each reference reads from an input stream
`template<class CharT, class Traits> class ostreambuf_iterator`	Each reference writes to an input stream
`template <class ForwardIter, class T> class raw_storage_iterator`	Raw memory iterator

Functors

Useful Functor Templates


template <class Arg, class Result>

struct unary_function

{

   typedef Arg    
argument_type;

   typedef Result  result_type;

};

template <class Arg1, class Arg2, class Result> struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; };

Functors

Arithmetic operations

plus minus multiplies divides modulus negate

Comparisons

equal_to not_equal_to less greater less_equal greater_equal

Logical operations

logical_and logical_or logical_not

Hash function

hash

Negators

not1(const Pred& pred);
not2(const BinPred& bin_pred);

Binders

bind1st(const Op& op, const T& bound_value);
bind2nd(const Op& op, const T& bound_value);

Adaptors

ptr_fun(FunctionPtr f);

Converts a function pointer to a functor.
Unary function if f takes one argument, binary function if f takes two.

mem_fun(PtrToMember mf);

Converts a pointer to member to a functor whose first arg is a pointer to the object.
Unary function if mf takes no arguments, binary function if mf takes an argument.

mem_fun_ref(PtrToMember mf);

Converts a pointer to member to a functor whose first arg is a reference to the object.
Unary function if mf takes no arguments, binary function if mf takes one argument.

Algorithms


distance_type n = distance(first, last);

advance(i, n);

Function result = for_each(first, last, func);

InputIter loc = find(first, last, target);

InputIter loc = find_if(first, last, pred);

ForwardIter loc = adjacent_find(first, last[, bin_pred]);

ForwardIter loc = find_first_of(first, last, targets_first,
targets_last[, bin_pred]);

ForwardIter loc = search(first, last, subseq_first, subseq_last[,
bin_pred]);

ForwardIter loc = search_n(first, last, count, target[, bin_pred]);

ForwardIter loc = find_end(first, last, subseq_first, subseq_last[,
bin_pred]);

difference_type n = count(first, last, value);

difference_type n = count_if(first, last, value, pred);

pair<InputIter1, InputIter2> differ = mismatch(first1, last1,
first2[, bin_pred]);

bool is_equal = equal(first1, last1, first2[, bin_pred]);

OutputIter result_end = copy(first, last, result);

BidirectionalIter result_begin = copy_backward(first, last,
result_end);

swap(a, b); 

ForwardIter2 new_last2 = swap_ranges(first1, last1, first2);

OutputIter result_end = transform(first, last, result, op);

OutputIter result_end = transform(first1, last2, first2, result,
bin_op);

replace (first, last, old_value, new_value);

replace_if(first, last, pred, new_value);

OutputIter result_end = replace_copy(first, last, result, old_value,
new_value);

OutputIter result_end = replace_copy_if(first, last, result, pred,
new_value);

fill(first, last, value);

fill_n(first, count, value);

generate(first, last, generator);

generate_n(first, count, generator);

ForwardIter new_last remove(first, last, value);

ForwardIter new_last remove_if(first, last, pred);

OutputIter result_end remove_copy(first, last, result, value);

OutputIter result_end remove_copy_if(first, last, result, pred);

ForwardIter new_last = unique(first, last[, bin_pred]);

ForwardIter result_end = unique_copy(first, last[, bin_pred]);

reverse(first, last);

OutputIter result_end = reverse_copy(first, last, result);

rotate(first, middle, last);

OutputIter result_end = rotate_copy(first, middle, last, result);

random_shuffle(first, last[, rand]);

BidirectionalIter middle = partition(first, last, pred);

BidirectionalIter middle = stable_partition(first, last, pred);

sort(first, last[, comp]);

stable_sort(first, last[, comp]);

partial_sort(first, middle, last[, comp]);

RandomAccessIter result_end = partial_sort_copy(first, middle, last,
result_first, result_last[, comp]);

nth_element(first, nth, last[, comp]);

ForwardIter loc = lower_bound(first, last, value[, comp]);

ForwardIter loc = upper_bound(first, last, value[, comp]);

pair<ForwardIter, ForwardIter> loc_range =
equal_range(first, last, value[, comp]);

bool is_present = binary_search(first, last, value[, comp]);

OutputIter result_end = merge(first1, last1, first2, last2, result[,
comp]);

inplace_merge(first, middle, last[, comp]);

bool is_included = includes(first, last, subseq_first, subseq_last[,
comp]);

OutputIter result_end = set_union(first1, last1, first2, last2, result[,
comp]);

OutputIter result_end = set_intersection(first1, last1, first2, last2,
result[, comp]);

OutputIter result_end = set_difference(first1, last1, first2, last2,
result[, comp]);

OutputIter result_end = set_symetric_difference(first1, last1, first2,
last2, result[, comp]);

minimum = min(a, b); 

maximum = max(a, b);

ForwardIter loc = min_element(first, last[, bin_pred]);

ForwardIter loc = max_element(first, last[, bin_pred]);

bool is_less = lexicographical_compare(first1, last1, first2, last2[,
bin_pred]);

bool next_permutation(first, last[, comp]);

bool prev_permutation(first, last[, comp]);

T total = accumulate(first, last, init_total[, bin_op]);

T prod = inner_product(first1, last1, first2, init[, bin_op1,
bin_op2]);

OutputIter result_end = partial_sum(first, last, result[, bin_op]);

OutputIter result_end = adjacent_difference(first, last, result[,
bin_op]);

RandomAccessIter result_end = random_sample(first, last, out_first,
out_last[, rand])

RandomAccessIter result_end = random_sample_n(first, last, out_first,
count[, rand])

bool is_inorder = is_sorted(first, last[, comp]);