The standard library: vector, string, map and sort

Introduction

The C++ standard library (the STL) gives you tested, fast classes and functions built from templates. Using them is usually better than writing your own.

Most programs need lists, lookups and sorting. The standard library provides tested, efficient versions of all three, so the classes you write can focus on your own problem.

How it works

vector: an array that grows

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

int main() {
    vector<int> marks = {72, 85, 64};
    marks.push_back(91);
    cout << "size " << marks.size() << ", first " << marks[0] << endl;
    int total = 0;
    for (int m : marks) total += m;
    cout << "average " << total / marks.size() << endl;
    sort(marks.begin(), marks.end());
    for (int& m : marks) m += 5;
    for (int m : marks) cout << m << " ";
    cout << endl;
    return 0;
}

• vector<int> marks = {72, 85, 64}; makes a vector with three items. push_back adds one at the end; the vector gets more memory by itself when it is full.
• marks.size() is the number of items, and marks[i] reaches item i (marks.at(i) does the same but checks the index and throws out_of_range).
• for (int m : marks) is a range-for loop: it visits every item in order. Use int& m to change the items, and const T& to read big items without copying them.
• sort(marks.begin(), marks.end()) sorts the items. begin() and end() mark the start and one-past-the-end of the range.

In the visualizer a vector shows its items, like an array. The vector object itself holds a pointer to its items on the heap, the size and the capacity, and frees the items in its destructor.

Syntax

vector<int> v = {3, 1, 2};
v.push_back(5);
sort(v.begin(), v.end());

map<string, int> count;
count["red"]++;
for (auto& p : count) cout << p.first << " " << p.second << endl;

Example

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    string words[] = {"red", "blue", "red", "green", "blue", "red"};
    map<string, int> count;
    for (const string& w : words) count[w]++;
    for (auto& p : count) cout << p.first << ": " << p.second << endl;
    cout << "blue appears " << count["blue"] << " times" << endl;
    return 0;
}

map<string, int> stores pairs of a key and a value, with each key at most once, kept in sorted order of the keys. count[w]++ finds the word, or adds it with the value 0 first, then adds one. Looping over a map gives the pairs in key order; each pair has .first (the key) and .second (the value).

auto lets the compiler work out a variable's type from its initializer; here auto& p saves writing pair<string, int>&.

Line by line

1. words is an ordinary array of six strings.
2. map<string, int> count maps each word to a number.
3. The range-for visits each word, and count[w]++ adds the word with value 0 the first time, then adds 1.
4. The second loop visits the map in key order, so the words come out alphabetically: blue, green, red.
5. auto& p is a reference to each pair, where p.first is the word and p.second the count.
6. count["blue"] looks the word up and prints 2.

Expected result

blue: 2
green: 1
red: 3
blue appears 2 times

In the real world

Counting words, grouping records by a key and building indexes are everyday jobs in data processing and are usually done with maps. Contest programmers rely on the STL so heavily that knowing it well is part of competitive programming.

Common mistakes

• Keeping a pointer or reference to a vector's item, then calling push_back: if the vector moves its items to bigger memory, the old reference points to freed memory. StepVioz stops you when that happens.
• marks[marks.size()]: the last valid index is size() - 1.
• count[w] adds the key w if it is missing. To only check, use count.count(w).

Best practices

• Choose vector unless you need something it does not offer.
• Use count.count(k) or find to check for a key without adding it.
• Pass containers to functions by const&.

Summary

The STL provides containers such as vector and map and algorithms such as sort. Vectors grow and index fast, maps keep keys sorted and look them up by key, and range-for loops visit every item.

Mark lesson complete