C++ STL

Containers plus algorithms

The Standard Template Library (STL) is the part of the C++ standard library built from templates. You get containers that hold values, and algorithms that work on ranges of those values. You already usedvector. This chapter places it next to map, set, sort, and find, then stops. The rest of the library has its own pages.

Include the header for the piece you need. <vector> does not pull in<algorithm>. sort lives in <algorithm>.

Containers at a glance

Pick a container by how you look things up. A vector is a list by position. A map is a dictionary by key. A set is a collection of unique values. All three grow as you insert.

There are more containers (deque, list, unordered_map). Learn these three first. The map and set chapters follow this one.

A vector is still the default list

Store a handful of numbers, print them, then hand the same range to an algorithm. Brace initialization fills the vector in one line. Range-for prints it. Nothing here is new if you finished the vector chapter; it is the input the next two listings sort and search.

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

int main() {
  vector<int> wait = {12, 3, 8, 20};
  cout << "count: " << wait.size() << endl;
  for (int minutes : wait) {
    cout << minutes << " ";
  }
  cout << endl;
  return 0;
}

Output starts with count: 4, then the four numbers in the order you wrote them.

sort rearranges a range

sort(first, last) orders the half-open range [first, last). For a whole vector that is wait.begin() to wait.end(). The default order for int is ascending.

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

int main() {
  vector<int> wait = {12, 3, 8, 20};
  sort(wait.begin(), wait.end());
  for (int minutes : wait) {
    cout << minutes << " ";
  }
  cout << endl;
  return 0;
}

Output is 3 8 12 20. sort is a function template. It works onvector<string> as well, as long as the element type can be compared.

find walks until it matches

find(first, last, value) returns an iterator to the first match, or last if nothing matches. For a vector, compare against end(). If the iterator is not end(),*it is the element.

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

int main() {
  vector<int> codes = {401, 404, 500, 200};
  auto it = find(codes.begin(), codes.end(), 404);
  if (it != codes.end()) {
    cout << "found " << *it << endl;
  } else {
    cout << "missing" << endl;
  }
  return 0;
}

Output is found 404. Change the search to 418 and the program printsmissing. auto here is the iterator type; you do not have to spell it.

begin and end are the glue

Algorithms do not take a vector by name. They take two iterators that mark a range. That is why the same sort can run on a vector today and on another container later. You will usebegin() and end() constantly. You rarely need to write a raw iterator type.

The algorithms chapter later in this track covers count and accumulate. This page only needs sort and find so the pattern is visible.

Map and set are next

A vector plus find still scans from the front. When you look up by a name or an id, amap stores the key beside the value and finds it without that scan. When you only care that a value appears once, a set keeps it unique and ordered. Those two chapters follow.