Standard Algorithms

• A set of functions in the Standard Library

  • Implement classic algorithms, such as searching and sorting
  • Plus populating, copying, reordering etc
  • Operate on containers and sequences of data

• Most are in <algorithm>

  • A few are in <numeric>

Algorithm Execution

• Function call which takes an iterator range

  • Usually corresponds to a sequence of elements in a container
  • Often begin() and end(), to process the entire container

• Iterates over the range of elements

• Performs an operation on the elements

• Returns either

  • An iterator representing an element of interest
  • The result of the operation on the elements

std::find() Algorithm

• Returns an iterator to the first matching element
• Or the end of the range if no matching element

std::string str("hello world");

// Search for the first occurence of 'o'
auto res = std::find(str.cbegin(), str.cend(), 'o');

// Did we find it?
if (res != str.cend()) {
  // Access the result
}

Pseudo code for std::find()

It_type std::find(begin, end, target) {

  for (it = begin; it != end; ++it) {
    if (*it == target) {
      return it;
    }
  }

  return end;
}

Predicates

• Many algorithms use a "predicate"
  • A function which returns bool
• std::find() uses the == operator
  • Compares each element to the target value
• The == operator for char is case sensitive
  • 'o' is not regarded as equal to 'O'

std::find_if()

• std::find_if() allow us to supply our own predicate

  • Pass a callable object as an extra argument
  • Allow us to change the definition of "equality"

• The predicate

  • Takes an argument of the element type
  • Returns a bool

• We will write a predicate which ignores case

• Use a lambda expression for the predicate

auto res = std::find_if(str.cbegin(), str.cend(), 
                        [](const char c) {
                            return ::toupper(c) == 'O'; 
                        });