C++ Algorithms

  #include <numeric>
  TYPE accumulate( iterator start, iterator end, TYPE val );
  TYPE accumulate( iterator start, iterator end, TYPE val, BinaryFunction f );

  #include <numeric>
  iterator adjacent_difference( iterator start, iterator end, iterator result );
  iterator adjacent_difference( iterator start, iterator end, iterator result, BinaryFunction f );

The adjacent_difference() function calculates the differences between adjacent elements in the range [start,end) and stores the result starting at result.

If a binary function f is given, it is used instead of the - operator to compute the differences.

adjacent_difference() runs in linear time.

  #include <algorithm>
  iterator adjacent_find( iterator start, iterator end );
  iterator adjacent_find( iterator start, iterator end, BinPred pr );

The adjacent_find() function searches between start and end for two consecutive identical elements. If the binary predicate pr is specified, then it is used to test whether two elements are the same or not.

The return value is an iterator that points to the first of the two elements that are found. If no matching elements are found, the returned iterator points to end.

For example, the following code creates a vector containing the integers between 0 and 10 with 7 appearing twice in a row. adjacent_find() is then used to find the location of the pair of 7's:

 vector<int> v1;
 for( int i = 0; i < 10; i++ ) {
   v1.push_back(i);
   // add a duplicate 7 into v1
   if( i == 7 ) {
     v1.push_back(i);           

   }
 }              

 vector<int>::iterator result;
 result = adjacent_find( v1.begin(), v1.end() );                

 if( result == v1.end() ) {
   cout << "Did not find adjacent elements in v1" << endl;
 }              

 else {
   cout << "Found matching adjacent elements starting at " << *result << endl;
 }              

  #include <algorithm>
  bool binary_search( iterator start, iterator end, const TYPE& val );
  bool binary_search( iterator start, iterator end, const TYPE& val, Comp f );

The binary_search() function searches from start to end for val. The elements between start and end that are searched should be in ascending order as defined by the < operator. Note that a binary search will not work unless the elements being searched are in order.

If val is found, binary_search() returns true, otherwise false.

If the function f is specified, then it is used to compare elements.

For example, the following code uses binary_search() to determine if the integers 0-9 are in an array of integers:

 int nums[] = { -242, -1, 0, 5, 8, 9, 11 };
 int start = 0;
 int end = 7;           

 for( int i = 0; i < 10; i++ ) {
   if( binary_search( nums+start, nums+end, i ) ) {
     cout << "nums[] contains " << i << endl;
   } else {
     cout << "nums[] DOES NOT contain " << i << endl;
   }
 }              

When run, this code displays the following output:

 nums[] contains 0
 nums[] DOES NOT contain 1
 nums[] DOES NOT contain 2
 nums[] DOES NOT contain 3
 nums[] DOES NOT contain 4
 nums[] contains 5
 nums[] DOES NOT contain 6
 nums[] DOES NOT contain 7
 nums[] contains 8
 nums[] contains 9              

  #include <algorithm>
  iterator copy( iterator start, iterator end, iterator dest );

The copy() function copies the elements between start and end to dest. In other words, after copy() has run,

 *dest == *start
 *(dest+1) == *(start+1)
 *(dest+2) == *(start+2)
 ...
 *(dest+N) == *(start+N)                

The return value is an iterator to the last element copied. copy() runs in linear time.

For example, the following code uses copy() to copy the contents of one vector to another:

 vector<int> from_vector;
 for( int i = 0; i < 10; i++ ) {
   from_vector.push_back( i );
 }              

 vector<int> to_vector(10);               

 copy( from_vector.begin(), from_vector.end(), to_vector.begin() );             

 cout << "to_vector contains: ";
 for( unsigned int i = 0; i < to_vector.size(); i++ ) {
   cout << to_vector[i] << " ";
 }
 cout << endl;            

  #include <algorithm>
  iterator copy_backward( iterator start, iterator end, iterator dest );

copy_backward() is similar to (C++ Strings) copy(), in that both functions copy elements from start to end to dest. The copy_backward() function , however, starts depositing elements at dest and then works backwards, such that:

 *(dest-1) == *(end-1)
 *(dest-2) == *(end-2)
 *(dest-3) == *(end-3)
 ...
 *(dest-N) == *(end-N)          

The following code uses copy_backward() to copy 10 integers into the end of an empty vector:

 vector<int> from_vector;
 for( int i = 0; i < 10; i++ ) {
   from_vector.push_back( i );
 }              

 vector<int> to_vector(15);               

 copy_backward( from_vector.begin(), from_vector.end(), to_vector.end() );              

 cout << "to_vector contains: ";
 for( unsigned int i = 0; i < to_vector.size(); i++ ) {
   cout << to_vector[i] << " ";
 }
 cout << endl;            

The above code produces the following output:

 to_vector contains: 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9              

  #include <algorithm>
  iterator copy_n( iterator from, size_t num, iterator to ); 

The copy_n() function copies num elements starting at from to the destination pointed at by to. To put it another way, copy_n() performs num assignments and duplicates a subrange.

The return value of copy_n() is an iterator that points to the last element that was copied, i.e. (to + num).

This function runs in linear time.

  #include <algorithm>
  size_t count( iterator start, iterator end, const TYPE& val );

The count() function returns the number of elements between start and end that match val.

For example, the following code uses count() to determine how many integers in a vector match a target value:

 vector<int> v;
 for( int i = 0; i < 10; i++ ) {
   v.push_back( i );
 }              

 int target_value = 3;
 int num_items = count( v.begin(), v.end(), target_value );             

 cout << "v contains " << num_items << " items matching " << target_value << endl;            

The above code displays the following output:

 v contains 1 items matching 3          

  #include <algorithm>
  size_t count_if( iterator start, iterator end, UnaryPred p );

The count_if() function returns the number of elements between start and end for which the predicate p returns true.

For example, the following code uses count_if() with a predicate that returns true for the integer 3 to count the number of items in an array that are equal to 3:

 int nums[] = { 0, 1, 2, 3, 4, 5, 9, 3, 13 };
 int start = 0;
 int end = 9;           

 int target_value = 3;
 int num_items = count_if( nums+start,
                    nums+end,
                    bind2nd(equal_to<int>(), target_value) );             

 cout << "nums[] contains " << num_items << " items matching " << target_value << endl;               

When run, the above code displays the following output:

 nums[] contains 2 items matching 3             

  #include <algorithm>
  bool equal( iterator start1, iterator end1, iterator start2 );
  bool equal( iterator start1, iterator end1, iterator start2, BinPred p );

The equal() function returns true if the elements in two ranges are the same. The first range of elements are those between start1 and end1. The second range of elements has the same size as the first range but starts at start2.

If the binary predicate p is specified, then it is used instead of == to compare each pair of elements.

For example, the following code uses equal() to compare two vectors of integers:

 vector<int> v1;
 for( int i = 0; i < 10; i++ ) {
   v1.push_back( i );
 }              

 vector<int> v2;
 for( int i = 0; i < 10; i++ ) {
   v2.push_back( i );
 }              

 if( equal( v1.begin(), v1.end(), v2.begin() ) ) {
   cout << "v1 and v2 are equal" << endl;
 } else {
   cout << "v1 and v2 are NOT equal" << endl;
 }              

  #include <algorithm>
  pair<iterator,iterator> equal_range( iterator first, iterator last, const TYPE& val );
  pair<iterator,iterator> equal_range( iterator first, iterator last, const TYPE& val, CompFn comp );

The equal_range() function returns the range of elements between first and last that are equal to val. This function assumes that the elements between first and last are in order according to comp, if it is specified, or the < operator otherwise.

equal_range() can be thought of as a combination of the lower_bound() and `upper_bound1`() functions, since the first of the pair of iterators that it returns is what lower_bound() returns and the second iterator in the pair is what `upper_bound1`() returns.

For example, the following code uses equal_range() to determine all of the possible places that the number 8 can be inserted into an ordered vector of integers such that the existing ordering is preserved:

 vector<int> nums;
 nums.push_back( -242 );
 nums.push_back( -1 );
 nums.push_back( 0 );
 nums.push_back( 5 );
 nums.push_back( 8 );
 nums.push_back( 8 );
 nums.push_back( 11 );          

 pair<vector<int>::iterator, vector<int>::iterator> result;
 int new_val = 8;               

 result = equal_range( nums.begin(), nums.end(), new_val );             

 cout << "The first place that " << new_val << " could be inserted is before "
      << *result.first << ", and the last place that it could be inserted is before "
      << *result.second << endl;            

The above code produces the following output:

 The first place that 8 could be inserted is before 8,
 and the last place that it could be inserted is before 11              

  #include <algorithm>
  #include <algorithm>
  void fill( iterator start, iterator end, const TYPE& val );

The function fill() assigns val to all of the elements between start and end.

For example, the following code uses fill() to set all of the elements of a vector of integers to -1:

 vector<int> v1;
 for( int i = 0; i < 10; i++ ) {
   v1.push_back( i );
 }              

 cout << "Before, v1 is: ";
 for( unsigned int i = 0; i < v1.size(); i++ ) {
   cout << v1[i] << " ";
 }
 cout << endl;            

 fill( v1.begin(), v1.end(), -1 );              

 cout << "After, v1 is: ";
 for( unsigned int i = 0; i < v1.size(); i++ ) {
   cout << v1[i] << " ";
 }
 cout << endl;            

When run, the above code displays:

 Before, v1 is: 0 1 2 3 4 5 6 7 8 9
 After, v1 is: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1            

  #include <algorithm>
  #include <algorithm>
  iterator fill_n( iterator start, size_t n, const TYPE& val );

The fill_n() function is similar to (C++ I/O) fill(). Instead of assigning val to a range of elements, however, fill_n() assigns val to the first n elements starting at start.

For example, the following code uses fill_n() to assign -1 to the first half of a vector of integers:

 vector<int> v1;
 for( int i = 0; i < 10; i++ ) {
   v1.push_back( i );
 }              

 cout << "Before, v1 is: ";
 for( unsigned int i = 0; i < v1.size(); i++ ) {
   cout << v1[i] << " ";
 }
 cout << endl;            

 fill_n( v1.begin(), v1.size()/2, -1 );         

 cout << "After, v1 is: ";
 for( unsigned int i = 0; i < v1.size(); i++ ) {
   cout << v1[i] << " ";
 }
 cout << endl;            

When run, this code displays:

 Before, v1 is: 0 1 2 3 4 5 6 7 8 9
 After, v1 is: -1 -1 -1 -1 -1 5 6 7 8 9         

  #include <algorithm>
  iterator find( iterator start, iterator end, const TYPE& val );

The find() algorithm looks for an element matching val between start and end. If an element matching val is found, the return value is an iterator that points to that element. Otherwise, the return value is an iterator that points to end.

For example, the following code uses find() to search a vector of integers for the number 3:

 int num_to_find = 3;           

 vector<int> v1;
 for( int i = 0; i < 10; i++ ) {
   v1.push_back(i);
 }              

 vector<int>::iterator result;
 result = find( v1.begin(), v1.end(), num_to_find );            

 if( result == v1.end() ) {
   cout << "Did not find any element matching " << num_to_find << endl;
 }              

 else {
   cout << "Found a matching element: " << *result << endl;
 }              

In the next example, shown below, the find() function is used on an array of integers. This example shows how the C++ Algorithms can be used to manipulate arrays and pointers in the same manner that they manipulate containers and iterators:

 int nums[] = { 3, 1, 4, 1, 5, 9 };

 int num_to_find = 5;
 int start = 0;
 int end = 2;
 int* result = find( nums + start, nums + end, num_to_find );                

 if( result == nums + end ) {
   cout << "Did not find any number matching " << num_to_find << endl;
 } else {
   cout << "Found a matching number: " << *result << endl;
 }              

  #include <algorithm>
  iterator find_end( iterator start, iterator end, iterator seq_start, iterator seq_end );
  iterator find_end( iterator start, iterator end, iterator seq_start, iterator seq_end, BinPred bp );

The find_end() function searches for the sequence of elements denoted by seq_start and seq_end. If such a sequence if found between start and end, an iterator to the first element of the last found sequence is returned. If no such sequence is found, an iterator pointing to end is returned.

If the binary predicate bp is specified, then it is used to when elements match.

For example, the following code uses find_end() to search for two different sequences of numbers. The the first chunk of code, the last occurence of "1 2 3" is found. In the second chunk of code, the sequence that is being searched for is not found:

 int nums[] = { 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4 };
 int* result;
 int start = 0;
 int end = 11;          

 int target1[] = { 1, 2, 3 };
 result = find_end( nums + start, nums + end, target1 + 0, target1 + 2 );
 if( *result == nums[end] ) {
   cout << "Did not find any subsequence matching { 1, 2, 3 }" << endl;
 } else {
   cout << "The last matching subsequence is at: " << *result << endl;
 }              

 int target2[] = { 3, 2, 3 };
 result = find_end( nums + start, nums + end, target2 + 0, target2 + 2 );
 if( *result == nums[end] ) {
   cout << "Did not find any subsequence matching { 3, 2, 3 }" << endl;
 } else {
   cout << "The last matching subsequence is at: " << *result << endl;
 }              

  #include <algorithm>
  iterator find_first_of( iterator start, iterator end, iterator find_start, iterator find_end );
  iterator find_first_of( iterator start, iterator end, iterator find_start, iterator find_end, BinPred bp );

The find_first_of() function searches for the first occurence of any element between find_start and find_end. The data that are searched are those between start and end.

If any element between find_start and find_end is found, an iterator pointing to that element is returned. Otherwise, an iterator pointing to end is returned.

For example, the following code searches for a 9, 4, or 7 in an array of integers:

 int nums[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 int* result;
 int start = 0;
 int end = 10;          

 int targets[] = { 9, 4, 7 };
 result = find_first_of( nums + start, nums + end, targets + 0, targets + 2 );
 if( *result == nums[end] ) {
   cout << "Did not find any of { 9, 4, 7 }" << endl;
 } else {
   cout << "Found a matching target: " << *result << endl;
 }              

  #include <algorithm>
  iterator find_if( iterator start, iterator end, UnPred up );

The find_if() function searches for the first element between start and end for which the unary predicate up returns true.

If such an element is found, an iterator pointing to that element is returned. Otherwise, an iterator pointing to end is returned.

For example, the following code uses find_if() and a "greater-than-zero" unary predicate to the first positive, non-zero number in a list of numbers:

 int nums[] = { 0, -1, -2, -3, -4, 342, -5 };
 int* result;
 int start = 0;
 int end = 7;           

 result = find_if( nums + start, nums + end, bind2nd(greater<int>(), 0));
 if( *result == nums[end] ) {
   cout << "Did not find any number greater than zero" << endl;
 } else {
   cout << "Found a positive non-zero number: " << *result << endl;
 }              

  #include <algorithm>
  UnaryFunction for_each( iterator start, iterator end, UnaryFunction f );

The for_each() algorithm applies the function f to each of the elements between start and end. The return value of for_each() is f.

For example, the following code snippets define a unary function then use it to increment all of the elements of an array:

 template<class TYPE> struct increment : public unary_function<TYPE, void> {
   void operator() (TYPE& x) {
     x++;
   }
 };             

 ...            

 int nums[] = {3, 4, 2, 9, 15, 267};
 const int N = 6;               

 cout << "Before, nums[] is: ";
 for( int i = 0; i < N; i++ ) {
   cout << nums[i] << " ";
 }
 cout << endl;            

 for_each( nums, nums + N, increment<int>() );            

 cout << "After, nums[] is: ";
 for( int i = 0; i < N; i++ ) {
   cout << nums[i] << " ";
 }
 cout << endl;            

The above code displays the following output:

 Before, nums[] is: 3 4 2 9 15 267
 After, nums[] is: 4 5 3 10 16 268              

  #include <algorithm>
  void generate( iterator start, iterator end, Generator g );

The generate() function runs the Generator function object g a number of times, saving the result of each execution in the range [start,end).

  #include <algorithm>
  iterator generate_n( iterator result, size_t num, Generator g );

The generate_n() function runs the Generator function object g num times, saving the result of each execution in result, (result+1), etc.

  #include <algorithm>
  bool includes( iterator start1, iterator end1, iterator start2, iterator end2 );
  bool includes( iterator start1, iterator end1, iterator start2, iterator end2, StrictWeakOrdering cmp );

The includes() algorithm returns true if every element in [start2,end2) is also in [start1,end1). Both of the given ranges must be sorted in ascending order.

By default, the < operator is used to compare elements. If the strict weak ordering function object cmp is given, then it is used instead.

includes() runs in linear time.

  #include <numeric>
  TYPE inner_product( iterator start1, iterator end1, iterator start2, TYPE val );
  TYPE inner_product( iterator start1, iterator end1, iterator start2, TYPE val, BinaryFunction f1, BinaryFunction f2 );

The inner_product() function computes the inner product of [start1,end1) and a range of the same size starting at start2.

inner_product() runs in linear time.

  #include <algorithm>
  inline void inplace_merge( iterator start, iterator middle, iterator end );
  inline void inplace_merge( iterator start, iterator middle, iterator end, StrictWeakOrdering cmp );

The inplace_merge() function is similar to the merge() function, but instead of creating a new sorted range of elements, inplace_merge() alters the existing ranges to perform the merge in-place.

  #include <numeric>
  void iota( iterator start, iterator end, TYPE value );

The iota() algorithm assigns value to the first element in the range [start,end), value+1 to the second element, and so on.

iota() runs in linear time.

  #include <algorithm>
  bool is_heap( iterator start, iterator end );
  bool is_heap( iterator start, iterator end, StrictWeakOrdering cmp );

The is_heap() function returns true if the given range [start,end) is a heap.

If the strict weak ordering comparison function object cmp is given, then it is used instead of the < operator to compare elements.

is_heap() runs in linear time.

  #include <algorithm>
  bool is_sorted( iterator start, iterator end );
  bool is_sorted( iterator start, iterator end, StrictWeakOrdering cmp );

The is_sorted() algorithm returns true if the elements in the range [start,end) are sorted in ascending order.

By default, the < operator is used to compare elements. If the strict weak order function object cmp is given, then it is used instead.

is_sorted() runs in linear time.

  #include <algorithm>
  inline void iter_swap( iterator a, iterator b );

A call to iter_swap() exchanges the values of two elements exactly as a call to

 swap( *a, *b );                

would.

  #include <algorithm>
  bool lexicographical_compare( iterator start1, iterator end1, iterator start2, iterator end2 );
  bool lexicographical_compare( iterator start1, iterator end1, iterator start2, iterator end2, BinPred p );

The lexicographical_compare() function returns true if the range of elements [start1,end1) is lexicographically less than the range of elements [start2,end2).

If you're confused about what lexicographic means, it might help to know that dictionaries are ordered lexicographically.

lexicographical_compare() runs in linear time.

  #include <algorithm>
  int lexicographical_compare_3way( iterator start1, iterator end1, iterator start2, iterator end2 );

The lexicographical_compare_3way() function compares the first range, defined by [start1,end1) to the second range, defined by [start2,end2).

If the first range is lexicographically less than the second range, this function returns a negative number. If the first range is lexicographically greater than the second, a positive number is returned. Zero is returned if neither range is lexicographically greater than the other.

lexicographical_compare_3way() runs in linear time.

  #include <algorithm>
  iterator lower_bound( iterator first, iterator last,  const TYPE& val );
  iterator lower_bound( iterator first, iterator last, const TYPE& val, CompFn f );

The lower_bound() function is a type of binary_search(). This function searches for the first place that val can be inserted into the ordered range defined by first and last that will not mess up the existing ordering.

The return value of lower_bound() is an iterator that points to the location where val can be safely inserted. Unless the comparison function f is specified, the < operator is used for ordering.

For example, the following code uses lower_bound() to insert the number 7 into an ordered vector of integers:

 vector<int> nums;
 nums.push_back( -242 );
 nums.push_back( -1 );
 nums.push_back( 0 );
 nums.push_back( 5 );
 nums.push_back( 8 );
 nums.push_back( 8 );
 nums.push_back( 11 );          

 cout << "Before nums is: ";
 for( unsigned int i = 0; i < nums.size(); i++ ) {
   cout << nums[i] << " ";
 }
 cout << endl;            

 vector<int>::iterator result;
 int new_val = 7;               

 result = lower_bound( nums.begin(), nums.end(), new_val );             

 nums.insert( result, new_val );                

 cout << "After, nums is: ";
 for( unsigned int i = 0; i < nums.size(); i++ ) {
   cout << nums[i] << " ";
 }
 cout << endl;            

The above code produces the following output:

 Before nums is: -242 -1 0 5 8 8 11
 After, nums is: -242 -1 0 5 7 8 8 11           

  #include <algorithm>
  void make_heap( iterator start, iterator end );
  void make_heap( iterator start, iterator end, StrictWeakOrdering cmp );

The make_heap() function turns the given range of elements [start,end) into a heap.

If the strict weak ordering comparison function object cmp is given, then it is used instead of the < operator to compare elements.

make_heap() runs in linear time.

  #include <algorithm>
  const TYPE& max( const TYPE& x, const TYPE& y );
  const TYPE& max( const TYPE& x, const TYPE& y, BinPred p );

The max() function returns the greater of x and y.

If the binary predicate p is given, then it will be used instead of the < operator to compare the two elements.

 cout << "Max of 1 and 9999 is " << max( 1, 9999) << endl;
 cout << "Max of 'a' and 'b' is " << max( 'a', 'b') << endl;
 cout << "Max of 3.14159 and 2.71828 is " << max( 3.14159, 2.71828) << endl;                

 Max of 1 and 9999 is 9999
 Max of 'a' and 'b' is b
 Max of 3.14159 and 2.71828 is 3.14159          

  #include <algorithm>
  iterator max_element( iterator start, iterator end );
  iterator max_element( iterator start, iterator end, BinPred p );

The max_element() function returns an iterator to the largest element in the range [start,end).

If the binary predicate p is given, then it will be used instead of the < operator to determine the largest element.

 int array[] = { 3, 1, 4, 1, 5, 9 };
 unsigned int array_size = 6;
 cout << "Max element in array is " << *max_element( array, array+array_size) << endl;              

 vector<char> v;
 v.push_back('a'); v.push_back('b'); v.push_back('c'); v.push_back('d');
 cout << "Max element in the vector v is " << *max_element( v.begin(), v.end() ) << endl;           

 Max element in array is 9
 Max element in the vector v is d               

  #include <algorithm>
  iterator merge( iterator start1, iterator end1, iterator start2, iterator end2, iterator result );
  iterator merge( iterator start1, iterator end1, iterator start2, iterator end2, iterator result, StrictWeakOrdering cmp );

The merge() function combines two sorted ranges [start1,end1) and [start2,end2) into a single sorted range, stored starting at result. The return value of this function is an iterator to the end of the merged range.

If the strict weak ordering function object cmp is given, then it is used in place of the < operator to perform comparisons between elements.

merge() runs in linear time.

  #include <algorithm>
  const TYPE& min( const TYPE& x, const TYPE& y );
  const TYPE& min( const TYPE& x, const TYPE& y, BinPred p );

The min() function, unsurprisingly, returns the smaller of x and y.

By default, the < operator is used to compare the two elements. If the binary predicate p is given, it will be used instead.

  #include <algorithm>
  iterator min_element( iterator start, iterator end );
  iterator min_element( iterator start, iterator end, BinPred p );

The min_element() function returns an iterator to the smallest element in the range [start,end).

If the binary predicate p is given, then it will be used instead of the < operator to determine the smallest element.

  #include <algorithm>
  pair <iterator1,iterator2> mismatch( iterator start1, iterator end1, iterator start2 );
  pair <iterator1,iterator2> mismatch( iterator start1, iterator end1, iterator start2, BinPred p );

The mismatch() function compares the elements in the range defined by [start1,end1) to the elements in a range of the same size starting at start2. The return value of mismatch() is the first location where the two ranges differ.

If the optional binary predicate p is given, then it is used to compare elements from the two ranges.

The mismatch() algorithm runs in linear time.

  #include <algorithm>
  bool next_permutation( iterator start, iterator end );
  bool next_permutation( iterator start, iterator end, StrictWeakOrdering cmp );

The next_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically greater permutation of elements. If it succeeds, it returns true, otherwise, it returns false.

If a strict weak ordering function object cmp is provided, it is used in lieu of the < operator when comparing elements.

  #include <algorithm>
  void nth_element( iterator start, iterator middle, iterator end );
  void nth_element( iterator start, iterator middle, iterator end, StrictWeakOrdering cmp );

The nth_element() function semi-sorts the range of elements defined by [start,end). It puts the element that middle points to in the place that it would be if the entire range was sorted, and it makes sure that none of the elements before that element are greater than any of the elements that come after that element.

nth_element() runs in linear time on average.

  #include <algorithm>
  void partial_sort( iterator start, iterator middle, iterator end );
  void partial_sort( iterator start, iterator middle, iterator end, StrictWeakOrdering cmp );

The partial_sort() function arranges the first N elements of the range [start,end) in ascending order. N is defined as the number of elements between start and middle.

By default, the < operator is used to compare two elements. If the strict weak ordering comparison function cmp is given, it is used instead.

  #include <algorithm>
  iterator partial_sort_copy( iterator start, iterator end, iterator result_start, iterator result_end );
  iterator partial_sort_copy( iterator start, iterator end, iterator result_start, iterator result_end, StrictWeakOrdering cmp );

The partial_sort_copy() algorithm behaves like partial_sort(), except that instead of partially sorting the range in-place, a copy of the range is created and the sorting takes place in the copy. The initial range is defined by [start,end) and the location of the copy is defined by [result_start,result_end).

partial_sort_copy() returns an iterator to the end of the copied, partially-sorted range of elements.

  #include <numeric>
  iterator partial_sum( iterator start, iterator end, iterator result );
  iterator partial_sum( iterator start, iterator end, iterator result, BinOp p );

The partial_sum() function calculates the partial sum of a range defined by [start,end), storing the output at result.

• start is assigned to *result, the sum of *start and *(start + 1) is assigned to *(result + 1), etc.

partial_sum() runs in linear time.

  #include <algorithm>
  iterator partition( iterator start, iterator end, Predicate p );

The partition() algorithm re-orders the elements in [start,end) such that the elements for which the predicate p returns true come before the elements for which p returns false.

In other words, partition() uses p to divide the elements into two groups.

The return value of partition() is an iterator to the first element for which p returns false.

parition() runs in linear time.

  #include <algorithm>
  void pop_heap( iterator start, iterator end );
  void pop_heap( iterator start, iterator end, StrictWeakOrdering cmp );

The pop_heap() function removes the larges element (defined as the element at the front of the heap) from the given heap.

If the strict weak ordering comparison function object cmp is given, then it is used instead of the < operator to compare elements.

pop_heap() runs in logarithmic time.

  #include <numeric>
  inline TYPE power( TYPE x, int N );

The power() function returns x raised to the power of N, where N is some non-negative integer.

  #include <algorithm>
  bool prev_permutation( iterator start, iterator end );
  bool prev_permutation( iterator start, iterator end, StrictWeakOrdering cmp );

The prev_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically smaller permutation of elements. If it succeeds, it returns true, otherwise, it returns false.

If a strict weak ordering function object cmp is provided, it is used instead of the < operator when comparing elements.

  #include <algorithm>
  void push_heap( iterator start, iterator end );
  void push_heap( iterator start, iterator end, StrictWeakOrdering cmp );

The push_heap() function adds an element (defined as the last element before end) to a heap (defined as the range of elements between [start,''end-1).

If the strict weak ordering comparison function object cmp is given, then it is used instead of the < operator to compare elements.

push_heap() runs in logarithmic time.

  #include <algorithm>
  iterator random_sample( iterator start1, iterator end1, iterator start2, iterator end2 );
  iterator random_sample( iterator start1, iterator end1, iterator start2, iterator end2, RandomNumberGenerator& rnd );

The random_sample() algorithm randomly copies elements from [start1,end1) to [start2,end2). Elements are chosen with uniform probability and elements from the input range will appear at most once in the output range.

If a random number generator function object rnd is supplied, then it will be used instead of an internal random number generator.

The return value of random_sample() is an iterator to the end of the output range.

random_sample() runs in linear time.

  #include <algorithm>
  iterator random_sample_n( iterator start, iterator end, iterator result, size_t N );
  iterator random_sample_n( iterator start, iterator end, iterator result, size_t N, RandomNumberGenerator& rnd );

The random_sample_n() algorithm randomly copies N elements from [start,end) to result. Elements are chosen with uniform probability and elements from the input range will appear at most once in the output range. Element order is preserved from the input range to the output range.

If a random number generator function object rnd is supplied, then it will be used instead of an internal random number generator.

The return value of random_sample_n() is an iterator to the end of the output range.

random_sample_n() runs in linear time.

  #include <algorithm>
  void random_shuffle( iterator start, iterator end );
  void random_shuffle( iterator start, iterator end, RandomNumberGenerator& rnd );

The random_shuffle() function randomly re-orders the elements in the range [start,end). If a random number generator function object rnd is supplied, it will be used instead of an internal random nunber generator.

  #include <algorithm>
  iterator remove( iterator start, iterator end, const TYPE& val );

The remove() algorithm removes all of the elements in the range [start,end) that are equal to val.

The return value of this function is an iterator to the last element of the new sequence that should contain no elements equal to val.

The remove() function runs in linear time.

  #include <algorithm>
  iterator remove_copy( iterator start, iterator end, iterator result, const TYPE& val );

The remove_copy() algorithm copies the range [start,end) to result but omits any elements that are equal to val.

remove_copy() returns an iterator to the end of the new range, and runs in linear time.

  #include <algorithm>
  iterator remove_copy_if( iterator start, iterator end, iterator result, Predicate p );

The remove_copy_if() function copies the range of elements [start,end) to result, omitting any elements for which the predicate function p returns true.

The return value of remove_copy_if() is an iterator the end of the new range.

remove_copy_if() runs in linear time.

  #include <algorithm>
  iterator remove_if( iterator start, iterator end, Predicate p );

The remove_if() function removes all elements in the range [start,end) for which the predicate p returns true.

The return value of this function is an iterator to the last element of the pruned range.

remove_if() runs in linear time.

  #include <algorithm>
  void replace( iterator start, iterator end, const TYPE& old_value, const TYPE& new_value );

The replace() function sets every element in the range [start,end) that is equal to old_value to have new_value instead.

replace() runs in linear time.

  #include <algorithm>
  iterator replace_copy( iterator start, iterator end, iterator result, const TYPE& old_value, const TYPE& new_value );

The replace_copy() function copies the elements in the range [start,end) to the destination result. Any elements in the range that are equal to old_value are replaced with new_value.

  #include <algorithm>
  iterator replace_copy_if( iterator start, iterator end, iterator result, Predicate p, const TYPE& new_value );

The replace_copy_if() function copies the elements in the range [start,end) to the destination result. Any elements for which the predicate p is true are replaced with new_value.

  #include <algorithm>
  void replace_if( iterator start, iterator end, Predicate p, const TYPE& new_value );

The replace_if() function assigns every element in the range [start,end) for which the predicate function p returns true the value of new_value.

This function runs in linear time.

  #include <algorithm>
  void reverse( iterator start, iterator end );

The reverse() algorithm reverses the order of elements in the range [start,end).

  #include <algorithm>
  iterator reverse_copy( iterator start, iterator end, iterator result );

The reverse_copy() algorithm copies the elements in the range [start,end) to result such that the elements in the new range are in reverse order.

The return value of the reverse_copy() function is an iterator the end of the new range.

  #include <algorithm>
  inline iterator rotate( iterator start, iterator middle, iterator end );

The rotate() algorithm moves the elements in the range [start,end) such that the middle element is now where start used to be, (middle+1) is now at (start+1), etc.

The return value of rotate() is an iterator to start + (end-middle).

rotate() runs in linear time.

  #include <algorithm>
  iterator rotate_copy( iterator start, iterator middle, iterator end, iterator result );

The rotate_copy() algorithm is similar to the rotate() algorithm, except that the range of elements is copied to result before being rotated.

  #include <algorithm>
  iterator search( iterator start1, iterator end1, iterator start2, iterator end2 );
  iterator search( iterator start1, iterator end1, iterator start2, iterator end2, BinPred p );

The search() algorithm looks for the elements [start2,end2) in the range [start1,end1). If the optional binary predicate p is provided, then it is used to perform comparisons between elements.

If search() finds a matching subrange, then it returns an iterator to the beginning of that matching subrange. If no match is found, an iterator pointing to end1 is returned.

In the worst case, search() runs in quadratic time, on average, it runs in linear time.

  #include <algorithm>
  iterator search_n( iterator start, iterator end, size_t num, const TYPE& val );
  iterator search_n( iterator start, iterator end, size_t num, const TYPE& val, BinPred p );

The search_n() function looks for num occurances of val in the range [start,end).

If num consecutive copies of val are found, search_n() returns an iterator to the beginning of that sequence. Otherwise it returns an iterator to end.

If the optional binary predicate p is given, then it is used to perform comparisons between elements.

This function runs in linear time.

  #include <algorithm>
  iterator set_difference( iterator start1, iterator end1, iterator start2, iterator end2, iterator result );
  iterator set_difference( iterator start1, iterator end1, iterator start2, iterator end2, iterator result, StrictWeakOrdering cmp );

The set_difference() algorithm computes the difference between two sets defined by [start1,end1) and [start2,end2) and stores the difference starting at result.

Both of the sets, given as ranges, must be sorted in ascending order.

The return value of set_difference() is an iterator to the end of the result range.

If the strict weak ordering comparison function object cmp is not specified, set_difference() will use the < operator to compare elements.

  #include <algorithm>
  iterator set_intersection( iterator start1, iterator end1, iterator start2, iterator end2, iterator result );
  iterator set_intersection( iterator start1, iterator end1, iterator start2, iterator end2, iterator result, StrictWeakOrdering cmp );

The set_intersection() algorithm computes the intersection of the two sets defined by [start1,end1) and [start2,end2) and stores the intersection starting at result.

Both of the sets, given as ranges, must be sorted in ascending order.

The return value of set_intersection() is an iterator to the end of the intersection range.

If the strict weak ordering comparison function object cmp is not specified, set_intersection() will use the < operator to compare elements.

  #include <algorithm>
  iterator set_symmetric_difference( iterator start1, iterator end1, iterator start2, iterator end2, iterator result );
  iterator set_symmetric_difference( iterator start1, iterator end1, iterator start2, iterator end2, iterator result, StrictWeakOrdering cmp );

The set_symmetric_difference() algorithm computes the symmetric difference of the two sets defined by [start1,end1) and [start2,end2) and stores the difference starting at result.

Both of the sets, given as ranges, must be sorted in ascending order.

The return value of set_symmetric_difference() is an iterator to the end of the result range.

If the strict weak ordering comparison function object cmp is not specified, set_symmetric_difference() will use the < operator to compare elements.

  #include <algorithm>
  iterator set_union( iterator start1, iterator end1, iterator start2, iterator end2, iterator result );
  iterator set_union( iterator start1, iterator end1, iterator start2, iterator end2, iterator result, StrictWeakOrdering cmp );

The set_union() algorithm computes the union of the two ranges [start1,end1) and [start2,end2) and stores it starting at result.

The return value of set_union() is an iterator to the end of the union range.

set_union() runs in linear time.

  #include <algorithm>
  void sort( iterator start, iterator end );
  void sort( iterator start, iterator end, StrictWeakOrdering cmp );

The sort() algorithm sorts the elements in the range [start,end) into ascending order. If two elements are equal, there is no guarantee what order they will be in.

If the strict weak ordering function object cmp is given, then it will be used to compare two objects instead of the < operator.

The algorithm behind sort() is the introsort algorithm. sort() runs in O(N log(N)) time (average and worst case) which is faster than polynomial time but slower than linear time.

 vector<int> v;
 v.push_back( 23 );
 v.push_back( -1 );
 v.push_back( 9999 );
 v.push_back( 0 );
 v.push_back( 4 );              

 cout << "Before sorting: ";
 for( unsigned int i = 0; i < v.size(); i++ ) {
   cout << v[i] << " ";
 }
 cout << endl;            

 sort( v.begin(), v.end() );            

 cout << "After sorting: ";
 for( unsigned int i = 0; i < v.size(); i++ ) {
   cout << v[i] << " ";
 }
 cout << endl;            

 Before sorting: 23 -1 9999 0 4
 After sorting: -1 0 4 23 9999          

 int array[] = { 23, -1, 9999, 0, 4 };
 unsigned int array_size = 5;           

 cout << "Before sorting: ";
 for( unsigned int i = 0; i < array_size; i++ ) {
   cout << array[i] << " ";
 }
 cout << endl;            

 sort( array, array + array_size );             

 cout << "After sorting: ";
 for( unsigned int i = 0; i < array_size; i++ ) {
   cout << array[i] << " ";
 }
 cout << endl;            

 bool cmp( int a, int b ) {
   return a > b;
 }              

 ...            

 vector<int> v;
 for( int i = 0; i < 10; i++ ) {
   v.push_back(i);
 }              

 cout << "Before: ";
 for( int i = 0; i < 10; i++ ) {
   cout << v[i] << " ";
 }
 cout << endl;            

 sort( v.begin(), v.end(), cmp );               

 cout << "After: ";
 for( int i = 0; i < 10; i++ ) {
   cout << v[i] << " ";
 }
 cout << endl;            

  #include <algorithm>
  void sort_heap( iterator start, iterator end );
  void sort_heap( iterator start, iterator end, StrictWeakOrdering cmp );

The sort_heap() function turns the heap defined by [start,end) into a sorted range.

If the strict weak ordering comparison function object cmp is given, then it is used instead of the < operator to compare elements.

  #include <algorithm>
  iterator stable_partition( iterator start, iterator end, Predicate p );

The stable_partition() function behaves similarily to partition(). The difference between the two algorithms is that stable_partition() will preserve the initial ordering of the elements in the two groups.

  #include <algorithm>
  void stable_sort( iterator start, iterator end );
  void stable_sort( iterator start, iterator end, StrictWeakOrdering cmp );

The stable_sort() algorithm is like the sort() algorithm, in that it sorts a range of elements into ascending order. Unlike sort(), however, stable_sort() will preserve the original ordering of elements that are equal to eachother.

This functionality comes at a small cost, however, as stable_sort() takes a few more comparisons that sort() in the worst case: N (log N)^2 instead of N log N.

  #include <algorithm>
  void swap( Assignable& a, Assignable& b );

The swap() function swaps the values of a and b.

swap() expects that its arguments will conform to the Assignable model; that is, they should have a copy constructor and work with the = operator. This function performs one copy and two assignments.

  #include <algorithm>
  iterator swap_ranges( iterator start1, iterator end1, iterator start2 );

The swap_ranges() function exchanges the elements in the range [start1,end1) with the range of the same size starting at start2.

The return value of swap_ranges() is an iterator to start2 + (end1-start1).

  #include <algorithm>
  iterator transform( iterator start, iterator end, iterator result, UnaryFunction f );
  iterator transform( iterator start1, iterator end1, iterator start2, iterator result, BinaryFunction f );

The transform() algorithm applies the function f to some range of elements, storing the result of each application of the function in result.

The first version of the function applies f to each element in [start,end) and assigns the first output of the function to result, the second output to (result+1), etc.

The second version of the transform() works in a similar manner, except that it is given two ranges of elements and calls a binary function on a pair of elements.

  #include <algorithm>
  iterator unique( iterator start, iterator end );
  iterator unique( iterator start, iterator end, BinPred p );

The unique() algorithm removes all consecutive duplicate elements from the range [start,end). If the binary predicate p is given, then it is used to test to test two elements to see if they are duplicates.

The return value of unique() is an iterator to the end of the modified range.

unique() runs in linear time.

  #include <algorithm>
  iterator unique_copy( iterator start, iterator end, iterator result );
  iterator unique_copy( iterator start, iterator end, iterator result, BinPred p );

The unique_copy() function copies the range [start,end) to result, removing all consecutive duplicate elements. If the binary predicate p is provided, then it is used to test two elements to see if they are duplicates.

The return value of unique_copy() is an iterator to the end of the new range.

unique_copy() runs in linear time.

  #include <algorithm>
  iterator upper_bound( iterator start, iterator end, const TYPE& val );
  iterator upper_bound( iterator start, iterator end, const TYPE& val, StrictWeakOrdering cmp );

The upper_bound() algorithm searches the ordered range [start,end) for the last location that val could be inserted without disrupting the order of the range.

If the strict weak ordering function object cmp is given, it is used to compare elements instead of the < operator.

upper_bound() runs in logarithmic time.