Previous Section
 < Free Open Study > 
Next Section


Algorithms

We have said that the Standard Template Library provides containers, iterators, and generic algorithms. In computer science terminology, an algorithm is a sequence of steps that solves a problem. In contrast, the term algorithm in the STL context means something much more specific: a template function that has iterators for its parameter types.

The STL supplies a large set of generic algorithms that operate on containers, whether they are STL containers or user-defined containers. The algorithms are generic because each algorithm is templated and the arguments in a function call are iterators, not containers. Therefore, a generic algorithm may operate on any data structure that provides an iterator type that meets the iterator requirements of that algorithm. Let's look at an example.

The STL supplies a sort algorithm with the following signature (the required header file and the function prototype):

    #include <algorithm>
    template <class RandomAccessIterator>
    void sort( RandomAccessIterator first,
               RandomAccessIterator pastLast );

Given any container that supports random access iterators, the sort algorithm sorts the container elements into ascending order using the < operator. We know that the STL vector container supports random access iterators, so we could use sort as follows:

    #include <vector>      // For vector<T> class
    #include <algorithm>   // For sort() function
      
    vector<int> v;
      
    sort(v.begin(), v.end());  // Sort the entire vector

Because sort works on any container whose iterators meet its requirements, we can sort a built-in array as follows. (Recall that pointers into a built-in array meet the requirements of a random access iterator.)

    int arr[100];
      
    sort(&arr[0], &arr[100]);  // Or sort(arr, arr+100);

In this code, the call to sort passes as arguments the location of the first array element and the location of the imaginary past-the-end element (because arr[99] is the last valid array element).

Function Objects

With the STL sort algorithm in mind, what if we want to sort a container into descending rather than ascending order? The STL provides a second version of sort with the following signature:

    #include <algorithm>
    template <class RandomAccessIterator, class Compare>
    void sort( RandomAccessIterator first,
               RandomAccessIterator pastLast, Compare cmp );

Here, the third argument in a call to sort is a user-supplied comparison operation on which the sorting is based. This argument can be either the name of a function or a function object. To demonstrate the first case, we could write a greater_than function as follows:

    bool greater_than( int m, int n)
    {
      return m > n;
    }

and then use its name as an argument to the sort function so that we can sort a vector<int> container into descending order:

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

To deal with the second case, we introduce the general concept of a function object. Stated simply, a function object is a class object that acts like a function. More precisely, a function object is an object of a class that overloads the function call operator, which is (). Here is an example:

    class Double
    {
    public:
      int operator() ( int i )
      {
        return 2 * i;
      }
    };

Given class Double, we can create and use a function object f as follows:

    Double f;
    int n;

    n = f(65) ;

The function call f(65) is equivalent to f.operator() (65) and returns the result 130. Thus, although f is used as if it were the name of a function, in reality it is the name of a class object.

Now back to our sorting problem. To sort a vector<int> into descending order, we can first write the following class:

    class Greater
    {
    public:
      bool operator() ( int m, int n )
      {
        return m > n;
      }
    };

and then proceed as follows:

    Greater greater_than;        // Create a function object
                                 // named greater_than
    sort(v.begin(), v.end(), greater_than);

Of course, if we wanted to have a Greater-like class that compares float values and another that compares char values and so on, we'd have to write all these as different classes with different names. Fortunately, the STL provides a template class greater<T> that lets us supply the base type as a template parameter and keeps us from having to write our own comparison class:

    #include <functional>   // For greater<T>
      
    greater<int> greater_than;   // Create a function object
                                 // named greater_than
    sort(v.begin(), v.end(), greater_than);

Note that the template parameter in greater<T> must be a type T for which the > operator is defined.

In addition to greater<T>, the header file <functional> also defines the following template classes: less<T>, less_equal<T>, greater_equal<T>, equal_to<T>, and not_equal_to<T>. In all cases, type T must be a type for which the corresponding operator (<, <=, and so on) is defined.

Algorithm Classification

Some STL algorithms are read-only (they inspect but don't modify the items in a container), others change the values of the items, and yet others change the order of the items. The C++ Standard classifies generic algorithms into categories that are distinguished by their use.

  • Non-modifying sequence operations

  • Mutating sequence operations

  • Sorting and related operations

  • Merging

  • Set operations

  • Heap operations

  • Numeric operations

  • Complex numbers and numeric arrays

In the following sections, we focus on the first three of these categories and present only a small sample of the available algorithms. In the descriptions of these algorithms, the formal parameter lists include type names with the following meanings (where T is the type of the items to which the iterators point):

Predicate

A function or function object taking one argument of type T and returning a bool value

Compare

A function or function object taking two arguments of type T (in order to compare them) and returning a bool value

UnaryOperation

A function or function object taking one argument of type T and returning a value of type T

BinaryOperation

A function or function object taking two arguments of type T and returning a value of type T

UnaryFunction

A function or function object taking one argument of type T and returning no value

Note 

In the following descriptions, the use of iterator arithmetic to describe positions and ranges is only for descriptive purposes. We do not intend to imply that the iterator type supports pointer arithmetic.

Non-Modifying Sequence Operations

Algorithms in this category are called non-modifying because they do not modify the container elements pointed to by the iterators.

  • Algorithm: count, count_if

  • Synopsis: Counts the number of items in a container that match a certain value or that satisfy a predicate.

  • Signatures:

          #include <algorithm>
          template<class InputIterator, class T>
          typename iterator_traits<InputIterator>::difference_type
          count( InputIterator first,
                 InputIterator pastLast,
                 const  T& value);
    
          #include <algorithm>
          template <class InputIterator, class Predicate>
          typename iterator_traits<InputIterator>::difference_type
          count_if( InputIterator first,
                    InputIterator pastLast,
                    Predicate pred):
    
  • Remarks on syntax: Conceptually, these two functions return integer values, but the int type might not be large enough to hold the result. So the return type is defined in terms of the difference between two iterator values. The keyword typename tells the compiler that what follows is the name of a type. iterator_traits is a struct that contains typedef statements for difference_type and other identifiers. The type difference_type is ultimately typedef'ed to ptrdiff_t, which is the integer type of the difference between two pointer values.

  • Requirement: For the count algorithm, T must be a type for which the == operator is defined.

  • Description: Each algorithm steps through the iterator range [first, pastLast). The count algorithm returns the number of items in the range that match the parameter value. The count_if algorithm returns the number of items in the range that satisfy the predicate pred.

  • Complexity: Each algorithm has a run time that is linear in the length of the range and has constant space complexity.

  • Algorithm: find, find_if

  • Synopsis: Locates the first item in a subrange of a container that matches a particular value. The predicate version, find_if, locates the first item that satisfies a predicate passed to the algorithm.

  • Signatures:

          #include <algorithm>
          template <class InputIterator, class T>
          InputIterator find( InputIterator first,
                              InputIterator pastLast,
                              const T& value);
    
          #include <algorithm>
          template <class InputIterator, class Predicate>
          InputIterator find_if( InputIterator first,
                                 InputIterator pastLast,
                                 Predicate pred);
    
  • Requirement: For the find algorithm, T must be a type for which the == operator is defined.

  • Description: find searches the range [first, pastLast) for the first item that matches value. find_if searches this range for the first item that satisfies the predicate pred. Both algorithms return an iterator value pointing to the item if it was found. If the item was not found, they return the value pastLast.

  • Complexity: Each algorithm has a run time that is linear in the length of the range and requires constant space.

  • Algorithm: for_each

  • Synopsis: Applies a function to every item in a range.

  • Signature:

          #include <algorithm>
          template <class InputIterator, class UnaryFunction>
          UnaryFunction for_each( InputIterator first,
                                  InputIterator pastLast,
                                  UnaryFunction f);
    
  • Description: This algorithm applies the function f to every item in the range [first, pastLast). The return value of f, if any, is ignored. The return value of the algorithm is the value of f after it has been applied to each container item. (This return value is useful if f is a function object that has member data that it keeps track of—for example, how many times f has been called. If f has no such member data or refers to a function rather than a function object, the return value is typically ignored by the caller.)

  • Complexity: The algorithm run time is linear in the length of the iterator range. It has constant space complexity.

Mutating Sequence Operations

Algorithms in this category are described as mutating because they can change the objects pointed to by the iterators in their argument lists.

  • Algorithm: copy

  • Synopsis: Copies items from one range to another.

  • Signature:

          #include <algorithm>
          template <class InputIterator, class OutputIterator>
          OutputIterator copy( InputIterator first,
                               InputIterator pastLast,
                               OutputIterator result);
    
  • Requirement: result, the starting point of the destination range, must not be in the range [first, pastLast). Also, there must be sufficient space at the destination to hold the copied items.

  • Description: The algorithm copies items from the range [first, pastLast) into the range [result, result + (pastLast - first)), starting from first and proceeding to pastLast. The function returns an iterator value denoting the past-the-last position in the destination range—that is, the position denoted by (result + (pastLast - first)).

  • Complexity: The algorithm is linear, performing pastLast - first assignments.

  • Algorithm: fill

  • Synopsis: Sets every item in a range to a specified value.

  • Signature:

          #include <algorithm>
          template <class ForwardIterator, class T>
          void fill ( ForwardIterator first,
                      ForwardIterator pastLast,
                      const T& value );
    
  • Description: fill traverses the range [first, pastLast), assigning value to each item.

  • Complexity: The algorithm is linear in the length of the range.

  • Algorithm: replace, replace_if

  • Synopsis: replace traverses a sequence, replacing each specified value with another value. replace_if replaces values that satisfy a predicate.

  • Signatures:

          #include <algorithm>
          template <class ForwardIterator, class T>
          void replace( ForwardIterator first,
                        ForwardIterator pastLast,
                        const T& old_value,
                        const T& new_value );
    
          #include <algorithm>
          template <class ForwardIterator. class Predicate, class T>
          void replace_if( ForwardIterator first,
                           ForwardIterator pastLast,
                           Predicate pred,
                           const T& new_value );
    
  • Requirement: For the replace algorithm, T must be a type for which the == operator is defined.

  • Description: replace replaces every occurrence of old_value with new_value in the range [first, pastLast). The algorithm replace_if replaces every item that satisfies pred with new_value in the range [first, pastLast).

  • Complexity: These algorithms are linear in the length of the range.

  • Algorithm: reverse

  • Synopsis: Reverses in place the relative order of items in a range.

  • Signature:

          #include <algorithm>
          template <class BidirectionalIterator>
          void reverse( BidirectionalIterator first,
                        BidirectionalIterator pastLast );
    
  • Description: The effect of reverse is to swap the first and last items in the range [first, pastLast), then the second and next-to-last items, and so on until the middle is detected, at which point the process stops.

  • Complexity: reverse processes all items once, so the time complexity is linear in the length of the range.

  • Algorithm: transform

  • Synopsis: Applies an operation to items from one or two ranges, placing the result in another.

  • Signatures:

          #include <algorithm>
          template <class InputIterator, class OutputIterator,
                    class UnaryOperation>
          OutputIterator transform( InputIterator first,
                                    InputIterator pastLast,
                                    OutputIterator result,
                                    UnaryOperation op );
    
          #include <algorithm>
          template <class InputIterator1, class InputIterator2,
                    class OutputIterator, class BinaryOperation>
          OutputIterator transform ( InputIterator1 first1,
                                     InputIterator1 pastLast1,
                                     InputIterator2 first2,
                                     OutputIterator result,
                                     BinaryOperation binary_op );
    
  • Requirement: Unary operation op and binary operation binary_op must not have side effects.

  • Description: Applies a unary operation op to each item in the range [first, pastLast), or a binary operation binary_op to pairs of corresponding items in two ranges, [first1, pastLast1) and [first2, pastLast2), each storing the results in another sequence starting at the position denoted by result. For each version, the return value is an iterator value denoting the past-the-last position in the destination range.

  • Complexity: Each algorithm is linear. Exactly pastLast - first (or, for the second version, pastLast1 - first1) applications of either op or binary_op are made.

Sorting and Related Operations

  • Algorithm: max_element

  • Synopsis: Finds the largest item in a range.

  • Signatures:

          #include <algorithm>
          template <class ForwardIterator>
          ForwardIterator max_element(ForwardIterator first,
                                      ForwardIterator pastLast);
    
          #include <algorithm>
          template <class ForwardIterator, class Compare>
          ForwardIterator max_element(ForwardIterator first,
                                      ForwardIterator pastLast,
                                      Compare cmp);
    
  • Requirement: For the first version, the items in the container must be of a type for which the < operator is defined. For the second version, cmp must be a Boolean function or function object whose semantics are "less than."

  • Description: max_element returns an iterator value denoting the position of the largest item in the range [first, pastLast). If there are several occurrences of the largest item, the position of the first one is returned. If [first, pastLast) is an empty range, the function returns pastLast.

    The first version of max_element compares items using the < operator, and the second compares items using the function or function object cmp.

  • Complexity: Each algorithm is linear in the length of the range.

  • Algorithm: min_element

  • Synopsis: Finds the smallest item in a range.

  • Signatures:

          #include <algorithm>
          template <class ForwardIterator>
          ForwardIterator min_element(ForwardIterator first,
                                      ForwardIterator pastLast);
    
          #include <algorithm>
          template <class ForwardIterator, class Compare>
          ForwardIterator min_element(ForwardIterator first,
                                      ForwardIterator pastLast,
                                      Compare cmp);
    
  • Requirement: For the first version, the items in the container must be of a type for which the < operator is defined. For the second version, cmp must be a Boolean function or function object whose semantics are "less than."

  • Description: min_element returns an iterator value denoting the position of the smallest item in the range [first, pastLast). If there are several occurrences of the smallest item, the position of the first one is returned. If [first, pastLast) is an empty range, the function returns pastLast.

    The first version of min_element compares items using the < operator, and the second compares items using the function or function object cmp.

  • Complexity: Each algorithm is linear in the length of the range.

  • Algorithm: sort

  • Synopsis: Sorts items in a range using the quick sort. One version sorts by using the < operator, the other by using a user-supplied comparison function.

  • Signatures:

          #include <algorithm>
          template <class RandomAccessIterator>
          void sort( RandomAccessIterator first,
                     RandomAccessIterator pastLast );
    
          #include <algorithm>
          template <class RandomAccessIterator, class Compare>
          void sort( RandomAccessIterator first,
                     RandomAccessIterator pastLast, Compare cmp );
    
    
  • Requirement: For the first version, the items in the container must be of a type for which the < operator is defined. For the second version, cmp must be a Boolean function or function object whose semantics are either "strictly less than" or "strictly greater than."

  • Description: Both versions sort the items in the range [first, pastLast) into order using a recursive quick sort. The first version sorts items into ascending order. The second version sorts into either ascending or descending order, depending on the comparison function cmp.

  • Complexity: Average time complexity is O(N*log(N)), and space complexity is O(log(N)) because the routines are recursive. The worst-case time complexity is O(N'). If worst-case behavior is important, two other STL algorithms named stable_sort and partial_sort provide better worst-case guarantees, but with somewhat poorer average behavior.

We hope that this appendix has whetted your appetite for the full range of features available in the Standard Template Library. We encourage you to consult the following references for further information.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)