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.

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:

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;
}

#include <algorithm> #include <iostream> #include <numeric> #include <vector> // function to find 'x' in v std::vector<int>::iterator find(std::vector<int>& v, int x) { for(auto p = v.begin(); p != v.end(); ++p) { if (x == *p) return p; } // did not find x return v.end(); } int main () { int value = 144; std::vector<int> nums(999); std::iota(nums.begin(), nums.end(), -72); auto it = find(nums, value); if (it == nums.end()) { std::cout << "Did not find " << value << '\n'; } else { std::cout << "Found " << value << " at position " << (std::distance(nums.begin(), it)) << '\n'; } return 0; }

See this example running step-by-step

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

#include <vector>

// 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;

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

#include <algorithm> #include <iostream> #include <numeric> #include <vector> // 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; } } return last; } int main () { int value = 144; std::vector<int> nums(999); std::iota(nums.begin(), nums.end(), -72); auto it = find(nums.begin(), nums.end(), value); if (it != nums.end()) { std::cout << "my_find() found " << value << " at position " << (std::distance(nums.begin(), it)) << '\n'; } return 0; }

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

• From cppreference.com

  • Overview of the algorithms library.

  • std::find (and find_if).