SyntaxPilot
Courses/C++/Lesson 21
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ · Lesson 21 of 40

STL 1: vector

queued

These are the notes for C++ episode 21, the first episode on the STL. In episode 8 you used arrays, in episode 10 you got memory at run time with new[] and delete[], and in episode 20 you wrote templates: code written once that works for any type. Here those three ideas meet. A chai stall that can't know how many orders a day will bring breaks a fixed array, growing an array by hand works but costs ten risky lines every time, and the fix, a growing array written once as a template, is exactly std::vector. Every example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the same command as the SyntaxPilot compiler) and run; the outputs and error messages are copied from those runs.

The problem: Raju's order notebook

Raju runs a chai stall near the station and writes every order in a notebook with five lines.

Day Orders What happens with a fixed notebook
Normal morning 5 fits exactly
Cricket match day 8 before 9 am line 6 doesn't exist
Slow Monday with a 1000-line register 12 988 lines wasted
Big final with a 1000-line register 1001+ still not enough

The real problem is that nobody knows the size in advance. Every fixed size is either too small or wasteful.

Step 1: a fixed array on a busy day

The obvious code uses an array from episode 8 and reads orders until the input ends:

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

int main() {
    int count = 0;
    string orders[5];
    string item;
    while (cin >> item) {
        orders[count] = item;
        count++;
    }
    cout << "Orders today: " << count << endl;
    for (int i = 0; i < count; i++) cout << orders[i] << " ";
    cout << endl;
    return 0;
}

Input (8 orders):

chai
coffee
chai
samosa
chai
bun
chai
lassi

Output:

Segmentation fault

Why it fails: an array's size is fixed when you write it. Order 6 is stored at orders[5], past the end of the array, in memory that belongs to something else. C++ does not check array indexes, so the program writes over other data and crashes (a segmentation fault is the operating system stopping a program that touched memory it doesn't own). Writing past the end is undefined behaviour: it may crash, print garbage, or seem to work, which is worse.

Making the array bigger (string orders[1000];) only moves the problem: a quiet day wastes 988 strings, and order 1001 crashes again.

Step 2: growing an array by hand

Do what Raju would do: when the notebook is full, get one twice as big and copy everything across. With new[] (episode 10) the size can be chosen at run time:

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

int main() {
    int cap = 2, count = 0;
    string* orders = new string[cap];
    string item;
    while (cin >> item) {
        if (count == cap) {              // full: move to a bigger box
            string* bigger = new string[cap * 2];
            for (int i = 0; i < count; i++) bigger[i] = orders[i];
            delete[] orders;
            orders = bigger;
            cap = cap * 2;
            cout << "(grew to " << cap << ")" << endl;
        }
        orders[count++] = item;
    }
    cout << "Orders today: " << count << endl;
    for (int i = 0; i < count; i++) cout << orders[i] << " ";
    cout << endl;
    delete[] orders;
    return 0;
}

Output (same 8 orders):

(grew to 4)
(grew to 8)
Orders today: 8
chai coffee chai samosa chai bun chai lassi

It works. But look at the cost:

  • About ten lines of bookkeeping (cap, count, new, the copy loop, delete[], the pointer swap).
  • Forget the last delete[] and memory leaks. Forget cap = cap * 2 and it overflows again.
  • Every program that needs a list (of ints, of strings, of students) would repeat the same code.

Code you need for any type, written once: that is what templates (episode 20) are for. The C++ standard library already contains this growing array, written as a template: std::vector.

Step 3: vector, the array that grows by itself

New words

Word Plain meaning
STL The Standard Template Library: ready-made, tested templates that come with every C++ compiler (containers, algorithms, iterators).
Container An object that holds many values. vector is the first container in this course; list, deque, map, set follow.
vector A container that works like an array but grows by itself.
Template argument The type in angle brackets: in vector<string>, string is the type of every item.

Real-life picture: a magic notebook that adds its own pages whenever it's about to fill up.

Raju's notebook C++
A notebook that grows vector<string> orders;
Write the next order on the next free line orders.push_back(item);
Count the lines used orders.size()
Read line 3 orders[2] (indexes start at 0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> orders;
    string item;
    while (cin >> item) {
        orders.push_back(item);
    }
    cout << "Orders today: " << orders.size() << endl;
    for (int i = 0; i < orders.size(); i++) cout << orders[i] << " ";
    cout << endl;
    return 0;
}

Output:

Orders today: 8
chai coffee chai samosa chai bun chai lassi

The same output as the hand-written version, with one line (push_back) instead of ten. There is no delete anywhere: when orders goes out of scope, the vector's destructor frees its memory (episode 13). A new vector starts empty (size 0).

Ways to create a vector:

Code Result
vector<int> v; empty, size 0
vector<int> v = {40, 15, 60}; three items
vector<int> v(5); five items, all 0
vector<int> v(5, 7); five items, all 7
vector<string> w(3, "chai"); three "chai" strings

Step 4: safe access with at()

Square brackets on a vector behave like on an array: fast, and never checked. at() checks the index.

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

int main() {
    vector<int> bills = {40, 15, 60};
    cout << "bills[1]: " << bills[1] << endl;
    cout << "bills[10]: " << bills[10] << endl;
    cout << "bills.at(10): " << bills.at(10) << endl;
    return 0;
}

Output:

bills[1]: 15
bills[10]: 891304541
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)
  • bills[10] prints whatever happened to be in that memory (the number changes between runs and machines): no error, just a wrong answer.
  • bills.at(10) throws an exception (an error object that stops the program unless it is caught; episode 31 covers catching them): std::out_of_range, and the message says exactly why: index 10 is not less than size 3. The line's label is never printed because the program stopped before the output buffer was flushed.

Rule: [] when you are sure of the index (it is slightly faster); at() while learning, and whenever the index comes from a user.

Step 5: a train waitlist, insert and erase

A waitlist is a list in order: people join at the back, a senior citizen may be moved to the front, and anyone can cancel from the middle.

Waitlist event vector call
Kabir joins at the back wait.push_back("Kabir");
Kabir leaves from the back wait.pop_back();
Dadi goes to the front wait.insert(wait.begin(), "Dadi");
Ravi (3rd) cancels wait.erase(wait.begin() + 2);
Who is first / last? wait.front(), wait.back()
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void show(vector<string> w) {
    for (string name : w) cout << name << " ";
    cout << "(" << w.size() << " waiting)" << endl;
}

int main() {
    vector<string> wait = {"Asha", "Ravi", "Meena"};
    wait.push_back("Kabir");                // joins at the back
    show(wait);
    wait.pop_back();                        // Kabir leaves
    show(wait);
    wait.insert(wait.begin(), "Dadi");      // senior citizen: front
    show(wait);
    wait.erase(wait.begin() + 2);           // Ravi cancels
    show(wait);
    cout << "Front: " << wait.front() << ", back: " << wait.back() << endl;
    return 0;
}

Output:

Asha Ravi Meena Kabir (4 waiting)
Asha Ravi Meena (3 waiting)
Dadi Asha Ravi Meena (4 waiting)
Dadi Asha Meena (3 waiting)
Front: Dadi, back: Meena

insert and erase need a position, given as an iterator. For now, think of an iterator as a bookmark that points at one item: begin() points at the first item, and begin() + i points at position i (end() points just past the last item). Iterators get their own episode (26).

Note: show takes its vector by value, so each call copies the whole waitlist. That is fine for four names; Step 9 shows why it matters for big vectors.

Common member functions:

Function What it does
push_back(x) add x at the end
pop_back() remove the last item (the vector must not be empty)
size() number of items
empty() true if there are no items
front() / back() first / last item (must not be empty)
insert(v.begin() + i, x) put x at position i; later items move one place right
erase(v.begin() + i) remove the item at position i; later items move one place left
clear() remove everything (size becomes 0)
at(i) item i, with a range check

Step 6: how a vector grows (size vs capacity)

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

int main() {
    vector<int> v;
    int last = -1;
    for (int i = 1; i <= 100; i++) {
        v.push_back(i);
        if (v.capacity() != last) {
            last = v.capacity();
            cout << "size " << v.size() << " -> capacity " << last << endl;
        }
    }
    return 0;
}

Output:

size 1 -> capacity 1
size 2 -> capacity 2
size 3 -> capacity 4
size 5 -> capacity 8
size 9 -> capacity 16
size 17 -> capacity 32
size 33 -> capacity 64
size 65 -> capacity 128
  • size = how many items are inside.
  • capacity = how many items fit before the vector must move to a bigger block of memory.

When it is full, g++'s vector doubles its capacity: allocate a bigger block, copy (or move) every item, free the old block. That's exactly our hand-written Step 2. (The C++ standard doesn't fix the growth factor; g++ and clang double, Microsoft's library grows by 1.5×.)

Amortized O(1)

A move copies everything, which is slow, but because the capacity doubles, moves are rare: reaching 100 items needed only 7 moves (capacity 1→2→4→8→16→32→64→128). If you spread the cost of those rare moves over all the pushes, each push_back costs a small constant amount on average. This is called amortized O(1) ("amortized" = averaged over many operations). Real-life picture: a family that moves house rarely, but always to a place twice as big.

reserve()

If you know roughly how many items are coming, make room up front:

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

int main() {
    vector<int> v;
    v.reserve(100);
    int last = -1;
    for (int i = 1; i <= 100; i++) {
        v.push_back(i);
        if (v.capacity() != last) {
            last = v.capacity();
            cout << "size " << v.size() << " -> capacity " << last << endl;
        }
    }
    return 0;
}

Output:

size 1 -> capacity 100

One allocation, zero moves. reserve makes room, not items: the size is still 0 until you push_back. (To make items, use vector<int> v(100); or v.resize(100);.)

Step 7: 2D vectors, a train coach

A table is a vector of vectors: each row is its own vector<int>.

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

int main() {
    vector<vector<int>> coach(3, vector<int>(4, 0));   // 3 rows, 4 seats
    coach[0][1] = 1;
    coach[2][3] = 1;
    coach[1].push_back(0);                            // row 1 gets an extra seat
    for (int r = 0; r < coach.size(); r++) {
        cout << "Row " << r << ": ";
        for (int seat : coach[r]) cout << (seat ? "X " : ". ");
        cout << endl;
    }
    return 0;
}

Output:

Row 0: . X . . 
Row 1: . . . . . 
Row 2: . . . X
  • vector<vector<int>> coach(3, vector<int>(4, 0)); = 3 rows, each a vector of 4 zeros (free seats).
  • coach[r][s] reads or writes row r, seat s.
  • coach[1].push_back(0) gives only row 1 an extra seat: rows can have different lengths (a "jagged" table), which a 2D array cannot do.

Step 8: passing a vector to a function

By value: the changes vanish

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

void addOrder(vector<string> orders, string item) {
    orders.push_back(item);
    cout << "Inside: " << orders.size() << " orders" << endl;
}

int main() {
    vector<string> orders = {"chai"};
    addOrder(orders, "samosa");
    addOrder(orders, "bun");
    cout << "Outside: " << orders.size() << " orders" << endl;
    return 0;
}

Output:

Inside: 2 orders
Inside: 2 orders
Outside: 1 orders

Passing by value gives the function a full copy. It adds to the copy, and the copy is destroyed when the function returns. Copying a vector of a million items is also slow.

By reference: work on the real vector

Add one & (episode 10):

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

void addOrder(vector<string>& orders, string item) {
    orders.push_back(item);
    cout << "Inside: " << orders.size() << " orders" << endl;
}

int main() {
    vector<string> orders = {"chai"};
    addOrder(orders, "samosa");
    addOrder(orders, "bun");
    cout << "Outside: " << orders.size() << " orders" << endl;
    return 0;
}

Output:

Inside: 2 orders
Inside: 3 orders
Outside: 3 orders

By const reference: read without copying

For a function that only reads, pass const vector<int>&: no copy, and a promise not to change it. Breaking the promise is a compile error:

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

int total(const vector<int>& bills) {
    int sum = 0;
    for (int b : bills) sum += b;
    bills.push_back(0);
    return sum;
}

int main() {
    vector<int> bills = {40, 15, 60};
    cout << "Total: " << total(bills) << endl;
    return 0;
}

g++ says:

main.cpp: In function 'int total(const std::vector<int>&)':
main.cpp:8:20: error: passing 'const std::vector<int>' as 'this' argument discards qualifiers [-fpermissive]
    8 |     bills.push_back(0);
      |     ~~~~~~~~~~~~~~~^~~

In plain words: push_back changes the vector, but you promised (const) not to. Without that line:

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

int total(const vector<int>& bills) {
    int sum = 0;
    for (int b : bills) sum += b;
    return sum;
}

int main() {
    vector<int> bills = {40, 15, 60};
    cout << "Total: " << total(bills) << endl;
    return 0;
}

Output:

Total: 115
You want to... Parameter
change the caller's vector vector<T>& v
only read it const vector<T>& v
work on your own private copy vector<T> v

A function can also return a vector (vector<int> evens(...) { ... return result; }); modern C++ moves it out instead of copying (episode 29 explains move semantics).

Mini project: a train waitlist from commands

Commands: join <name> adds to the back, confirm gives the front passenger a berth, cancel <name> removes that passenger. At the end, print the waitlist.

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

int main() {
    vector<string> wait;
    string cmd, name;
    while (cin >> cmd) {
        if (cmd == "join") {
            cin >> name;
            wait.push_back(name);
        } else if (cmd == "confirm" && !wait.empty()) {
            cout << wait.front() << " gets a berth!" << endl;
            wait.erase(wait.begin());
        } else if (cmd == "cancel") {
            cin >> name;
            for (int i = 0; i < wait.size(); i++)
                if (wait[i] == name) { wait.erase(wait.begin() + i); break; }
        }
    }
    cout << "Still waiting: " << wait.size() << endl;
    for (int i = 0; i < wait.size(); i++)
        cout << "WL " << i + 1 << ": " << wait[i] << endl;
    return 0;
}

Input:

join Asha
join Ravi
join Meena
join Kabir
confirm
cancel Meena
join Dev

Output:

Asha gets a berth!
Still waiting: 3
WL 1: Ravi
WL 2: Kabir
WL 3: Dev
  • !wait.empty() guards confirm: front() of an empty vector is undefined behaviour.
  • cancel searches with a loop and erases at begin() + i, then breaks (the indexes after i have shifted).
  • Every erase(wait.begin()) moves all the other passengers one place to the left. With a million passengers, that is a million moves for one confirm: the problem list and deque solve in the next episode.

Common mistakes (and the real g++ messages)

Mistake Code What g++ says / what happens Fix
Forgetting the header vector<int> bills; without #include <vector> error: 'vector' was not declared in this scope and note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'? #include <vector>
Indexing an empty vector vector<int> bills; bills[0] = 40; Segmentation fault (undefined behaviour) bills.push_back(40); or vector<int> bills(1);
Index past the end with at() bills.at(10) (size 3) 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) check i < bills.size()
Index past the end with [] bills[10] (size 3) no message: a garbage number use at(), or check the index
Passing by value and expecting changes void addOrder(vector<string> orders, ...) no message: Outside: 1 orders vector<string>& orders
Changing through a const reference const vector<int>& bills then bills.push_back(0); error: passing 'const std::vector<int>' as 'this' argument discards qualifiers [-fpermissive] drop const, or don't change it
Erasing in a loop and then i++ see below no message: skips the item after each erased one don't i++ after an erase
Confusing reserve with size v.reserve(5); v[0] = 1; undefined behaviour: size is still 0 v.resize(5) or push_back

The erase-in-a-loop bug, run for real:

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

int main() {
    vector<int> v = {5, -2, -7, 3};
    for (int i = 0; i < v.size(); i++)
        if (v[i] < 0) v.erase(v.begin() + i);
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

Output:

5 -7 3

-7 survived: after erasing -2 at index 1, -7 slid into index 1, and i++ jumped past it. Practice question 2 shows the fix.

Practice

  1. Read marks until the input ends; print how many students, the average and the highest mark.
  2. Remove every negative number from a vector (watch out for the erase-in-a-loop bug).
  3. Reverse a vector in place, without a second vector.
  4. Add a status <name> command to the waitlist that prints the passenger's WL number, or "not on the list".
Solutions

1. Input 72 88 95 61 80:

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

int main() {
    vector<int> marks;
    int m;
    while (cin >> m) marks.push_back(m);
    if (marks.empty()) {
        cout << "No marks" << endl;
        return 0;
    }
    int sum = 0, best = marks[0];
    for (int x : marks) {
        sum += x;
        if (x > best) best = x;
    }
    cout << "Students: " << marks.size() << endl;
    cout << "Average: " << (double)sum / marks.size() << endl;
    cout << "Highest: " << best << endl;
    return 0;
}

Output:

Students: 5
Average: 79.2
Highest: 95

2. Only move on when nothing was erased:

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

int main() {
    vector<int> v = {5, -2, 8, -7, -1, 3};
    for (int i = 0; i < v.size(); ) {
        if (v[i] < 0) v.erase(v.begin() + i);   // don't move on: the next item slid into i
        else i++;
    }
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

Output:

5 8 3

(The STL can also do this in one line with erase + remove_if; that's for the STL algorithms episode, 27.)

3. Two indexes walk towards each other and swap:

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    int i = 0, j = v.size() - 1;
    while (i < j) {
        int t = v[i];
        v[i] = v[j];
        v[j] = t;
        i++;
        j--;
    }
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

Output:

5 4 3 2 1

4. Add one more else if to the command loop. Input join Asha, join Ravi, join Meena, status Meena, confirm, status Meena, status Asha:

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

int main() {
    vector<string> wait;
    string cmd, name;
    while (cin >> cmd) {
        if (cmd == "join") {
            cin >> name;
            wait.push_back(name);
        } else if (cmd == "confirm" && !wait.empty()) {
            cout << wait.front() << " gets a berth!" << endl;
            wait.erase(wait.begin());
        } else if (cmd == "cancel") {
            cin >> name;
            for (int i = 0; i < wait.size(); i++)
                if (wait[i] == name) { wait.erase(wait.begin() + i); break; }
        } else if (cmd == "status") {
            cin >> name;
            bool found = false;
            for (int i = 0; i < wait.size(); i++)
                if (wait[i] == name) { cout << name << ": WL " << i + 1 << endl; found = true; }
            if (!found) cout << name << ": not on the list" << endl;
        }
    }
    cout << "Still waiting: " << wait.size() << endl;
    for (int i = 0; i < wait.size(); i++)
        cout << "WL " << i + 1 << ": " << wait[i] << endl;
    return 0;
}

Output:

Meena: WL 3
Asha gets a berth!
Meena: WL 2
Asha: not on the list
Still waiting: 2
WL 1: Ravi
WL 2: Meena

Quick quiz

What does this print?

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

int main() {
    vector<int> v = {10, 20, 30};
    v.push_back(40);
    v.erase(v.begin() + 1);
    v.pop_back();
    cout << v.size() << " " << v.back();
    return 0;
}
  • A. 2 30
  • B. 3 40
  • C. 2 20
  • D. 3 30
Answer

A: 2 30 (verified). {10, 20, 30} → push_back(40): {10, 20, 30, 40} → erase(v.begin() + 1) removes the second item, 20: {10, 30, 40} → pop_back() removes 40: {10, 30}. Size 2, back 30.

Output:

2 30

Interview questions

  • What is the difference between an array and a vector? An array's size is fixed at compile time and it never checks indexes; a vector grows at run time, knows its own size(), frees its own memory, can be copied and returned like any value, and offers checked access with at().
  • What is the difference between size and capacity? Size is the number of items stored; capacity is how many fit in the current memory block before a reallocation. capacity() >= size() always.
  • What is the time complexity of push_back? Amortized O(1): usually constant, occasionally O(n) when the vector reallocates, but because capacity grows by a constant factor the average stays constant.
  • What is the time complexity of insert / erase at the front or middle? O(n): every later item must move one place.
  • [] vs at()? [] is unchecked (out of range is undefined behaviour); at() checks and throws std::out_of_range.
  • reserve vs resize? reserve(n) changes only capacity (no new items); resize(n) changes the size, creating or destroying items.
  • What happens to pointers, references and iterators to elements when a vector reallocates? They become invalid (they point to freed memory). reserve up front, or use indexes, if you must keep them.
  • How should you pass a vector to a function? const vector<T>& to read, vector<T>& to modify, by value only when the function needs its own copy.
  • Why are a vector's elements contiguous, and why does that matter? They are stored side by side like an array, so indexing is O(1) and looping over them is very cache-friendly (fast on real hardware).

Glossary

Term Plain meaning Example
STL Standard Template Library: ready-made templates that come with C++ vector, map, sort
Container An object that holds many values vector<int>
vector A container that works like an array and grows by itself vector<string> orders;
Template argument The type you give a template in angle brackets string in vector<string>
Header A file you #include to use a library feature #include <vector>
push_back Add an item at the end orders.push_back("chai");
pop_back Remove the last item wait.pop_back();
size Number of items stored orders.size() → 8
empty Whether there are no items wait.empty()
front / back The first / last item wait.front() → Dadi
Index The position number of an item, starting at 0 orders[2] is the 3rd order
at() Index access with a range check bills.at(10) throws
Exception An error object that stops the program unless it is caught std::out_of_range
Segmentation fault The OS stopping a program that touched memory it doesn't own writing orders[5] in a size-5 array
Undefined behaviour Code the C++ rules give no meaning to; anything may happen bills[10] on size 3
Iterator A bookmark pointing at one item of a container wait.begin() + 2
begin() / end() Iterators to the first item / just past the last wait.insert(wait.begin(), "Dadi")
insert / erase Add / remove at a position; later items shift wait.erase(wait.begin() + 2)
Capacity How many items fit before the vector must move 1, 2, 4, 8, ...
Reallocation Moving to a bigger memory block and copying everything capacity 4 → 8
Amortized O(1) Constant time on average over many operations, even if a few are slow push_back
reserve Make room for n items up front (size unchanged) v.reserve(100);
resize Change the number of items v.resize(5);
2D vector A vector whose items are vectors: a table vector<vector<int>> coach
Jagged table A table whose rows have different lengths row 1 has 5 seats
Pass by value The function gets its own copy void f(vector<int> v)
Pass by reference The function works on the caller's vector void f(vector<int>& v)
Const reference No copy, and no changes allowed int total(const vector<int>& b)
Memory leak Memory taken with new and never given back forgetting delete[]
Destructor Function that runs when an object is destroyed; vector's frees its memory end of main

Summary

  • A fixed array can't grow: order 6 in a 5-string array is a segmentation fault, and a bigger fixed size only wastes memory.
  • Growing by hand (new[], copy, delete[], double) works but is ten risky lines repeated in every program.
  • std::vector<T> from the STL is that growing array written once as a template: push_back, pop_back, size, empty, front, back, and it frees its own memory.
  • [] never checks; at() throws std::out_of_range.
  • insert and erase take an iterator position, begin() + i; items after it shift, which costs O(n).
  • size vs capacity: capacity doubles when full (1, 2, 4, ... 128), so push_back is amortized O(1); reserve makes room ahead.
  • Tables are vectors of vectors, and rows can have different lengths.
  • Pass vector<T>& to change, const vector<T>& to read; by value works on a copy.

Next episode: STL 2, list and deque. Every erase(begin()) in the waitlist moved every other passenger; with a million passengers that's a million moves for one confirm. list and deque are built for that.