Structures, vectors, and container contracts

A record groups fields that describe one thing. A book might have a title and a quantity: those two values belong together. A structure gives the fields names and places them in one object. A vector then stores a sequence of those objects and manages the sequence's memory.

These tools remove some manual bookkeeping, but they do not remove the need to understand which elements exist, which accesses are valid, and whether a function copies or changes its inputs.

Read one record and one collection #

struct introduces a type with named members. Here Book is the type; title and quantity are its members. A type describes the form of an object. Each actual book object has its own values for those members.

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

struct Book {
    std::string title;
    int quantity;
};

int total_quantity(const std::vector<Book>& books) {
    int total = 0;
    for (const Book& book : books) {
        total += book.quantity;
    }
    return total;
}

int main() {
    std::vector<Book> books;
    books.push_back(Book{"Atlas", 3});
    books.push_back(Book{"Poems", 2});
    std::cout << books.size() << ' ' << total_quantity(books) << '\n';
}

The first three headers provide stream output, strings, and vectors. The structure declaration establishes the form of a book before any vector of books is declared. Its ending semicolon belongs to that type declaration.

Begin the execution trace in main. books starts as an empty vector of Book objects. Book{"Atlas", 3} constructs a record whose title is "Atlas" and quantity is 3. push_back adds that record at the vector's end. After this statement, size is 1 and index 0 identifies the Atlas record. The next statement adds Book{"Poems", 2}. Size becomes 2; index 1 identifies the Poems record.

The print expression obtains the size and calls total_quantity. Inside that function, total begins at 0. The first loop iteration reads the Atlas record and adds its quantity, making total 3. The second reads Poems and adds 2, making total 5. The function returns 5, so the output is 2 5: two book records and five copies of books in total.

This example assumes small nonnegative quantities whose sum fits in an int. A type declaration alone does not enforce those assumptions. A larger application would validate incoming quantities and choose an appropriate type or overflow check for its totals.

Grouping fields helps preserve their relationship during sorting or movement. With parallel arrays, a title at one index and a quantity at the same index are related only by a convention the code must maintain. Swapping just one array breaks it. Moving one Book object moves its associated fields together.

Count existing elements, not reserved space #

Size is the number of elements currently in the vector. Capacity is the amount of element storage the vector can use before needing another allocation. Capacity can exceed size. Extra capacity is not a collection of extra accessible elements.^[1]

std::vector<int> values; begins with size zero. values.reserve(10) requests capacity for at least ten elements, but size remains zero. There are still no valid element indices. In contrast, values.resize(10) changes the size to ten. For these integers, the newly added values are zero. std::vector<int> values(10, 4) creates a vector already containing ten integers, each with value 4.

push_back appends one element and increases size by one. If size was 3, it becomes 4, and the new element has index 3. An indexed assignment such as values[i] = 9 changes an existing element; it does not grow the vector. values.at(i) performs a bounds check and throws if the position is out of range. values[i] requires the caller to supply a valid position.

front and back access the first and last elements, so the vector must be nonempty. pop_back removes the last element and likewise needs a nonempty vector. Removing an element is different from merely overwriting its value: after removal, the size and valid index range have changed.

Understand what a reference reads #

The parameter const std::vector<Book>& books is a read-only reference to the caller's vector. The function does not receive a full vector copy. It reads through an alias, and the const restricts modification through that parameter.

In for (const Book& book : books), each iteration's book is a read-only alias for the corresponding existing record. Reading book.quantity reads that record's quantity. The loop does not copy each title string just to add an integer.

Compare three loop declarations. for (Book book : books) creates a value copy for each iteration. Changing that local record would not change the original vector's record. for (Book& book : books) aliases each original record and permits changes. for (const Book& book : books) aliases it for reading. Choose according to the function's intended effect, rather than treating the forms as interchangeable punctuation.

Passing an entire vector by value can be appropriate when the function deliberately needs independence. The capstone median function does that so it can sort its own copy. A reference, meanwhile, does not generally keep an owner's elements alive after their destruction. Its safety still depends on the objects it names continuing to exist.

Structural changes can invalidate aliases #

Appending can require a larger allocation. The vector then relocates its elements and releases the old allocation. Pointers, references, and iterators into that old allocation are invalidated. An iterator is an object used to identify and traverse positions in a container. Do not continue using an old element address merely because the vector variable itself still exists.

erase removes selected elements and moves the later ones forward. Iterators and references at and after the erased position are invalidated; an index can also now identify a different record. After a structural change, use the operation's documented result or obtain a fresh position. The simpler beginner rule is to avoid retaining aliases across changes to the collection's shape.

Practice with explained answers #

A vector has size 3 and capacity 8. Its valid indices are 0, 1, and 2, because only three elements exist. After push_back(9), size is 4 and index 3 identifies the appended value. values[7] = 9 is not a valid way to use reserved storage: there is no element at index 7 yet.

If a loop uses Book book and adds one to its quantity, the original records do not change. If it uses Book& book, each original quantity changes. This distinction and the size/capacity distinction prepare CS2 Lecture 11, inventory work in Lab 3, and comparisons with manually managed dynamic arrays.