C++ Algorithms

A range is two iterators

The algorithms in the standard library do not take a container by name. They take a half-open range: the first iterator, then the iterator one past the last element. For a vector that pair isv.begin() and v.end(). The same functions work on an array if you pass pointers to the first element and one past the last.

Include <algorithm> for sort, find, and count. Include<numeric> for accumulate. Include <vector> when the data lives in a vector. StudyGrid compiles these examples as C++17 with g++ 13.

sort rearranges the range

sort(first, last) orders the elements from smallest to largest using <. After the call, the vector itself is changed. There is no separate sorted copy unless you make one first.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> temps = {18, 7, 21, 12, 9};
  sort(temps.begin(), temps.end());
  for (int t : temps) {
    cout << t << " ";
  }
  cout << endl;
  return 0;
}

Output is 7 9 12 18 21. begin() is the first slot. end() is not a value in the vector; it marks the stop. Every algorithm in this chapter uses that pair.

find locates one value

find(first, last, value) walks the range until it sees value. It returns an iterator to that element. If the value is missing, the return is last — for a vector, that isv.end(). Always test against end() before you dereference.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> lots = {11, 42, 8, 19, 5};
  vector<int>::iterator it = find(lots.begin(), lots.end(), 42);
  if (it != lots.end()) {
    cout << "found " << *it << endl;
  } else {
    cout << "missing" << endl;
  }
  return 0;
}

*it is the int sitting at that iterator. Change 42 to 99 and the program prints missing. find stops at the first match; it does not count the rest.

count tallies matches

count(first, last, value) returns how many times value appears. The return type is an integer count, not an iterator. Use it when you care about frequency, not position.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> rolls = {3, 1, 3, 3, 6, 3};
  int threes = count(rolls.begin(), rolls.end(), 3);
  int sixes = count(rolls.begin(), rolls.end(), 6);
  cout << "threes: " << threes << endl;
  cout << "sixes: " << sixes << endl;
  return 0;
}

Output is threes: 4 then sixes: 1. A missing value yields 0, not an error.

accumulate lives in numeric

accumulate is not in <algorithm>. Include <numeric>. The call is accumulate(first, last, start). It adds every element onto start and returns the total. For a sum of int values, start at 0.

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
  vector<int> crates = {4, 6, 5, 7};
  int total = accumulate(crates.begin(), crates.end(), 0);
  cout << "sum: " << total << endl;
  cout << "count: " << crates.size() << endl;
  return 0;
}

Output is sum: 22 and count: 4. The third argument is the seed, not an extra element. Starting at 10 would print 32. For a product, the seed is 1 and you pass a multiplying function; this chapter stays with addition.

begin and end on a vector

Write nums.begin() and nums.end() every time. Do not pass the vector itself to these four functions in C++17. A later standard adds range overloads; this tutorial stays with iterators so the same pattern works on arrays and vectors.

Write a loop only when you must

A hand-written for that finds a max or a sum is fine while you learn. Once the work is “sort this” or “how many of these”, prefer the named algorithm. The range is obvious. Off-by-one mistakes shrink.