17.2. Basic Model

One of the primary goals of the STL is avoiding repetition & using regular, compact syntax. The STL achieves these goals using separation of concerns.

STL basic model

Algorithms and containers interact through iterators.

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.

std::vector<int>::iterator 
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
 8find(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 = 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 defines a generic type and uses iterators.

  • 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

// function to find 'x' between first and last
template<class InputIt, class T>
// requires: InputIt is Convertible to T when dereferenced
//        && InputIt is EqualityComparable
//        && T is Regular
InputIt my_find(InputIt first, InputIt last, const T& value)
{
  for (; first != last; ++first) {
    if (*first == value) {
      return first;
    }

Run It

And we can prove to ourselves that we get the same results as find.

 1#include <algorithm>
 2#include <iostream>
 3#include <numeric>
 4#include <vector>
 5
 6// function to find 'x' between first and last
 7template<class InputIt, class T>
 8// requires: InputIt is Convertible to T when dereferenced
 9//        && InputIt is EqualityComparable
10//        && T is Regular
11InputIt my_find(InputIt first, InputIt last, const T& value)
12{
13  for (; first != last; ++first) {
14    if (*first == value) {
15      return first;
16    }
17  }
18  return last;
19}
20
21int main () {
22  int value = 144;
23  std::vector<int> nums(999);
24  std::iota(nums.begin(), nums.end(), -72);
25
26  auto it  = find(nums.begin(), nums.end(), value);
27
28  if (it != nums.end()) {
29    std::cout << "my_find() found " << value << " at position "
30              << (std::distance(nums.begin(), it)) << '\n';
31  }
32  return 0;
33}

And since it is arguably the same function as std::find, we now know we no longer need it.

Try this!

Change the name of the function my_find to find and change the matching name on line 24.

Does this program still compile? Explain.

Rewrite the previous example to use find.

More to Explore