<< Cheat-Sheets

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

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]);