# Chapter 15 - STL Algorithm Notes

## Algorithms&#x20;

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

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

The most common algorithms used are:

* `std::find` - finding a particular value in a collection&#x20;
* `std::find_if` - finding a particular value in a collection that matches a given condition
* `std::reverse` - reverses the elements in a collection&#x20;
* `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&#x20;

These algorithms are template functions in the `std` namespace, requiring the `<algorithm>` header be included.&#x20;

### Finding&#x20;

#### Find

```cpp
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`.&#x20;

```cpp
#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

```cpp
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`.&#x20;

```cpp
#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

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

* Reverses the elements between the range `[first, last)`&#x20;

```cpp
#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&#x20;

#### Remove&#x20;

```cpp
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.&#x20;

```cpp
#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&#x20;

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

* &#x20;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.

```cpp
#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&#x20;

```cpp
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`.

```cpp
#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';
}
```
