Why It Matters: Fewer Lines, Fewer Bugs, Known Costs

Bob wrote a growing array in C for his marks program. It works on Monday. On Tuesday a friend adds six marks and two of them come back as zeros.

Bob's resize copies one element too few, so every time the array grows, the last mark is lost. The compiler said nothing, and the program never crashed. vector::push_back does the same job in millions of programs, and a bug like Bob's would have been found and fixed long ago.

That is the first reason the STL matters. There are two more, and there are costs too. This lesson gives you all of them, because a library that only sells itself is not telling you the whole story.

Reason one: correct code you do not have to write

Every line you write is a line that can be wrong. The STL's containers and algorithms ship with every C++ compiler, and the same code is used by millions of programs every day. A bug in push_back would be found within hours, by someone else.

Here is the same job twice: store the squares of 1 to 5 in a growing array, then print them. First in C, done properly, with the growth and the failure check.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *a = NULL;
    size_t n = 0, cap = 0;
    for (int x = 1; x <= 5; x++) {
        if (n == cap) {
            cap = cap ? cap * 2 : 1;
            int *p = realloc(a, cap * sizeof *a);
            if (p == NULL) { free(a); return 1; }
            a = p;
        }
        a[n++] = x * x;
    }
    for (size_t i = 0; i < n; i++) printf("%d\n", a[i]);
    free(a);
    return 0;
}

1
4
9
16
25

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> a;
    for (int x = 1; x <= 5; x++) {
        a.push_back(x * x);
    }
    for (int v : a) std::cout << v << '\n';
}

1
4
9
16
25

Reason two: every operation has a known cost

The C++ standard does not only say what push_back does. It also says how long it may take, as a complexity (how the work grows as the container grows). For push_back the promise is "amortised constant": on average, adding one element costs the same whether the vector holds ten or ten million.

Your own C array comes with no such promise unless you work it out. The STL's promises are written down, the same for every compiler, and you can look them up before you write a line. Lesson 5 shows you where.

Here is a search, twice. Find where 90 is in a list of marks.

#include <stdio.h>

int main(void)
{
    int marks[] = {72, 45, 90, 61, 88};
    int n = sizeof marks / sizeof marks[0];
    int where = -1;
    for (int i = 0; i < n; i++) {
        if (marks[i] == 90) { where = i; break; }
    }
    if (where >= 0) printf("90 is at index %d\n", where);
    else printf("90 is not there\n");
    return 0;
}

90 is at index 2

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

int main()
{
    std::vector<int> marks = {72, 45, 90, 61, 88};
    auto it = std::find(marks.begin(), marks.end(), 90);
    if (it != marks.end())
        std::cout << "90 is at index " << (it - marks.begin()) << '\n';
    else
        std::cout << "90 is not there\n";
}

90 is at index 2

Reason three: code other people can read

When a C++ programmer reads std::sort(v.begin(), v.end()), they know what it does, what it costs and that it is correct. They do not have to read a sorting function first. The names are shared by every C++ programmer on earth, the way printf is shared by every C programmer.

Sorting shows this best. In C you write a comparison function that takes void pointers, casts them, and returns a negative, zero or positive number.

#include <stdio.h>
#include <stdlib.h>

int by_value(const void *a, const void *b)
{
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void)
{
    int marks[] = {72, 45, 90, 61, 88};
    size_t n = sizeof marks / sizeof marks[0];
    qsort(marks, n, sizeof marks[0], by_value);
    printf("sorted:");
    for (size_t i = 0; i < n; i++) printf(" %d", marks[i]);
    printf("\n");
    return 0;
}

sorted: 45 61 72 88 90

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

int main()
{
    std::vector<int> marks = {72, 45, 90, 61, 88};
    std::sort(marks.begin(), marks.end());
    std::cout << "sorted:";
    for (int m : marks) std::cout << ' ' << m;
    std::cout << '\n';
}

sorted: 45 61 72 88 90

The three pairs, counted

Here are the six programs above, measured two ways. The first is lines of code, not counting blank lines. The second is the details you must get right by hand, each named in the table so you can check the count yourself.

Lines are a rough measure, and the gap is modest for a search. The second column is the one that matters. Thirteen hand-kept details become one, and each detail removed is a bug that can no longer happen.

What the STL costs you

Nothing is free. Here are the four costs, said plainly, so you can weigh them.

• Compile time. On Compiler Explorer's GCC 12.2 at the runner's flags plus -E, which only pastes the headers in, Example 1 with its two C headers comes to 665 lines. Example 2 with <iostream> and <vector> comes to 32,394 lines. Big projects feel this as slower builds.
• Error messages. When you misuse a template, the message can run to dozens of lines of library internals. Module 1 teaches you to find the one line that matters.
• A learning curve. You must learn which container suits which job, and what each operation costs. That is what this track is for, and it takes weeks, not an afternoon.
• Less control. A vector decides how much to grow and when to move its elements. You can ask it to reserve space in advance, but you cannot pick its growth rule. Code that must control every byte, such as firmware for a tiny device, often uses plain C arrays for this reason.

So the honest summary is this. For almost every program you will write in this track, in a contest or at work, the STL wins. When you hit a case where it does not, you will know why, because you know its costs.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {10, 20, 30};
    std::cout << v.at(10) << '\n';
}

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 10) >= this->size() (which is 3)

void push(int x)
{
    if (n == cap) {                         /* full: grow by two */
        int *bigger = calloc(cap + 2, sizeof *bigger);
        for (int i = 0; i < n - 1; i++) bigger[i] = a[i];
        free(a);
        a = bigger;
        cap += 2;
    }
    a[n++] = x;
}

if (std::find(v.begin(), v.end(), 8)) {
    std::cout << "found\n";
}

#include <stdio.h>

int main(void)
{
    printf("%zu\n", sizeof('a'));
    return 0;
}

Next comes the full list of containers, in one table, with the one question each answers fastest.