17.2. Basic Model¶

One of the primary goals of the C++ standard library is to support generic, reusable code with regular, compact interfaces. The standard library achieves these goals through separation of concerns.

Algorithms and containers interact through iterators. An algorithm does not need to know whether its iterators came from a vector, list, array, or a user-defined container; it does need the operations promised by the iterator category and the value type.

The examples on this page use the classic iterator-pair interface. C++20 also provides constrained ranges algorithms, which express many of the same requirements using concepts and accept ranges directly.

17.2.1. Basic Model in Action: find()¶

Let's suppose we need to find the first element in a container that equals a value. Specifically, we want to find a specific int in a vector.

This seems like a function we will need to use frequently, so we decide right away that it should be written as a free function:

Example

We could choose to pass an entire container of a specific type to our find function.

This first version is intentionally narrow: it searches only a mutable std::vector<int> and cannot operate on part of a vector or on another container type.

std::vector<int>::iterator
my_find(std::vector<int>& v, int x) {

and loop over the entire container:

for(auto p = v.begin(); p != v.end(); ++p) {
  if (x == *p) return p;
}

Run It

 1#include <algorithm>
 2#include <iostream>
 3#include <numeric>
 4#include <vector>
 5
 6// function to find 'x' in v
 7std::vector<int>::iterator
 8my_find(std::vector<int>& v, int x) {
 9  for(auto p = v.begin(); p != v.end(); ++p) {
10    if (x == *p) return p;
11  }
12  // did not find x
13  return v.end();
14}
15
16int main () {
17  int value = 144;
18  std::vector<int> nums(999);
19  std::iota(nums.begin(), nums.end(), -72);
20  auto it = my_find(nums, value);
21
22  if (it == nums.end()) {
23    std::cout << "Did not find " << value <<  '\n';
24  } else {
25    std::cout << "Found " << value << " at position "
26              << (std::distance(nums.begin(), it)) << '\n';
27  }
28  return 0;
29}

While this seems easier at first, this version is not nearly as generic or general-purpose as a version that accepts generic iterator types.

No way to run this function over part of a container.
Need a different function for every container type.

How do we refactor our find function to satisfy our goals?

Replace vector<int> v with a pair of iterators
Make the iterators generic types
Make the value type generic

Example

// Find the first value in [first, last) equal to value.
template <std::input_iterator InputIt, class T>
requires std::equality_comparable_with<
    std::iter_reference_t<InputIt>, const T&>
InputIt my_find(InputIt first, InputIt last, const T& value)
{
  for (; first != last; ++first) {
    if (*first == value) {
      return first;
    }
  }
  return last;
}

Run It

We can compare the custom algorithm with std::find and verify that both return the same iterator.

 1#include <algorithm>
 2#include <concepts>
 3#include <iostream>
 4#include <iterator>
 5#include <numeric>
 6#include <vector>
 7
 8// Find the first value in [first, last) equal to value.
 9template <std::input_iterator InputIt, class T>
10requires std::equality_comparable_with<
11    std::iter_reference_t<InputIt>, const T&>
12InputIt my_find(InputIt first, InputIt last, const T& value)
13{
14  for (; first != last; ++first) {
15    if (*first == value) {
16      return first;
17    }
18  }
19  return last;
20}
21
22int main () {
23  int value = 144;
24  std::vector<int> nums(999);
25  std::iota(nums.begin(), nums.end(), -72);
26
27  auto custom_it = my_find(nums.begin(), nums.end(), value);
28  auto standard_it = std::find(nums.begin(), nums.end(), value);
29
30  if (custom_it == standard_it && custom_it != nums.end()) {
31    std::cout << "Both algorithms found " << value << " at position "
32              << (std::distance(nums.begin(), custom_it)) << '\n';
33  }
34  return 0;
35}

Since it is now the same operation as std::find, we now know we no longer need it.

More to Explore