Containers and Their Algorithms

Algorithms¶

In the 3rd practice session we learned about several standard template library (STL) data structures and reviewed the basic algorithms defined on them.
In this section we go through some of the more useful STL algorithms. The functions implementing these algorithms are often used together with iterators, fixed values, or functions expressing a condition on the examined elements.
Since when using iterators we frequently specify a first and last element, it is important to understand the interval on which algorithms operate.
As a general rule, the iterator marking the first element is included, while the iterator marking the last element is not processed; it merely indicates the end of traversal.
In other words: the first element is a closed interval boundary [, while the last element is an open interval boundary ).
Algorithms are available within the std namespace via including the <algorithm> header.

Iterators (supplement to earlier material)¶

We have already studied iterators earlier, but so far we have only used them to access a single element and to traverse the data stored in a container.
When using algorithms, however, we must distinguish between different types of iterators.

Some iterators only support forward movement (next element via ++ operator).
More capable iterators can also reach the previous element (backward movement via -- operator).
Even more advanced iterators support random access, meaning they can move by an arbitrary offset (random access via index operator or (it + n)).

Types of iterators and some of their properties

input iterator: can move to the next element using the ++ operator, but elements that were already passed are no longer considered valid. Suitable when the algorithm only needs to traverse the data once.
forward iterator: can move forward using ++ (like input iterators), but previously traversed elements remain valid and reusable. Used when multiple passes over the data are required.
bidirectional iterator: provides all forward iterator capabilities and can also reach the previous element using --. Supports multiple traversals and is useful when accessing elements before the current position is required.
random access iterator: supports everything previous iterator categories do, and can also reach any element directly (index operator and + operator). Useful when the algorithm needs not only sequential traversal but indexing as well.

Any type implementing the operations of one of the iterator categories is considered an iterator type and can be used with STL algorithms.

find ¶

The find algorithm searches for the element we specify. Its first two parameters expect an InputIt type, meaning an iterator that is capable of moving forward, but the algorithm will only perform a single pass over the data. The third parameter must match the type of elements stored in the container and represents the value we are searching for.
As a return value, we get an iterator pointing to the found element in the data range. If the element is not found, the algorithm returns the end iterator of the data range.
If an element may occur multiple times in the container, find returns the first occurrence it encounters during traversal.

Usage:

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

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
  int searched_value = 44; // a value of the same type that can be found in the container
  auto find_it = std::find(v_int.begin(), v_int.end(), searched_value);

  if (find_it != v_int.end()) { // did not return the end of the container
    std::cout << *find_it << " found." << std::endl;
  }
}

Kimenet

44 found.

Use with an iterator that satisfies the input-iterator requirements (pointer):

#include <iostream>
#include <algorithm>

int main() {
  const int size = 5;
  int array[size] = { 2, 4, -1, 55, 4 };
  int searched_value = 55;

  auto find_it = std::find(array, array + size, searched_value);

  if (find_it != (array + size)) { // not the value we provided as the end
    std::cout << *find_it 
              << " found. The data is accessible at this memory address: "
              << find_it << std::endl;
  }
}

Kimenet

55 found. The data is accessible at this memory address: 0xe54d9ffbdc

find_if ¶

The find_if algorithm is similar to find, but instead of providing a fixed value, we give a condition that filters the elements of the data set to determine which one meets the requirement.
So instead of searching for a specific value, we tie the search to some logical condition.
This condition can be anything; for now, let's use functions to check the condition!

The parameters of find_if are similar to those of find, but the 3rd parameter is a UnaryPredicate. An element belongs to this type if it can be invoked as a function, taking one parameter of the type stored in the data set, and returning a bool (indicating whether the predicate is true or false for the given element).

Usage:

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

bool greater_than_four(int value_under_process);

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
  auto find_it = std::find_if(v_int.begin(), v_int.end(), greater_than_four);
  if (find_it != v_int.end()) { // not the end of the container
    std::cout << *find_it << " found." << std::endl;
  }
}

bool greater_than_four(int value_under_process) {
  return value_under_process > 4;
}

Output

5 found.

Explanation:

The third parameter is the name of a function.
The algorithm knows that it should call that function for every element while traversing the container.
It returns false for the values 1 and 2, then true for 5.
At this point, the search stops, and the element is found. You can see that if multiple elements satisfy the condition, the first one encountered during traversal is returned.

count and count_if ¶

The relationship between count and count_if is similar to the relationship between find and find_if; the only difference is the algorithm executed.
They return the number of elements that satisfy the condition (either a value or a predicate).

Usage:

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

bool greater_than_four( int value_under_process );

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
  auto count_ones = std::count( v_int.begin(), v_int.end(), 1 );
  auto count_greaters = std::count_if( v_int.begin(), v_int.end(), greater_than_four );
  std::cout << "Number of ones: " << count_ones << std::endl
  << "Number of greater than four: " << count_greaters << std::endl;
}

bool greater_than_four( int value_under_process ) {
  return value_under_process > 4;
}

Kimenet

Number of ones: 2
Number of greater than four: 3

remove and remove_if ¶

Used for removing elements. There are also versions tied to a value or a predicate.

Very important: remove does not actually delete elements! remove only moves the next non-deleted element to the place of the element to be deleted, and returns the position pointing after the last non-deleted element. After that, you need to manually erase elements starting from that iterator.

Usage:

int main() {
  std::vector<int> v_int = { 1, 2, 5, 1, 4, 7, 44, 1 };
  std::cout << "Size: " << v_int.size() << std::endl;
  auto end_of_remaining_elements = std::remove(v_int.begin(), v_int.end(), 1);

  std::cout << "Size after remove: " << v_int.size() << std::endl;

  std::cout << std::endl << "Actual useful elements: ";
  for (auto it = v_int.begin(); it != end_of_remaining_elements; ++it) { std::cout << *it << " "; }
}

Output

Size: 8
Size after remove: 8

Actual useful elements: 2 5 4 7 44

Usage with manual deletion:

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

int main() {
    std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };
    auto end_of_remaining_elements = std::remove(v_int.begin(), v_int.end(), 1);

    for (auto it = v_int.begin(); it != v_int.end(); ++it) { std::cout << *it << " "; }
    std::cout << std::endl << "Actual useful elements:" << std::endl;
    for (auto it = v_int.begin(); it != end_of_remaining_elements; ++it) { std::cout << *it << " "; }
    std::cout << std::endl;

    v_int.erase(end_of_remaining_elements, v_int.end());
    std::cout << "Complete container:" << std::endl;
    for (auto it = v_int.begin(); it != v_int.end(); ++it) { std::cout << *it << " "; }
    std::cout << std::endl;
}

Output

2 5 4 7 44 44 1
Actual useful elements:
2 5 4 7 44
Complete container:
2 5 4 7 44

Lambda expression ¶

When using algorithms, sometimes we pass functions for predicates or comparisons. Often, however, we only need the procedure in a single place, so it’s unnecessary to create a full function, polluting the scope. Here, the solution is a lambda expression—a small piece of code that can be invoked as a function.

Function object¶

We have seen that classes can define operators, creating special syntax. Operators include ++, --, +=, *, /, [], and even the comma operator. In addition, the function call operator operator() can be overloaded. Objects of a type with this operator defined can be called "function-like".

Example:

#include <iostream>

class A {
  unsigned u = 0;
public:
  A() = default;
  A(unsigned u) : u(u) {}

  bool operator()(unsigned parameter) {
    std::cout << "Works." << std::endl;
    for (unsigned i = 0; i < parameter; ++i) {
      std::cout << u << std::endl;
    }
    return true;
  }
};

int main() {
  A a(42); // instantiate object
  a(3); // call object as operator() with unsigned parameter
}

Output

Works.
42
42
42

If a class instance can be called like a function, we can pass class instances to algorithms instead of regular functions.

Example:

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

class greater_than {
  int u = 0;
public:
    greater_than(int u) : u(u) {}

    bool operator()(int i) { return i > u; }
};

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };

  greater_than greater_than_four(4); // greater_than object with value 4

  auto count_ones = std::count(v_int.begin(), v_int.end(), 1);
  auto count_greaters = std::count_if(v_int.begin(), v_int.end(), greater_than_four);
  std::cout << "Number of ones: " << count_ones << std::endl
            << "Number greater than four: " << count_greaters << std::endl;
}

Output

Number of ones: 2
Number greater than four: 3

Lambda implementation¶

A lambda expression is a shortened version of the function object mentioned above, used when the type is only needed in one place for a short task.

Writing a lambda creates a class where the compiler generates only the useful parts, e.g., the function call operator.

Lambda syntax: [](){}. Details: - In [] we can capture variables from the original scope (capture). - In () we specify the lambda/function parameters. - In {} we define the lambda body to execute when called.

Example:

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

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };

  auto count_ones = std::count(v_int.begin(), v_int.end(), 1);

  auto count_greaters = std::count_if(v_int.begin(), v_int.end(), [](int i){ return i > 4; });

  std::cout << "Number of ones: " << count_ones << std::endl
            << "Number greater than four: " << count_greaters << std::endl;
}

Output

Number of ones: 2
Number greater than four: 3

If we want to use variables inside a lambda, we must capture them in []. They can be passed by value or by reference.

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

int main() {
  std::vector<int> v_int = { 1, 2, 5, 4, 7, 44, 1 };

  int greater_than_limit = 4;

  auto count_ones = std::count(v_int.begin(), v_int.end(), 1);

  // auto count_greaters = std::count_if(v_int.begin(), v_int.end(), [](int i){ return i > greater_than_limit; });
  // This code will fail to compile because the variable is not captured

  auto count_greaters = std::count_if(v_int.begin(), v_int.end(),
    [greater_than_limit](int i){ return i > greater_than_limit; }
  );
  // Here we cannot modify the variable, since it's captured by value

  auto count_next_greaters = std::count_if(v_int.begin(), v_int.end(),
    [&greater_than_limit](int i){ ++greater_than_limit; return i > greater_than_limit; }
  );
  // Here we can modify it, since it's captured by reference
  // The value changes with each comparison

  std::cout << "Number of ones: " << count_ones << std::endl
            << "Number greater than four: " << count_greaters << std::endl
            << "Modified limit: " << greater_than_limit << std::endl;
}

Output

Number of ones: 2
Number greater than four: 3
Modified limit: 11

Last update: 2025-11-27
Created: 2025-11-27

Containers and Their Algorithms

Algorithms¶

Iterators (supplement to earlier material)¶

find¶

find_if¶

count and count_if¶

remove and remove_if¶

Lambda expression¶

Function object¶

Lambda implementation¶

find ¶

find_if ¶

count and count_if ¶

remove and remove_if ¶

Lambda expression ¶