The Standard Template Library gives you four things that work together. There are the containers that store the data, the iterators that walk over it, the algorithms that operate on it through those iterators, and the function objects that let you pass the behaviour in as a parameter. Because every container provides the same iterator interface, a single algorithm can sort a vector, a list and a deque without knowing which one it has.
This is the first lesson in the The Standard Template Library module, and the next lesson in this module is about "How Does std::vector Grow and When Should You Care?".
The four parts of the STL
The library is built around one idea. You separate what you are storing from what you want to do with it.
the part what it is
------------------- ------------------------------------------------
the containers std::vector, std::list, std::map, std::set,
std::deque, std::array and more
the iterators the uniform way to walk over a container
the algorithms std::sort, std::find, std::transform,
std::accumulate and hundreds more
the function objects classes with an operator(), so a behaviour can
be passed around like a value
And because the algorithms only know about the iterators, they work with any container that provides the right kind of iterator.
Containers hold your data
The container that you choose depends on how you access the data.
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
int main() {
std::vector<std::string> parcels = {"p-001", "p-002", "p-003"};
std::list<int> route = {4, 2, 9, 7};
std::set<int> zones = {1, 2, 3, 3, 3};
std::map<std::string, int> weights = {{"p-001", 4}, {"p-002", 11}};
std::cout << "parcels: " << parcels.size() << '\n';
std::cout << "route: " << route.size() << '\n';
std::cout << "zones: " << zones.size() << '\n';
std::cout << "weights: " << weights.size() << '\n';
return 0;
}The output shows the sizes, and the set has collapsed the repeated zone number.
parcels: 3
route: 4
zones: 3
weights: 2And the container that fits the access pattern is the one that performs best. A vector for the random access, a list for the cheap insertion in the middle, and a map for the lookup by key.
Iterators walk the containers
Every container provides .begin() and .end(), and those give back iterators. The iterator supports the asterisk to read the current element, the increment to move to the next one, and a comparison to test whether you have reached the end.
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> parcels = {"p-001", "p-002", "p-003"};
for (auto it = parcels.begin(); it != parcels.end(); ++it) {
std::cout << *it << ' ';
}
std::cout << '\n';
for (const std::string& parcel : parcels) {
std::cout << parcel << ' ';
}
std::cout << '\n';
return 0;
}Both of the loops print the same thing.
p-001 p-002 p-003
p-001 p-002 p-003And the second form is the range-based for, which is the same thing written more readably.
Algorithms work through iterators
An algorithm takes a range, which is a pair of iterators, and it does something with it.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<int> weights = {12, 4, 30, 8};
std::sort(weights.begin(), weights.end());
std::cout << "sorted: ";
for (int weight : weights) {
std::cout << weight << ' ';
}
std::cout << '\n';
auto middle = std::find(weights.begin(), weights.end(), 12);
if (middle != weights.end()) {
std::cout << "found 12 at position "
<< (middle - weights.begin()) << '\n';
}
return 0;
}The output shows the sorted weights and the position of the search.
sorted: 4 8 12 30
found 12 at position 2And notice that std::find knows nothing about the vector. It takes two iterators and it gives back an iterator, and the same call works on a list or on a set.
Function objects pass behaviour in
Some algorithms need to know how to compare or what to compute. A lambda or a function object supplies that.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> parcels = {"p-003", "p-001", "p-012"};
std::sort(parcels.begin(), parcels.end(),
[](const std::string& left, const std::string& right) {
return left.size() < right.size();
});
for (const std::string& parcel : parcels) {
std::cout << parcel << ' ';
}
std::cout << '\n';
return 0;
}The output shows the parcels sorted by the length of their identifier.
p-003 p-001 p-012Headers and namespaces
The STL lives in the std namespace and in a handful of headers.
the header what it gives you
-------------------- ---------------------------------------------
, , the containers
, ,
,
the non-member algorithms
the iterator adapters and std::back_inserter
std::function, std::bind and the wrappers
std::accumulate, std::iota and friends
And including a header gives you the declarations and not the definitions, so the compiler only pays for what you actually use.
What the STL deliberately leaves out
Two things are worth knowing before you start. First, the STL containers are not thread-safe, so sharing a vector between threads needs the external synchronisation.
Second, the standard library does not include a matrix, a graph, a date and time type or a regular expression engine in the core language. Some of those are available in the other libraries, and the dates and the times in particular have their own well-known library.
The generic algorithm pattern
The pattern to remember is this. To write an algorithm that works with any container, you write it in terms of the iterators.
#include <iostream>
#include <list>
#include <string>
#include <vector>
template <typename Container>
int count_long(const Container& container, std::size_t minimum) {
int count = 0;
for (const auto& element : container) {
if (element.size() >= minimum) {
++count;
}
}
return count;
}
int main() {
std::vector<std::string> parcels = {"p-1", "p-22", "p-333"};
std::list<std::string> route = {"r-1", "r-4444"};
std::cout << "vector: " << count_long(parcels, 4) << '\n';
std::cout << "list: " << count_long(route, 4) << '\n';
return 0;
}The output shows one template handling two different container types.
vector: 2
list: 1Quick reference
- The STL has the containers, the iterators, the algorithms and the function objects.
- The containers are chosen by the access pattern and the algorithms are chosen by the operation.
- Every container provides
.begin()and.end(), and the algorithms work on those. - The same algorithm works on any container with the right iterator category.
- The lambdas and the function objects let you pass the behaviour into an algorithm.
- Write your own algorithms in terms of the iterators, so that they work with everything.
Try it yourself: store a set of the parcel records in a std::vector, then sort them with std::sort using a custom comparator, then use std::find to locate one and std::accumulate to total a field. Next, move the same records into a std::map that is keyed by the identifier and repeat the total with a loop over the map.