accumulate

int main()
{
  int A[] = {1, 2, 3, 4, 5};
  const int N = sizeof(A) / sizeof(int);

  cout << "The sum of all elements in A is " 
       << accumulate(A, A + N, 0)
       << endl;

  cout << "The product of all elements in A is "
       << accumulate(A, A + N, 1, multiplies<int>())
       << endl;
}

adjacent_difference

int main()
{
  int A[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
  const int N = sizeof(A) / sizeof(int);
  int B[N];

  cout << "A[]:         ";
  copy(A, A + N, ostream_iterator<int>(cout, " "));
  cout << endl;
  
  adjacent_difference(A, A + N, B);
  cout << "Differences: ";
  copy(B, B + N, ostream_iterator<int>(cout, " "));
  cout << endl;

  cout << "Reconstruct: ";
  partial_sum(B, B + N, ostream_iterator<int>(cout, " "));
  cout << endl;
}

adjacent_find

int A[] = {1, 2, 3, 4, 6, 5, 7, 8};
const int N = sizeof(A) / sizeof(int);

const int* p = adjacent_find(A, A + N, greater<int>());

cout << "Element " << p - A << " is out of order: "
     << *p << " > " << *(p + 1) << "." << endl;

advance

list<int> L;
L.push_back(0);
L.push_back(1);

list<int>::iterator i = L.begin();
advance(i, 2);
assert(i == L.end());

Allocators

vector<double> V(100, 5.0);     // Uses the default allocator.
vector<double, single_client_alloc> local(V.begin(), V.end());

back_insert_iterator

list<int> L;
L.push_front(3);
back_insert_iterator<list<int> > ii(L);
*ii++ = 0;
*ii++ = 1;
*ii++ = 2;
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 3 0 1 2

basic_string

int main() { 
  string s(10u, ' ');           // Create a string of ten blanks.

  const char* A = "this is a test";
  s += A;
  cout << "s = " << (s + '\n');
  cout << "As a null-terminated sequence: " << s.c_str() << endl;
  cout << "The sixteenth character is " << s[15] << endl;
  
  reverse(s.begin(), s.end());
  s.push_back('\n');
  cout << s;
}

bidirectional_iterator

class my_bidirectional_iterator : public bidirectional_iterator<double> 
{
  ...
};

bidirectional_iterator_tag

binary_compose

list<int> L;
...
list<int>::iterator in_range = 
     find_if(L.begin(), L.end(),
             compose2(logical_and<bool>(),
                      bind2nd(greater_equal<int>(), 1),
                      bind2nd(less_equal<int>(), 10)));
assert(in_range == L.end() || (*in_range >= 1 && *in_range <= 10));

Computes sin(x)/(x + DBL_MIN) for each element of a range.

transform(first, last, first,
          compose2(divides<double>(),
                   ptr_fun(sin),
                   bind2nd(plus<double>(), DBL_MIN)));

binary_function

struct exponentiate : public binary_function<double, double, double> {
    double operator()(double x, double y) { return pow(x, y); }
};

binary_negate

char str[MAXLEN];
...
const char* wptr = find_if(str, str + MAXLEN,
                           compose2(not2(logical_or<bool>()),
                                    bind2nd(equal_to<char>(), ' '),
                                    bind2nd(equal_to<char>(), '\n')));
assert(wptr == str + MAXLEN || !(*wptr == ' ' || *wptr == '\n')); 

binary_search

int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 1; i <= 10; ++i) {
    cout << "Searching for " << i << ": "
         << (binary_search(A, A + N, i) ? "present" : "not present") << endl;
  }
}

Searching for 1: present
Searching for 2: present
Searching for 3: present
Searching for 4: not present
Searching for 5: present
Searching for 6: not present
Searching for 7: not present
Searching for 8: present
Searching for 9: not present
Searching for 10: not present

binder1st

list<int> L;
...
list<int>::iterator first_nonzero = 
       find_if(L.begin(), L.end(), bind1st(not_equal_to<int>(), 0));
assert(first_nonzero == L.end() || *first_nonzero != 0);

binder2nd

list<int> L;
...
list<int>::iterator first_positive = 
       find_if(L.begin(), L.end(), bind2nd(greater<int>(), 0));
assert(first_positive == L.end() || *first_positive > 0);

bitset

int main() {
  const bitset<12> mask(2730ul); 
  cout << "mask =      " << mask << endl;

  bitset<12> x;

  cout << "Enter a 12-bit bitset in binary: " << flush;
  if (cin >> x) {
    cout << "x =        " << x << endl;
    cout << "As ulong:  " << x.to_ulong() << endl;
    cout << "And with mask: " << (x & mask) << endl;
    cout << "Or with mask:  " << (x | mask) << endl;
  }
}

bit_vector

bit_vector V(5);
V[0] = true;
V[1] = false;
V[2] = false;
V[3] = true;
V[4] = false;

for (bit_vector::iterator i = V.begin(); i < V.end(); ++i)
  cout << (*i ? '1' : '0');
cout << endl;

char_traits

construct

double* dp = (double*) malloc(sizeof(double));
construct(dp, 3);
assert(*dp == 3);

copy_backward

vector<int> V(15);
iota(V.begin(), V.end(), 1);
copy_backward(V.begin(), V.begin() + 10, V.begin() + 15);

copy

vector<int> V(5);
iota(V.begin(), V.end(), 1);

list<int> L(V.size());
copy(V.begin(), V.end(), L.begin());
assert(equal(V.begin(), V.end(), L.begin()));

copy_n

vector<int> V(5);
iota(V.begin(), V.end(), 1);

list<int> L(V.size());
copy_n(V.begin(), V.size(), L.begin());
assert(equal(V.begin(), V.end(), L.begin()));

count

int main() {
  int A[] = { 2, 0, 4, 6, 0, 3, 1, -7 };
  const int N = sizeof(A) / sizeof(int);

  cout << "Number of zeros: " 
       << count(A, A + N, 0)
       << endl;
}

count_if

int main() {
  int A[] = { 2, 0, 4, 6, 0, 3, 1, -7 };
  const int N = sizeof(A) / sizeof(int);

  cout << "Number of even elements: " 
       << count_if(A, A + N, 
                   compose1(bind2nd(equal_to<int>(), 0), 
                            bind2nd(modulus<int>(), 2)))
       << endl;
} 

Deque

deque<int> Q;
Q.push_back(3);
Q.push_front(1);
Q.insert(Q.begin() + 1, 2);
Q[2] = 0;
copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 1 2 0

destroy

class Int {
public:
  Int(int x) : val(x) {}
  int get() { return val; }
private:
  int val;
};

int main()
{
  Int A[] = { Int(1), Int(2), Int(3), Int(4) };

  destroy(A, A + 4);
  construct(A,     Int(10));
  construct(A + 1, Int(11));
  construct(A + 2, Int(12));
  construct(A + 3,  Int(13));
}

distance

int main() {
  list<int> L;
  L.push_back(0);
  L.push_back(1);

  assert(distance(L.begin(), L.end()) == L.size());
}

distance_type

template <class RandomAccessIterator, class LessThanComparable, 
          class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,
                                   RandomAccessIterator last, 
                                   const LessThanComparable& value,
                                   Distance*)
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle;

    while (len > 0) {
        half = len / 2;
        middle = first + half;
        if (*middle < value) {
            first = middle + 1;
            len = len - half - 1;
        } else
            len = half;
    }
    return first;
}

template <class RandomAccessIterator, class LessThanComparable>
inline RandomAccessIterator lower_bound(RandomAccessIterator first,
                                        RandomAccessIterator last,
                                        const LessThanComparable& value) {
    return __lower_bound(first, last, value, distance_type(first));
}

divides

const int N = 1000;
vector<double> V1(N);
vector<double> V2(N);
vector<double> V3(N);

iota(V1.begin(), V1.end(), 1);
fill(V2.begin(), V2.end(), 75);

assert(V2.size() >= V1.size() && V3.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),
          divides<double>());

equal

int A1[] = { 3, 1, 4, 1, 5, 9, 3 };
int A2[] = { 3, 1, 4, 2, 8, 5, 7 };
const int N = sizeof(A1) / sizeof(int);

cout << "Result of comparison: " << equal(A1, A1 + N, A2) << endl;

equal_range

int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 2; i <= 4; ++i) {
    pair<int*, int*> result = equal_range(A, A + N, i);

    cout << endl;
    cout << "Searching for " << i << endl;
    cout << "  First position where " << i << " could be inserted: "
         << result.first - A << endl;
    cout << "  Last position where " << i << " could be inserted: "
         << result.second - A << endl;
    if (result.first < A + N)
      cout << "  *result.first = " << *result.first << endl;
    if (result.second < A + N)
      cout << "  *result.second = " << *result.second << endl;
  }
}    

Searching for 2
  First position where 2 could be inserted: 1
  Last position where 2 could be inserted: 2
  *result.first = 2
  *result.second = 3

Searching for 3
  First position where 3 could be inserted: 2
  Last position where 3 could be inserted: 5
  *result.first = 3
  *result.second = 5

Searching for 4
  First position where 4 could be inserted: 5
  Last position where 4 could be inserted: 5
  *result.first = 5
  *result.second = 5

equal_to

vector<int> V;
...
partition(V.begin(), V.end(), bind2nd(equal_to<int>(), 0));

fill

vector<double> V(4);
fill(V.begin(), V.end(), 137);
assert(V[0] == 137 && V[1] == 137 && V[2] == 137 && V[3] == 137);

fill_n

vector<double> V;
fill_n(back_inserter(V), 4, 137);
assert(V.size() == 4 && V[0] == 42 && V[1] == 42 && V[2] == 42 && V[3] == 42);

find_end

int main()
{
  char* s = "executable.exe";
  char* suffix = "exe";

  const int N = strlen(s);
  const int N_suf = strlen(suffix);

  char* location = find_end(s, s + N,
                            suffix, suffix + N_suf);

  if (location != s + N) {
    cout << "Found a match for " << suffix << " within " << s << endl;
    cout << s << endl;

    int i;
    for (i = 0; i < (location - s); ++i)
      cout << ' ';
    for (i = 0; i < N_suf; ++i)
      cout << '^';
    cout << endl;
  }
  else
    cout << "No match for " << suffix << " within " << s << endl;
}

find_first_of

int main()
{
  const char* WS = "\t\n ";
  const int n_WS = strlen(WS);

  char* s1 = "This sentence contains five words.";
  char* s2 = "OneWord";


  char* end1 = find_first_of(s1, s1 + strlen(s1),
                             WS, WS + n_WS); 
  char* end2 = find_first_of(s2, s2 + strlen(s2),
                             WS, WS + n_WS); 

  printf("First word of s1: %.*s\n", end1 - s1, s1); 
  printf("First word of s2: %.*s\n", end2 - s2, s2); 
}

find

list<int> L;
L.push_back(3);
L.push_back(1);
L.push_back(7);

list<int>::iterator result = find(L.begin(), L.end(), 7);
assert(result == L.end() || *result == 7);

find_if

list<int> L;
L.push_back(-3);
L.push_back(0);
L.push_back(3);
L.push_back(-2);

list<int>::iterator result = find_if(L.begin(), L.end(),
                                     bind2nd(greater<int>(), 0));
assert(result == L.end() || *result > 0);

for_each

template<class T> struct print : public unary_function<T, void>
{
  print(ostream& out) : os(out), count(0) {}
  void operator() (T x) { os << x << ' '; ++count; }
  ostream& os;
  int count;
};

int main()
{
  int A[] = {1, 4, 2, 8, 5, 7};
  const int N = sizeof(A) / sizeof(int);

  print<int> P = for_each(A, A + N, print<int>(cout));
  cout << endl << P.count << " objects printed." << endl;
}

forward_iterator

class my_forward_iterator : public forward_iterator<double> 
{
  ...
};

forward_iterator_tag

front_insert_iterator

list<int> L;
L.push_front(3);
front_insert_iterator<list<int> > ii(L);
*ii++ = 0;
*ii++ = 1;
*ii++ = 2;
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 2 1 0 3

functors

    vector<int> V(100);
    generate(V.begin(), V.end(), rand);

Sort a vector of double by magnitude, i.e. ignoring the elements' signs. In this example, the function object is an object of a user-defined class.

    struct less_mag : public binary_function<double, double, bool> {
	bool operator()(double x, double y) { return fabs(x) < fabs(y); }
    };

    vector<double> V;
    ...
    sort(V.begin(), V.end(), less_mag());

Find the sum of elements in a vector. In this example, the function object is of a user-defined class that has local state.

    struct adder : public unary_function<double, void>
    {
      adder() : sum(0) {}
      double sum;
      void operator()(double x) { sum += x; }
    };

    vector<double> V;
    ...
    adder result = for_each(V.begin(), V.end(), adder()); [3]
    cout << "The sum is " << result.sum << endl;

Remove all elements from a list that are greater than 100 and less than 1000.

    list<int> L;
    ...
    list<int>::iterator new_end = 
	 remove_if(L.begin(), L.end(),
		   compose2(logical_and<bool>(),
			    bind2nd(greater<int>(), 100),
			    bind2nd(less<int>(), 1000)));
    L.erase(new_end, L.end());

generate

vector<int> V;
...
generate(V.begin(), V.end(), rand);

generate_n

generate_n(ostream_iterator<int>(cout, "\n"), 100, rand);

get_temporary_buffer

int main()
{
  pair<int*, ptrdiff_t> P = get_temporary_buffer(10000, (int*) 0);
  int* buf = P.first;
  ptrdiff_t N = P.second;
  uninitialized_fill_n(buf, N, 42);
  int* result = find_if(buf, buf + N, bind2nd(not_equal_to<int>(), 42));
  assert(result == buf + N);
  return_temporary_buffer(buf);
}        

greater_equal

list<int> L;
...
list<int>::iterator first_nonnegative = 
    find_if(L.begin(), L.end(), bind2nd(greater_equal<int>(), 0));
assert(first_nonnegative == L.end() || *first_nonnegative >= 0);

greater

vector<int> V;
...
sort(V.begin(), V.end(), greater<int>());

hash

int main()
{
  hash<const char*> H;
  cout << "foo -> " << H("foo") << endl;
  cout << "bar -> " << H("bar") << endl;
}

hash_map

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) == 0;
  }
};

int main()
{
  hash_map<const char*, int, hash<const char*>, eqstr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  
  cout << "september -> " << months["september"] << endl;
  cout << "april     -> " << months["april"] << endl;
  cout << "june      -> " << months["june"] << endl;
  cout << "november  -> " << months["november"] << endl;
}

hash_multimap

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) == 0;
  }
};

typedef hash_multimap<const char*, int, hash<const char*>, eqstr> map_type;

void lookup(const map_type& Map, const char* str)
{
  cout << str << ": ";
  pair<map_type::const_iterator, map_type::const_iterator> p =
    Map.equal_range(str);
  for (map_type::const_iterator i = p.first; i != p.second; ++i)
    cout << (*i).second << " ";
  cout << endl;
}

int main()
{
  map_type M;
  M.insert(map_type::value_type("H", 1));
  M.insert(map_type::value_type("H", 2));
  M.insert(map_type::value_type("C", 12));
  M.insert(map_type::value_type("C", 13));
  M.insert(map_type::value_type("O", 16));
  M.insert(map_type::value_type("O", 17));
  M.insert(map_type::value_type("O", 18));
  M.insert(map_type::value_type("I", 127));

  lookup(M, "I");
  lookup(M, "O");
  lookup(M, "Rn");
}

hash_multiset

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) == 0;
  }
};

void lookup(const hash_multiset<const char*, hash<const char*>, eqstr>& Set,
            const char* word)
{
  int n_found = Set.count(word);
  cout << word << ": "
       << n_found << " "
       << (n_found == 1 ? "instance" : "instances")
       << endl;
}

int main()
{
  hash_multiset<const char*, hash<const char*>, eqstr> Set;
  Set.insert("mango");
  Set.insert("kiwi");
  Set.insert("apple");
  Set.insert("kiwi");
  Set.insert("mango");
  Set.insert("mango");
  Set.insert("apricot");
  Set.insert("banana");
  Set.insert("mango");

  lookup(Set, "mango");
  lookup(Set, "apple");
  lookup(Set, "durian");
}

hash_set

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) == 0;
  }
};

void lookup(const hash_set<const char*, hash<const char*>, eqstr>& Set,
            const char* word)
{
  hash_set<const char*, hash<const char*>, eqstr>::const_iterator it
    = Set.find(word);
  cout << word << ": "
       << (it != Set.end() ? "present" : "not present")
       << endl;
}

int main()
{
  hash_set<const char*, hash<const char*>, eqstr> Set;
  Set.insert("kiwi");
  Set.insert("plum");
  Set.insert("apple");
  Set.insert("mango");
  Set.insert("apricot");
  Set.insert("banana");

  lookup(Set, "mango");
  lookup(Set, "apple");
  lookup(Set, "durian");
}

identity

int main()
{
  int x = 137;
  identity<int> id;
  assert(x == id(x));   
}           

includes

int A1[] = { 1, 2, 3, 4, 5, 6, 7 };
int A2[] = { 1, 4, 7 };
int A3[] = { 2, 7, 9 };
int A4[] = { 1, 1, 2, 3, 5, 8, 13, 21 };
int A5[] = { 1, 2, 13, 13 };
int A6[] = { 1, 1, 3, 21 };

const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3) / sizeof(int);
const int N4 = sizeof(A4) / sizeof(int);
const int N5 = sizeof(A5) / sizeof(int);
const int N6 = sizeof(A6) / sizeof(int);

cout << "A2 contained in A1: " 
     << (includes(A1, A1 + N1, A2, A2 + N2) ? "true" : "false") << endl;
cout << "A3 contained in A1: " 
     << (includes(A1, A1 + N2, A3, A3 + N3) ? "true" : "false") << endl;
cout << "A5 contained in A4: " 
     << (includes(A4, A4 + N4, A5, A5 + N5) ? "true" : "false") << endl;
cout << "A6 contained in A4: " 
     << (includes(A4, A4 + N4, A6, A6 + N6) ? "true" : "false") << endl;

A2 contained in A1: true
A3 contained in A1: false
A5 contained in A4: false
A6 contained in A4: true

inner_product

int main()
{
  int A1[] = {1, 2, 3};
  int A2[] = {4, 1, -2};
  const int N1 = sizeof(A1) / sizeof(int);

  cout << "The inner product of A1 and A2 is " 
       << inner_product(A1, A1 + N1, A2, 0)
       << endl;
}

inplace_merge

int main()
{
  int A[] = { 1, 3, 5, 7, 2, 4, 6, 8 };

  inplace_merge(A, A + 4, A + 8);
  copy(A, A + 8, ostream_iterator<int>(cout, " "));  
  // The output is "1 2 3 4 5 6 7 8".
}

input_iterator

class my_input_iterator : public input_iterator<double> 
{
  ...
};

input_iterator_tag

insert_iterator

list<int> L;
L.push_front(3);
insert_iterator<list<int> > ii(L, L.begin());
*ii++ = 0;
*ii++ = 1;
*ii++ = 2;
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 0 1 2 3.

int main() 
{
  const int N = 6;

  int A1[N] = {1, 3, 5, 7, 9, 11};
  int A2[N] = {1, 2, 3, 4, 5, 6};
  set<int> result;

  merge(A1, A1 + N, A2, A2 + N, 
        inserter(result, result.begin()));
 
  copy(result.begin(), result.end(), ostream_iterator<int>(cout, " "));
  cout << endl;

  // The output is "1 2 3 4 5 6 7 9 11".
}

iota

int main()
{
  vector<int> V(10);

  iota(V.begin(), V.end(), 7);
  copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
  cout << endl; 
}

is_heap

int A[] = {1, 2, 3, 4, 5, 6, 7};
const int N = sizeof(A) / sizeof(int);

assert(!is_heap(A, A+N));
make_heap(A, A+N);
assert(is_heap(A, A+N));

is_sorted

int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);

assert(!is_sorted(A, A + N));
sort(A, A + N);
assert(is_sorted(A, A + N));

istream_iterator

vector<int> V;
copy(istream_iterator<int>(cin), istream_iterator<int>(),
     back_inserter(V));   

iterator_category

template <class BidirectionalIterator>
void __reverse(BidirectionalIterator first, BidirectionalIterator last, 
               bidirectional_iterator_tag) {
    while (true)
        if (first == last || first == --last)
            return;
        else
            iter_swap(first++, last);
}

template <class RandomAccessIterator>
void __reverse(RandomAccessIterator first, RandomAccessIterator last,
               random_access_iterator_tag) {
    while (first < last) iter_swap(first++, --last);
}

template <class BidirectionalIterator>
inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
    __reverse(first, last, iterator_category(first));
}

iterator_tags

    template <class ForwardIterator1, class ForwardIterator2, class ValueType>
    inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, ValueType*) {
	ValueType tmp = *a;
	*a = *b;
	*b = tmp;
    }

    template <class ForwardIterator1, class ForwardIterator2>
    inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
	__iter_swap(a, b, value_type(a));
    }

This example does exactly the same thing, using iterator_traits instead. Note how much simpler it is: the auxiliary function is no longer required.

    template <class ForwardIterator1, class ForwardIterator2>
    inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
        iterator_traits<ForwardIterator1>::value_type tmp = *a;
        *a = *b;
        *b = tmp;    
    }

This example uses the iterator_category iterator tag function: reverse can be implemented for either Bidirectional Iterators or for Random Access Iterators, but the algorithm for Random Access Iterators is more efficient. Consequently, reverse is written to dispatch on the iterator category. This dispatch takes place at compile time, and should not incur any run-time penalty.

    template <class BidirectionalIterator>
    void __reverse(BidirectionalIterator first, BidirectionalIterator last, 
		   bidirectional_iterator_tag) {
	while (true)
	    if (first == last || first == --last)
		return;
	    else
		iter_swap(first++, last);
    }

    template <class RandomAccessIterator>
    void __reverse(RandomAccessIterator first, RandomAccessIterator last,
		   random_access_iterator_tag) {
	while (first < last) iter_swap(first++, --last);
    }

    template <class BidirectionalIterator>
    inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
	__reverse(first, last, iterator_category(first));
    }

In this case, iterator_traits would not be different in any substantive way: it would still be necessary to use auxiliary functions to dispatch on the iterator category. The only difference is changing the top-level function to

    template <class BidirectionalIterator>
    inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
	__reverse(first, last, 
                  iterator_traits<first>::iterator_category());
    }

iterator_traits

template <class InputIterator>
iterator_traits<InputIterator>::value_type
last_value(InputIterator first, InputIterator last) {
  iterator_traits<InputIterator>::value_type result = *first;
  for (++first; first != last; ++first)
    result = *first;
  return result;
}    

(Note: this is an example of how to use iterator_traits; it is not an example of good code. There are better ways of finding the last element in a range of bidirectional iterators, or even forward iterators.)

iter_swap

int x = 1;
int y = 2;
assert(x == 1 && y == 2);
iter_swap(&x, &y);
assert(x == 2 && y == 1);

less_equal

list<int> L;
...
list<int>::iterator first_nonpositive = 
       find_if(L.begin(), L.end(), bind2nd(less_equal<int>(), 0));
assert(first_nonpositive == L.end() || *first_nonpositive <= 0);

less

list<int> L;
...
list<int>::iterator first_negative = 
       find_if(L.begin(), L.end(), bind2nd(less<int>(), 0));
assert(first_negative == L.end() || *first_negative < 0);

lexicographical_compare_3way

int main()
{
  int A1[] = {3, 1, 4, 2, 8, 5, 7};
  int A2[] = {3, 1, 4, 1, 5, 9, 3};
  int A3[] = {1, 2, 3, 4};
  int A4[] = {1, 2, 3, 4, 5};

  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int);
  const int N3 = sizeof(A3) / sizeof(int);
  const int N4 = sizeof(A4) / sizeof(int);

  int C12 = lexicographical_compare_3way(A1, A1 + N1, A2, A2 + N2);
  int C34 = lexicographical_compare_3way(A3, A3 + N3, A4, A4 + N4);

  cout << "A1[] and A2[]: " << C12 << endl;
  cout << "A3[] and A4[]: " << C34 << endl;
}

lexicographical_compare

int main()
{
  int A1[] = {3, 1, 4, 1, 5, 9, 3};
  int A2[] = {3, 1, 4, 2, 8, 5, 7};
  int A3[] = {1, 2, 3, 4};
  int A4[] = {1, 2, 3, 4, 5};

  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int);
  const int N3 = sizeof(A3) / sizeof(int);
  const int N4 = sizeof(A4) / sizeof(int);

  bool C12 = lexicographical_compare(A1, A1 + N1, A2, A2 + N2);
  bool C34 = lexicographical_compare(A3, A3 + N3, A4, A4 + N4);

  cout << "A1[] < A2[]: " << (C12 ? "true" : "false") << endl;
  cout << "A3[] < A4[]: " << (C34 ? "true" : "false") << endl;
}

List

list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(), 2);
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 1 2 0

logical_and

list<int> L;
...
list<int>::iterator in_range = 
     find_if(L.begin(), L.end(),
             compose2(logical_and<bool>(),
                      bind2nd(greater_equal<int>(), 1),
                      bind2nd(less_equal<int>(), 10)));
assert(in_range == L.end() || (*in_range >= 1 && *in_range <= 10));

logical_not

vector<bool> V;
...
transform(V.begin(), V.end(), V.begin(), logical_not<bool>());

logical_or

char str[MAXLEN];
...
const char* wptr = find_if(str, str + MAXLEN,
                           compose2(logical_or<bool>(),
                                    bind2nd(equal_to<char>(), ' '),
                                    bind2nd(equal_to<char>(), '\n')));
assert(wptr == str + MAXLEN || *wptr == ' ' || *wptr == '\n');  

lower_bound

int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 1; i <= 10; ++i) {
    int* p = lower_bound(A, A + N, i);
    cout << "Searching for " << i << ".  ";
    cout << "Result: index = " << p - A << ", ";
    if (p != A + N)
      cout << "A[" << p - A << "] == " << *p << endl;
    else
      cout << "which is off-the-end." << endl;
  }
}

Searching for 1.  Result: index = 0, A[0] == 1
Searching for 2.  Result: index = 1, A[1] == 2
Searching for 3.  Result: index = 2, A[2] == 3
Searching for 4.  Result: index = 5, A[5] == 5
Searching for 5.  Result: index = 5, A[5] == 5
Searching for 6.  Result: index = 6, A[6] == 8
Searching for 7.  Result: index = 6, A[6] == 8
Searching for 8.  Result: index = 6, A[6] == 8
Searching for 9.  Result: index = 7, which is off-the-end.
Searching for 10.  Result: index = 7, which is off-the-end.

make_heap

int main()
{
  int A[] = {1, 4, 2, 8, 5, 7};
  const int N = sizeof(A) / sizeof(int);

  make_heap(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  sort_heap(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;
}

Map

struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  map<const char*, int, ltstr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  
  cout << "june -> " << months["june"] << endl;
  map<const char*, int, ltstr>::iterator cur  = months.find("june");
  map<const char*, int, ltstr>::iterator prev = cur;
  map<const char*, int, ltstr>::iterator next = cur;    
  ++next;
  --prev;
  cout << "Previous (in alphabetical order) is " << (*prev).first << endl;
  cout << "Next (in alphabetical order) is " << (*next).first << endl;
}

max_element

int main()
{
  list<int> L;
  generate_n(front_inserter(L), 1000, rand);
  
  list<int>::const_iterator it = max_element(L.begin(), L.end());
  cout << "The largest element is " << *it << endl;
}

max

const int x = max(3, 9);
assert(x == 9);

mem_fun1_ref_t

int main() {
  int A1[5] = {1, 2, 3, 4, 5};
  int A2[5] = {1, 1, 2, 3, 5};
  int A3[5] = {1, 4, 1, 5, 9};

  vector<vector<int> > V;
  V.push_back(vector<int>(A1, A1 + 5));
  V.push_back(vector<int>(A2, A2 + 5));
  V.push_back(vector<int>(A3, A3 + 5));

  int indices[3] = {0, 2, 4};

  int& (vector<int>::*extract)(vector<int>::size_type);
  extract = vector<int>::operator[];
  transform(V.begin(), V.end(), indices,
            ostream_iterator<int>(cout, "\n"),
            mem_fun_ref(extract));
}

mem_fun1_t

struct Operation {
  virtual double eval(double) = 0;
};

struct Square : public Operation {
  double eval(double x) { return x * x; }
};

struct Negate : public Operation {
  double eval(double x) { return -x; }
};

int main() {
  vector<Operation*> operations;
  vector<double> operands;

  operations.push_back(new Square);
  operations.push_back(new Square);
  operations.push_back(new Negate);
  operations.push_back(new Negate);
  operations.push_back(new Square);

  operands.push_back(1);
  operands.push_back(2);
  operands.push_back(3);
  operands.push_back(4);
  operands.push_back(5);

  transform(operations.begin(), operations.end(),
            operands.begin(),
            ostream_iterator<double>(cout, "\n"),
            mem_fun(Operation::eval));
}

mem_fun_ref_t

struct B {
  virtual void print() = 0;
};

struct D1 : public B {
  void print() { cout << "I'm a D1" << endl; }
};

struct D2 : public B {
  void print() { cout << "I'm a D2" << endl; }
};

int main()
{
  vector<D1> V;

  V.push_back(D1());
  V.push_back(D1());

  for_each(V.begin(), V.end(), mem_fun_ref(B::print));
}

mem_fun_t

struct B {
  virtual void print() = 0;
};

struct D1 : public B {
  void print() { cout << "I'm a D1" << endl; }
};

struct D2 : public B {
  void print() { cout << "I'm a D2" << endl; }
};

int main()
{
  vector<B*> V;

  V.push_back(new D1);
  V.push_back(new D2);
  V.push_back(new D2);
  V.push_back(new D1);

  for_each(V.begin(), V.end(), mem_fun(&B::print));
}

merge

int main()
{
  int A1[] = { 1, 3, 5, 7 };
  int A2[] = { 2, 4, 6, 8 };
  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int);

  merge(A1, A1 + N1, A2, A2 + N2, 
        ostream_iterator<int>(cout, " "));
  // The output is "1 2 3 4 5 6 7 8"
}

min_element

int main()
{
  list<int> L;
  generate_n(front_inserter(L), 1000, rand);
  
  list<int>::const_iterator it = min_element(L.begin(), L.end());
  cout << "The smallest element is " << *it << endl;
}

min

const int x = min(3, 9);
assert(x == 3);

minus

const int N = 1000;
vector<double> V1(N);
vector<double> V2(N);
vector<double> V3(N);

iota(V1.begin(), V1.end(), 1);
fill(V2.begin(), V2.end(), 75);

assert(V2.size() >= V1.size() && V3.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),
          minus<double>());

mismatch

int A1[] = { 3, 1, 4, 1, 5, 9, 3 };
int A2[] = { 3, 1, 4, 2, 8, 5, 7 };
const int N = sizeof(A1) / sizeof(int);

pair<int*, int*> result = mismatch(A1, A1 + N, A2);
cout << "The first mismatch is in position " << result.first - A1 << endl;
cout << "Values are: " << *(result.first) << ", " << *(result.second) << endl;

modulus

const int N = 1000;
vector<double> V1(N);
vector<double> V2(N);
vector<double> V3(N);

iota(V1.begin(), V1.end(), 1);
fill(V2.begin(), V2.end(), 75);

assert(V2.size() >= V1.size() && V3.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),
          modulus<int>());

Multimap

struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  multimap<const char*, int, ltstr> m;
  
  m.insert(pair<const char* const, int>("a", 1));
  m.insert(pair<const char* const, int>("c", 2));
  m.insert(pair<const char* const, int>("b", 3));
  m.insert(pair<const char* const, int>("b", 4));
  m.insert(pair<const char* const, int>("a", 5));
  m.insert(pair<const char* const, int>("b", 6));

  cout << "Number of elements with key a: " << m.count("a") << endl;
  cout << "Number of elements with key b: " << m.count("b") << endl;
  cout << "Number of elements with key c: " << m.count("c") << endl;

  cout << "Elements in m: " << endl;
  for (multimap<const char*, int, ltstr>::iterator it = m.begin();
       it != m.end();
       ++it)
   cout << "  [" << (*it).first << ", " << (*it).second << "]" << endl;
}

multiset

int main()
{
  const int N = 10;
  int a[N] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};
  int b[N] = {4, 4, 2, 4, 2, 4, 0, 1, 5, 5};

  multiset<int> A(a, a + N);
  multiset<int> B(b, b + N);
  multiset<int> C;

  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<int>(cout, " "));   
  cout << endl;

  cout << "Union: ";
  set_union(A.begin(), A.end(), B.begin(), B.end(),
            ostream_iterator<int>(cout, " "));
  cout << endl;

  cout << "Intersection: ";
  set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                   ostream_iterator<int>(cout, " "));
  cout << endl;  

  set_difference(A.begin(), A.end(), B.begin(), B.end(),
                 inserter(C, C.begin()));
  cout << "Set C (difference of A and B): ";
  copy(C.begin(), C.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
}

negate

const int N = 1000;
vector<double> V1(N);
vector<double> V2(N);

iota(V1.begin(), V1.end(), 1);

assert(V2.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(),
          negate<int>());

next_permutation

template <class BidirectionalIterator> 
void snail_sort(BidirectionalIterator first, BidirectionalIterator last)
{
  while (next_permutation(first, last)) {}
}

int main()
{
  int A[] = {8, 3, 6, 1, 2, 5, 7, 4};
  const int N = sizeof(A) / sizeof(int);

  snail_sort(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, "\n"));
}

not_equal_to

list<int> L;
...
list<int>::iterator first_nonzero = 
       find_if(L.begin(), L.end(), bind2nd(not_equal_to<int>(), 0));
assert(first_nonzero == L.end() || *first_nonzero != 0);

nth_element

int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);

nth_element(A, A + 6, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result is "5 2 6 1 4 3 7 8 9 10 11 12".

operators

template <class T> void relations(T x, T y)
{
  if (x == y) assert(!(x != y));
  else assert(x != y);

  if (x < y) {
    assert(x <= y);
    assert(y > x);
    assert(y >= x);
  }
  else if (y < x) {
    assert(y <= x);
    assert(x < y);
    assert(x <= y);
  }
  else {
    assert(x <= y);
    assert(x >= y);
  }
}  

ostream_iterator

vector<int> V;
// ...
copy(V.begin(), V.end(), ostream_iterator<int>(cout, "\n"));

output_iterator

class my_output_iterator : public output_iterator
{
  ...
};

output_iterator_tag

pair

pair<bool, double> result = do_a_calculation();
if (result.first)
  do_something_more(result.second);
else
  report_error();

partial_sort_copy

int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);

vector<int> V(4);
partial_sort_copy(A, A + N, V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
// The printed result is "1 2 3 4".

partial_sort

int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);

partial_sort(A, A + 5, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result is "1 2 3 4 5 11 12 10 9 8 7 6".

partial_sum

int main()
{
  const int N = 10;
  int A[N];

  fill(A, A+N, 1);
  cout << "A:                 ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  cout << "Partial sums of A: ";
  partial_sum(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;
}  

partition

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
partition(A, A + N,
          compose1(bind2nd(equal_to<int>(), 0),
                   bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "10 2 8 4 6 5 7 3 9 1". [1]

plus

const int N = 1000;
vector<double> V1(N);
vector<double> V2(N);
vector<double> V3(N);

iota(V1.begin(), V1.end(), 1);
fill(V2.begin(), V2.end(), 75);

assert(V2.size() >= V1.size() && V3.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),
          plus<double>());

pointer_to_binary_function

list<char*> L;
...
list<char*>::iterator item = 
              find_if(L.begin(), L.end(),
                      not1(binder2nd(ptr_fun(strcmp), "OK")));

pointer_to_unary_function

transform(first, last, first, fabs);

transform(first, last, first,
          compose1(negate<double>, ptr_fun(fabs)));

pop_heap

int main()
{
  int A[] = {1, 2, 3, 4, 5, 6};
  const int N = sizeof(A) / sizeof(int);

  make_heap(A, A+N);
  cout << "Before pop: ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));

  pop_heap(A, A+N);
  cout << endl << "After pop: ";
  copy(A, A+N-1, ostream_iterator<int>(cout, " "));
  cout << endl << "A[N-1] = " << A[N-1] << endl;
}

The output is

Before pop: 6 5 3 4 2 1 
After pop: 5 4 3 1 2 
A[N-1] = 6

power

int main() {
  cout << "2 ** 30 = " << power(2, 30) << endl;
}

prev_permutation

int main()
{
  int A[] = {2, 3, 4, 5, 6, 1};
  const int N = sizeof(A) / sizeof(int);

  cout << "Initially:              ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  prev_permutation(A, A+N);
  cout << "After prev_permutation: ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  next_permutation(A, A+N);
  cout << "After next_permutation: ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;
}

priority_queue

int main() {
  priority_queue<int> Q;
  Q.push(1);
  Q.push(4);
  Q.push(2);
  Q.push(8);
  Q.push(5);
  Q.push(7);
  
  assert(Q.size() == 6);

  assert(Q.top() == 8);
  Q.pop();

  assert(Q.top() == 7);
  Q.pop();

  assert(Q.top() == 5);
  Q.pop();

  assert(Q.top() == 4);
  Q.pop();

  assert(Q.top() == 2);
  Q.pop();

  assert(Q.top() == 1);
  Q.pop();

  assert(Q.empty());
}

project1st

int main()
{
  vector<int> v1(10, 137);
  vector<char*> v2(10, (char*) 0);
  vector<int> result(10);

  transform(v1.begin(), v1.end(), v2.begin(), result.begin(),
            project1st<int, char*>());
  assert(equal(v1.begin(), v1.end(), result.begin()));
}           

project2nd

int main()
{
  vector<char*> v1(10, (char*) 0);
  vector<int> v2(10, 137);
  vector<int> result(10);

  transform(v1.begin(), v1.end(), v2.begin(), result.begin(),
            project2nd<char*, int>());
  assert(equal(v2.begin(), v2.end(), result.begin()));
}           

ptr_fun

push_heap

int main()
{
  int A[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  make_heap(A, A + 9);
  cout << "[A, A + 9)  = ";
  copy(A, A + 9, ostream_iterator<int>(cout, " "));
  
  push_heap(A, A + 10);
  cout << endl << "[A, A + 10) = ";
  copy(A, A + 10, ostream_iterator<int>(cout, " "));
  cout << endl;
}

The output is

[A, A + 9)  = 8 7 6 3 4 5 2 1 0 
[A, A + 10) = 9 8 6 3 7 5 2 1 0 4 

queue

int main() {
  queue<int> Q;
  Q.push(8);
  Q.push(7);
  Q.push(6);
  Q.push(2);
  
  assert(Q.size() == 4);
  assert(Q.back() == 2);

  assert(Q.front() == 8);
  Q.pop();

  assert(Q.front() == 7);
  Q.pop();

  assert(Q.front() == 6);
  Q.pop();
  
  assert(Q.front() == 2);
  Q.pop();

  assert(Q.empty());
}

random_access_iterator

class my_random_access_iterator : public random_access_iterator<double> 
{
  ...
};

random_access_iterator_tag

random_sample

int main()
{
  const int N = 10;
  const int n = 4;
  int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int B[n];

  random_sample(A, A+N, B, B+n);
  copy(B, B + n, ostream_iterator<int>(cout, " "));
  // The printed value might be 1 6 3 5, 
  //  or any of 5039 other possibilities.
}

random_sample_n

int main()
{
  const int N = 10;
  int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  random_sample_n(A, A+N, ostream_iterator<int>(cout, " "), 4);
  // The printed value might be 3 5 6 10,
  //  or any of 209 other possibilities.
}

random_shuffle

const int N = 8;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result might be 7 1 6 3 2 5 4 8, 
//  or any of 40,319 other possibilities.

raw_storage_iterator

class Int {
public:
  Int(int x) : val(x) {}
  int get() { return val; }
private:
  int val;
};    

int main()
{
  int A1[] = {1, 2, 3, 4, 5, 6, 7};
  const int N = sizeof(A1) / sizeof(int);

  Int* A2 = (Int*) malloc(N * sizeof(Int));     
  transform(A1, A1 + N, 
            raw_storage_iterator<Int*, int>(A2),
            negate<int>());
}

remove_copy

vector<int> V;
V.push_back(-2);
V.push_back(0);
V.push_back(-1);
V.push_back(0);
V.push_back(1);
V.push_back(2);

remove_copy(V.begin(), V.end(), 
            ostream_iterator<int>(cout, "\n"),
            0);

remove_copy_if

vector<int> V1;
V.push_back(-2);
V.push_back(0);
V.push_back(-1);
V.push_back(0);
V.push_back(1);
V.push_back(2);

vector<int> V2;
remove_copy_if(V1.begin(), V1.end(), 
               back_inserter(V2),
               bind2nd(less<int>(), 0));

remove

vector<int> V;
V.push_back(3);
V.push_back(1);
V.push_back(4);
V.push_back(1);
V.push_back(5);
V.push_back(9);

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    // The output is "3 1 4 1 5 9".

vector<int>::iterator new_end = remove(V.begin(), V.end(), 1);
copy(V.begin(), new_end, ostream_iterator<int>(cout, " "));
    // The output is "3 4 5 9".

remove_if

vector<int> V;
V.push_back(1);
V.push_back(4);
V.push_back(2);
V.push_back(8);
V.push_back(5);
V.push_back(7);

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    // The output is "1 4 2 8 5 7"

vector<int>::iterator new_end = 
        remove_if(V.begin(), V.end(), 
                  compose1(bind2nd(equal_to<int>(), 0),
                           bind2nd(modulus<int>(), 2)));
V.erase(new_end, V.end()); [1]

copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    // The output is "1 5 7".

replace_copy

vector<int> V1;
V1.push_back(1);
V1.push_back(2);
V1.push_back(3);
V1.push_back(1);

vector<int> V2(4);

replace_copy(V1.begin(), V1.end(), V2.begin(), 1, 99);
assert(V[0] == 99 && V[1] == 2 && V[2] == 3 && V[3] == 99);

replace_copy_if

vector<int> V1;
V1.push_back(1);
V1.push_back(-1);
V1.push_back(-5);
V1.push_back(2);

vector<int> V2(4);

replace_copy_if(V1.begin(), V1.end(), V2.begin(),
                bind2nd(less<int>(), 0),
                0);
assert(V[0] == 1 && V[1] == 0 && V[2] == 0 && V[3] == 2);

replace

vector<int> V;
V.push_back(1);
V.push_back(2);
V.push_back(3);
V.push_back(1);

replace(V.begin(), V.end(), 1, 99);
assert(V[0] == 99 && V[3] == 99);

replace_if

vector<int> V;
V.push_back(1);
V.push_back(-3);
V.push_back(2);
V.push_back(-1);

replace_if(V.begin(), V.end(), bind2nd(less<int>(), 0), -1);
assert(V[1] == 0 && V[3] == 0);

return_temporary_buffer

int main()
{
  pair<int*, ptrdiff_t> P = get_temporary_buffer(10000, (int*) 0);
  int* buf = P.first;
  ptrdiff_t N = P.second;
  uninitialized_fill_n(buf, N, 42);
  int* result = find_if(buf, buf + N, bind2nd(not_equal_to<int>(), 42));
  assert(result == buf + N);
  return_temporary_buffer(buf);
}        

ReverseBidirectionalIterator

template <class T>
void forw(const list<T>& L)
{
   list<T>::iterator first = L.begin();
   list<T>::iterator last = L.end();
   while (first != last) 
      cout << *first++ << endl;
}      

template <class T>
void rev(const list<T>& L)
{
   typedef reverse_bidirectional_iterator<list<T>::iterator,
                                          T,
                                          list<T>::reference_type,
                                          list<T>::difference_type> 
           reverse_iterator; [2]
   reverse_iterator rfirst(L.end());
   reverse_iterator rlast(L.begin());

   while (rfirst != rlast) 
      cout << *rfirst++ << endl;
}      

In the function forw, the elements are printed in the order *first, *(first+1), ..., *(last-1). In the function rev, they are printed in the order *(last - 1), *(last-2), ..., *first. [3]

reverse_copy

vector<int> V;
V.push_back(0);
V.push_back(1);
V.push_back(2);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
                // Output: 0 1 2
list<int> L(V.size());
reverse_copy(V.begin(), V.end(), L.begin());
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
                // Output: 2 1 0

reverse

vector<int> V;
V.push_back(0);
V.push_back(1);
V.push_back(2);
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
                // Output: 0 1 2
reverse(V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
                // Output: 2 1 0

ReverseIterator

template <class T>
void forw(const vector<T>& V)
{
   vector<T>::iterator first = V.begin();
   vector<T>::iterator last = V.end();
   while (first != last) 
      cout << *first++ << endl;
}      

template <class T>
void rev(const vector<T>& V)
{
   typedef reverse_iterator<vector<T>::iterator,
                            T,
                            vector<T>::reference_type,
                            vector<T>::difference_type> 
           reverse_iterator; [2]
   reverse_iterator rfirst(V.end());
   reverse_iterator rlast(V.begin());

   while (rfirst != rlast) 
      cout << *rfirst++ << endl;
}      

In the function forw, the elements are printed in the order *first, *(first+1), ..., *(last-1). In the function rev, they are printed in the order *(last - 1), *(last-2), ..., *first. [3]

Rope

crope r(1000000, 'x');          // crope is rope<char>. wrope is rope<wchar_t>
                                // Builds a rope containing a million 'x's.
                                // Takes much less than a MB, since the
                                // different pieces are shared.
crope r2 = r + "abc" + r;       // concatenation; takes on the order of 100s
                                // of machine instructions; fast
crope r3 = r2.substr(1000000, 3);       // yields "abc"; fast.
crope r4 = r2.substr(1000000, 1000000); // also fast.
reverse(r2.mutable_begin(), r2.mutable_end());
                                // correct, but slow; may take a
                                // minute or more.

rotate_copy

const char alpha[] = "abcdefghijklmnopqrstuvwxyz";
rotate_copy(alpha, alpha + 13, alpha + 26, ostream_iterator<char>(cout));
// The output is nopqrstuvwxyzabcdefghijklm

rotate

char alpha[] = "abcdefghijklmnopqrstuvwxyz";
rotate(alpha, alpha + 13, alpha + 26);
printf("%s\n", alpha);
// The output is nopqrstuvwxyzabcdefghijklm

search

  const char S1[] = "Hello, world!";
  const char S2[] = "world";
  const int N1 = sizeof(S1) - 1;
  const int N2 = sizeof(S2) - 1;

  const char* p = search(S1, S1 + N1, S2, S2 + N2);
  printf("Found subsequence \"%s\" at character %d of sequence \"%s\".\n",
         S2, p - S1, S1);

search_n

bool eq_nosign(int x, int y) { return abs(x) == abs(y); }

void lookup(int* first, int* last, size_t count, int val) {
  cout << "Searching for a sequence of "
       << count
       << " '" << val << "'"
       << (count != 1 ? "s: " : ":  ");
  int* result = search_n(first, last, count, val);
  if (result == last)
    cout << "Not found" << endl;
  else
    cout << "Index = " << result - first << endl;
}

void lookup_nosign(int* first, int* last, size_t count, int val) {
  cout << "Searching for a (sign-insensitive) sequence of "
       << count
       << " '" << val << "'"
       << (count != 1 ? "s: " : ":  ");
  int* result = search_n(first, last, count, val, eq_nosign);
  if (result == last)
    cout << "Not found" << endl;
  else
    cout << "Index = " << result - first << endl;
}

int main() {
  const int N = 10;
  int A[N] = {1, 2, 1, 1, 3, -3, 1, 1, 1, 1};

  lookup(A, A+N, 1, 4);
  lookup(A, A+N, 0, 4);
  lookup(A, A+N, 1, 1);
  lookup(A, A+N, 2, 1);
  lookup(A, A+N, 3, 1);
  lookup(A, A+N, 4, 1);

  lookup(A, A+N, 1, 3);
  lookup(A, A+N, 2, 3);
  lookup_nosign(A, A+N, 1, 3);
  lookup_nosign(A, A+N, 2, 3);
}

The output is

Searching for a sequence of 1 '4':  Not found
Searching for a sequence of 0 '4's: Index = 0
Searching for a sequence of 1 '1':  Index = 0
Searching for a sequence of 2 '1's: Index = 2
Searching for a sequence of 3 '1's: Index = 6
Searching for a sequence of 4 '1's: Index = 6
Searching for a sequence of 1 '3':  Index = 4
Searching for a sequence of 2 '3's: Not found
Searching for a (sign-insensitive) sequence of 1 '3':  Index = 4
Searching for a (sign-insensitive) sequence of 2 '3's: Index = 4

select1st

int main()
{
  map<int, double> M;
  M[1] = 0.3;
  M[47] = 0.8;
  M[33] = 0.1;

  transform(M.begin(), M.end(), ostream_iterator<int>(cout, " "),
            select1st<map<int, double>::value_type>());
  // The output is  1 33 47.
}

select2nd

int main()
{
  map<int, double> M;
  M[1] = 0.3;
  M[47] = 0.8;
  M[33] = 0.1;

  transform(M.begin(), M.end(), ostream_iterator<double>(cout, " "),
            select2nd<map<int, double>::value_type>());
  // The output is  0.3 0.1 0.8
}

sequence_buffer

int main()
{
  const char* const s = "this is a test";
  const int N = strlen(s);

  crope r;
  transform(s, s + N,
            sequence_buffer<crope>(r),
            toupper);
  cout << "r = " << r << endl;
}

set_difference

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  int A1[] = {1, 3, 5, 7, 9, 11};
  int A2[] = {1, 1, 2, 3, 5, 8, 13};  
  char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
  char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };

  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int); 
  const int N3 = sizeof(A3);
  const int N4 = sizeof(A4);

  cout << "Difference of A1 and A2: ";
  set_difference(A1, A1 + N1, A2, A2 + N2,
                 ostream_iterator<int>(cout, " "));
  cout << endl 
       << "Difference of A3 and A4: ";
  set_difference(A3, A3 + N3, A4, A4 + N4, 
                   ostream_iterator<char>(cout, " "),
                   lt_nocase);
  cout << endl;
}

The output is

Difference of A1 and A2: 7 9 11 
Difference of A3 and A4: B B g H 

set

struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  const int N = 6;
  const char* a[N] = {"isomer", "ephemeral", "prosaic", 
                      "nugatory", "artichoke", "serif"};
  const char* b[N] = {"flat", "this", "artichoke",
                      "frigate", "prosaic", "isomer"};

  set<const char*, ltstr> A(a, a + N);
  set<const char*, ltstr> B(b, b + N);
  set<const char*, ltstr> C;

  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));   
  cout << endl;

  cout << "Union: ";
  set_union(A.begin(), A.end(), B.begin(), B.end(),
            ostream_iterator<const char*>(cout, " "),
            ltstr());   
  cout << endl;

  cout << "Intersection: ";
  set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                   ostream_iterator<const char*>(cout, " "),
                   ltstr());    
  cout << endl;

  set_difference(A.begin(), A.end(), B.begin(), B.end(),
                 inserter(C, C.begin()),
                 ltstr());
  cout << "Set C (difference of A and B): ";
  copy(C.begin(), C.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
}

set_intersection

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  int A1[] = {1, 3, 5, 7, 9, 11};
  int A2[] = {1, 1, 2, 3, 5, 8, 13};  
  char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'h', 'H'};
  char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };

  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int); 
  const int N3 = sizeof(A3);
  const int N4 = sizeof(A4);

  cout << "Intersection of A1 and A2: ";
  set_intersection(A1, A1 + N1, A2, A2 + N2,
                   ostream_iterator<int>(cout, " "));
  cout << endl 
       << "Intersection of A3 and A4: ";
  set_intersection(A3, A3 + N3, A4, A4 + N4, 
                   ostream_iterator<char>(cout, " "),
                   lt_nocase);
  cout << endl;
}

The output is

Intersection of A1 and A2: 1 3 5 
Intersection of A3 and A4: a b b f h 

set_symmetric_difference

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  int A1[] = {1, 3, 5, 7, 9, 11};
  int A2[] = {1, 1, 2, 3, 5, 8, 13};  
  char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
  char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };

  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int); 
  const int N3 = sizeof(A3);
  const int N4 = sizeof(A4);

  cout << "Symmetric difference of A1 and A2: ";
  set_symmetric_difference(A1, A1 + N1, A2, A2 + N2,
                           ostream_iterator<int>(cout, " "));
  cout << endl 
       << "Symmetric difference of A3 and A4: ";
  set_symmetric_difference(A3, A3 + N3, A4, A4 + N4, 
                           ostream_iterator<char>(cout, " "),
                           lt_nocase);
  cout << endl;
}

The output is

Symmetric difference of A1 and A2: 1 2 7 8 9 11 13 
Symmetric difference of A3 and A4: B B C D F g H 

set_union

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  int A1[] = {1, 3, 5, 7, 9, 11};
  int A2[] = {1, 1, 2, 3, 5, 8, 13};  
  char A3[] = {'a', 'b', 'B', 'B', 'f', 'H'};
  char A4[] = {'A', 'B', 'b', 'C', 'D', 'F', 'F', 'h', 'h'};

  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int); 
  const int N3 = sizeof(A3);
  const int N4 = sizeof(A4);

  cout << "Union of A1 and A2: ";
  set_union(A1, A1 + N1, A2, A2 + N2,
            ostream_iterator<int>(cout, " "));
  cout << endl 
       << "Union of A3 and A4: ";
  set_union(A3, A3 + N3, A4, A4 + N4, 
            ostream_iterator<char>(cout, " "),
            lt_nocase);
  cout << endl;
}

The output is

Union of A1 and A2: 1 1 2 3 5 7 8 9 11 13 
Union of A3 and A4: a b B B C D f F H h 

Slist

int main() {
  slist<int> L;
  L.push_front(0);
  L.push_front(1);
  L.insert_after(L.begin(), 2);
  copy(L.begin(), L.end(),        // The output is 1 2 0
       ostream_iterator<int>(cout, " "));
  cout << endl;

  slist<int>::iterator back = L.previous(L.end());
  back = L.insert_after(back, 3); 
  back = L.insert_after(back, 4);
  back = L.insert_after(back, 5);
  copy(L.begin(), L.end(),        // The output is 1 2 0 3 4 5
       ostream_iterator<int>(cout, " "));
  cout << endl;
}

sort_heap

int main()
{
  int A[] = {1, 4, 2, 8, 5, 7};
  const int N = sizeof(A) / sizeof(int);

  make_heap(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  sort_heap(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;
}

sort

int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
sort(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is " 1 2 4 5 7 8".

stable_partition

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
stable_partition(A, A + N,
                 compose1(bind2nd(equal_to<int>(), 0),
                          bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "2 4 6 8 10 1 3 5 7 9". [1]

stable_sort

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  char A[] = "fdBeACFDbEac";
  const int N = sizeof(A) - 1;
  stable_sort(A, A+N, lt_nocase);
  printf("%s\n", A);
  // The printed result is ""AaBbCcdDeEfF".
}

stack

int main() {
  stack<int> S;
  S.push(8);
  S.push(7);
  S.push(4);
  assert(S.size() == 3);

  assert(S.top() == 4);
  S.pop();

  assert(S.top() == 7);
  S.pop();

  assert(S.top() == 8);
  S.pop();

  assert(S.empty());
}

subtractive_rng

int main()
{
  subtractive_rng R;
  for (int i = 0; i < 20; ++i)
    cout << R(5) << ' ';
  cout << endl;
}
// The output is   3 2 3 2 4 3 1 1 2 2 0 3 4 4 4 4 2 1 0 0 

swap

int x = 1;
int y = 2;
assert(x == 1 && y == 2);
swap(x, y);
assert(x == 2 && y == 1);

swap_ranges

vector<int> V1, V2;
V1.push_back(1);
V1.push_back(2);
V2.push_back(3);
V2.push_back(4);

assert(V1[0] == 1 && V1[1] == 2 && V2[0] == 3 && V2[1] == 4);
swap_ranges(V1.begin(), V1.end(), V2.begin());
assert(V1[0] == 3 && V1[1] == 4 && V2[0] == 1 && V2[1] == 2);

temporary_buffer

int main()
{
  vector<int> V(50);
  iota(V.begin(), V.end(), 1);

  temporary_buffer<vector<int>::iterator, int> buf(V.begin(), V.end());
  copy(V.rbegin(), V.rbegin() + buf.size(), buf.begin());
  copy(buf.begin(), buf.end(), ostream_iterator<int>(cout, "\n"));
}

times

const int N = 1000;
vector<double> V1(N);
vector<double> V2(N);
vector<double> V3(N);

iota(V1.begin(), V1.end(), 1);
fill(V2.begin(), V2.end(), 75);

assert(V2.size() >= V1.size() && V3.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),
          multiplies<double>());

transform

const int N = 1000;
double A[N];
iota(A, A+N, 1);

transform(A, A+N, A, negate<double>());

Calculate the sum of two vectors, storing the result in a third vector.

const int N = 1000;
vector<int> V1(N);
vector<int> V2(N);
vector<int> V3(N);

iota(V1.begin(), V1.end(), 1);
fill(V2.begin(), V2.end(), 75);

assert(V2.size() >= V1.size() && V3.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),
          plus<int>());

unary_compose

vector<double> angles;
vector<double> sines;
const double pi = 3.14159265358979323846;
...
assert(sines.size() >= angles.size());
transform(angles.begin(), angles.end(), sines.begin(),
          compose1(negate<double>(),
                   compose1(ptr_fun(sin),
                            bind2nd(multiplies<double>(), pi / 180.))));

unary_function

struct sine : public unary_function<double, double> {
    double operator()(double x) { return sin(x); }
};

unary_negate

list<int> L;
...
list<int>::iterator in_range = 
     find_if(L.begin(), L.end(),
             not1(compose2(logical_and<bool>(),
                           bind2nd(greater_equal<int>(), 1),
                           bind2nd(less_equal<int>(), 10))));
assert(in_range == L.end() || !(*in_range >= 1 && *in_range <= 10));

uninitialized_copy

class Int {
public:
  Int(int x) : val(x) {}
  int get() { return val; }
private:
  int val;
};    

int main()
{
  int A1[] = {1, 2, 3, 4, 5, 6, 7};
  const int N = sizeof(A1) / sizeof(int);

  Int* A2 = (Int*) malloc(N * sizeof(Int));
  uninitialized_copy(A1, A1 + N, A2);
}

uninitialized_copy_n

class Int {
public:
  Int(int x) : val(x) {}
  int get() { return val; }
private:
  int val;
};    

int main()
{
  int A1[] = {1, 2, 3, 4, 5, 6, 7};
  const int N = sizeof(A1) / sizeof(int);

  Int* A2 = (Int*) malloc(N * sizeof(Int));
  uninitialized_copy_n(A1, N, A2);
}

uninitialized_fill

class Int {
public:
  Int(int x) : val(x) {}
  int get() { return val; }
private:
  int val;
};    

int main()
{
  const int N = 137;
  
  Int val(46);
  Int* A = (Int*) malloc(N * sizeof(Int));
  uninitialized_fill(A, A + N, val);
}

uninitialized_fill_n

class Int {
public:
  Int(int x) : val(x) {}
  int get() { return val; }
private:
  int val;
};    

int main()
{
  const int N = 137;
  
  Int val(46);
  Int* A = (Int*) malloc(N * sizeof(Int));
  uninitialized_fill_n(A, N, val);
}

unique_copy

const int A[] = {2, 7, 7, 7, 1, 1, 8, 8, 8, 2, 8, 8};
unique_copy(A, A + sizeof(A) / sizeof(int), 
            ostream_iterator<int>(cout, " "));
// The output is "2 7 1 8 2 8".

unique

vector<int> V;
V.push_back(1);
V.push_back(3);
V.push_back(3);
V.push_back(3);
V.push_back(2);
V.push_back(2);
V.push_back(1);

vector<int>::iterator new_end = unique(V.begin(), V.end());
copy(V.begin(), new_end, ostream_iterator<int>(cout, " "));
    // The output it "1 3 2 1".

Remove all duplicates from a vector of chars, ignoring case. First sort the vector, then remove duplicates from consecutive groups.

inline bool eq_nocase(char c1, char c2) { return tolower(c1) == tolower(c2); }
inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  const char init[] = "The Standard Template Library";
  vector<char> V(init, init + sizeof(init));
  sort(V.begin(), V.end(), lt_nocase);
  copy(V.begin(), V.end(), ostream_iterator<char>(cout));
  cout << endl;
  vector<char>::iterator new_end = unique(V.begin(), V.end(), eq_nocase);
  copy(V.begin(), new_end, ostream_iterator<char>(cout));
  cout << endl;
}
// The output is:
//    aaaabddeeehiLlmnprrrStTtTy
//  abdehiLmnprSty

upper_bound

int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 1; i <= 10; ++i) {
    int* p = upper_bound(A, A + N, i);
    cout << "Searching for " << i << ".  ";
    cout << "Result: index = " << p - A << ", ";
    if (p != A + N)
      cout << "A[" << p - A << "] == " << *p << endl;
    else
      cout << "which is off-the-end." << endl;
  }
}

Searching for 1.  Result: index = 1, A[1] == 2
Searching for 2.  Result: index = 2, A[2] == 3
Searching for 3.  Result: index = 5, A[5] == 5
Searching for 4.  Result: index = 5, A[5] == 5
Searching for 5.  Result: index = 6, A[6] == 8
Searching for 6.  Result: index = 6, A[6] == 8
Searching for 7.  Result: index = 6, A[6] == 8
Searching for 8.  Result: index = 7, which is off-the-end.
Searching for 9.  Result: index = 7, which is off-the-end.
Searching for 10.  Result: index = 7, which is off-the-end.

value_type

template <class ForwardIterator1, class ForwardIterator2, class ValueType>
inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, ValueType*) {
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

template <class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
    __iter_swap(a, b, value_type(a));
}

Vector

vector<int> V;
V.insert(V.begin(), 3);
assert(V.size() == 1 && V.capacity() >= 1 && V[0] == 3);