The STL: containers and algorithms

In this lesson you will learn

Choose the right STL container for a task
Store and count key–value pairs with std::map
Build a collection of unique elements with std::set
Sort, search and count with iterators and <algorithm> functions

At an olympiad you need to sort a million numbers. Writing and debugging a sorting algorithm from scratch would take an hour. A C++ programmer writes a single line: std::sort(v.begin(), v.end());. This magic comes from the STL (Standard Template Library): a collection of ready-made, well-tested and very fast data structures and algorithms.

The three parts of the STL

Containers store data: std::vector, std::map, std::set and others.
Iterators mark a position in a container: v.begin() points to the first element and v.end() to the place after the last one.
Algorithms (from <algorithm>) work on a range given by iterators: they sort, search, count and transform.

Container	What it stores	Lookup speed
`std::vector<T>`	elements in order, by index	search by value: O(n)
`std::map<K, V>`	key–value pairs sorted by key	O(log n)
`std::set<T>`	sorted, unique elements	O(log n)
`std::unordered_map<K, V>`	unordered key–value pairs (hash table)	O(1) on average

The most used containers

std::map: keys and values

std::map (from <map>) is like a dictionary: every key has one value, and keys never repeat. Elements are always kept sorted by key. Below we count the votes of a class survey: count[v] creates the key with the value 0 if it is missing, and ++ increases it.

C++

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> votes = {"tea", "coffee", "tea", "juice", "tea", "coffee"};
    std::map<std::string, int> count;
    for (const std::string& v : votes) {
        count[v]++;
    }
    for (const auto& entry : count) {
        std::cout << entry.first << ": " << entry.second << '\n';
    }
    std::cout << "Kinds: " << count.size() << '\n';

    if (count.find("milk") == count.end()) {
        std::cout << "Nobody chose milk\n";
    }
    return 0;
}

Expected output

coffee: 2
juice: 1
tea: 3
Kinds: 3
Nobody chose milk

The keys come out in alphabetical order. Each element is a pair: first is the key and second the value.

std::set: unique elements

std::set (from <set>) keeps every value only once and sorts the elements automatically. If you insert a value that is already there, nothing changes. It is ideal for removing duplicates and for quickly answering “have we seen this value?”.

C++

#include <iostream>
#include <set>

int main() {
    std::set<int> numbers = {5, 1, 4, 1, 5, 9, 2, 6, 5};
    numbers.insert(3);
    numbers.insert(4);
    std::cout << "Size: " << numbers.size() << '\n';
    for (int n : numbers) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    std::cout << std::boolalpha << (numbers.count(7) > 0) << '\n';
    return 0;
}

Expected output

Size: 7
1 2 3 4 5 6 9 
false

Six of the nine numbers are unique; 3 was added, while 4 was already there.

Algorithms

<algorithm> contains dozens of ready-made functions, and they all work the same way: they take the start and the end of a range as iterators. std::find returns an iterator to the element it found, or end() if it found nothing. For summing there is std::accumulate in <numeric>.

C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> v = {42, 7, 19, 73, 7, 50};

    std::sort(v.begin(), v.end());
    for (int x : v) {
        std::cout << x << ' ';
    }
    std::cout << '\n';

    auto it = std::find(v.begin(), v.end(), 19);
    if (it != v.end()) {
        std::cout << "19 found at index " << (it - v.begin()) << '\n';
    }
    std::cout << "Sevens: " << std::count(v.begin(), v.end(), 7) << '\n';
    std::cout << "Max: " << *std::max_element(v.begin(), v.end()) << '\n';
    std::cout << "Sum: " << std::accumulate(v.begin(), v.end(), 0) << '\n';
    return 0;
}

Expected output

7 7 19 42 50 73 
19 found at index 2
Sevens: 2
Max: 73
Sum: 198

Algorithm	What it does
`std::sort(b, e)`	sorts in ascending order
`std::reverse(b, e)`	reverses the order
`std::find(b, e, x)`	returns an iterator to `x`, or `e`
`std::count(b, e, x)`	counts how many times `x` appears
`std::max_element(b, e)`	an iterator to the largest element
`std::binary_search(b, e, x)`	fast search in a sorted range, `true`/`false`

Interactive

Loading simulation…

Simple sorting algorithms take about n² steps. std::sort works with about n · log n comparisons — for a million elements that is thousands of times fewer.

Key points

The STL = containers + iterators + algorithms.
std::map keeps key–value pairs sorted by key; m[k] creates a missing key with 0.
std::set stores each value once, in sorted order.
v.end() is the place after the last element; std::find returns it when nothing is found.
Ready-made algorithms like std::sort, std::count and std::max_element are shorter and more reliable than hand-written loops.

Check yourself

10 questions. Every correct answer earns XP.

1 / 10

Which container keeps its elements unique and sorted?