Chapter 15 - STL Algorithm Notes

Algorithms

Simple algorithms such as finding, sorting, and reversing are standard programming requirements that programmers shouldn't have to reinvent each time.

The STL supplies these functions in the form of STL algorithms that work with STL containers and iterators.

The most common algorithms used are:

• std::find - finding a particular value in a collection

• std::find_if - finding a particular value in a collection that matches a given condition

• std::reverse - reverses the elements in a collection

• std::remove_if - removes all elements from a collection that matches a given condition

• std::transform - applies a given transformation function to all elements in a container

These algorithms are template functions in the std namespace, requiring the <algorithm> header be included.

Finding

Find

template<class InputIt, class T>
InputIt find( InputIt first, InputIt last, const T& value );

• Returns an iterator to the first element in the range [first, last) that is equal to value. If no such element exists, it returns last.

#include <iostream>
#include <algorithm>
#include <vector>

int main () {
  std::vector<int> numbers = {10, 20, 30, 40, 50};

  std::vector<int>::iterator result = std::find(numbers.begin(), numbers.end(), 30);

  if (result != numbers.end()) {
      std::cout << "Found element '" << *result << "' at index: " << (result - numbers.begin()) << std::endl;
  } else {
      std::cout << "Element was not found" << std::endl;
  }
}

Find If

template<class InputIt, class UnaryPredicate>
InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );

• Returns an iterator to the first element in the range [first, last) that returns true for unary predicate p. If no such element exists, it returns last.

#include <iostream>
#include <algorithm>
#include <vector>

bool is_even(int value) {
    return (value % 2 == 0);
}

int main () {
  std::vector<int> numbers = {1, 2, 3, 4};

  std::vector<int>::iterator result = std::find_if(numbers.begin(), numbers.end(), is_even);

  if (result != numbers.end()) {
      std::cout << "Found element '" << *result << "' at index: " << (result - numbers.begin()) << std::endl;
  } else {
      std::cout << "Element was not found" << std::endl;
  }
}

Reversing

template<class BidirIt>
void reverse( BidirIt first, BidirIt last );

• Reverses the elements between the range [first, last)

#include <vector>
#include <iostream>
#include <algorithm>
 
int main()
{
    std::vector<int> numbers {1, 2, 3};
    std::reverse(numbers.begin(), numbers.end());

    for (auto num : numbers) {
        std::cout << num;
    }

    std::cout << '\n';
}

Removing

Remove

template< class ForwardIt, class T >
ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

• Transforms the range [first, last) into a range with all elements equal to value removed, and returns an iterator to the new end of the range.

#include <iostream>
#include <algorithm>
#include <vector>

int main () {
    std::vector<int> numbers = {10, 20, 30, 30, 20, 10, 10, 20};

    // Remove all 20s 
    auto new_end = std::remove(numbers.begin(), numbers.end(), 20);

    for (auto it = numbers.begin(); it != new_end; it++) {
        std::cout << *it << std::endl;
    }
}

Remove If

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, 
                           UnaryPredicate pred);

• Transforms the range [first,last) into a range with all the elements for which pred returns true removed, and returns an iterator to the new end of that range.

#include <iostream>
#include <algorithm>
#include <vector>

bool is_odd (int i) { 
    return (i % 2 == 1);
}

int main () {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  
    auto new_end = std::remove_if(numbers.begin(), numbers.end(), is_odd);
  
    for (auto it = numbers.begin(); it != new_end; it++) {
        std::cout << *it << std::endl;
    }
}

Transforming

template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform (InputIterator first1, InputIterator last1,
                          OutputIterator result, UnaryOperation op);

• Applies an operation sequentially to the elements of a range and stores the result in the range that begins at result.

#include <iostream>
#include <algorithm>
#include <vector>

int times_two(int i) { 
    return i * 2; 
}

int main () {
    std::vector<int> foo = {10, 20, 30, 40, 50};
    std::vector<int> bar;
  
    // allocate the same number of space for bar
    bar.resize(foo.size()); 
  
    // apply `times_two` to every element of `foo`, and store it in `bar` 
    std::transform(foo.begin(), foo.end(), bar.begin(), times_two); 
  
    std::cout << "foo contains:";
    for (auto num: foo) {
      std::cout << ' ' << num;
    }
    std::cout << '\n';
  
    std::cout << "bar contains:";
    for (auto num: bar)
      std::cout << ' ' << num;
    std::cout << '\n';
}