Storing Collections of Data

What Are Containers and Arrays?

A container is a data type that stores a collection of unnamed objects, called elements. An array is a container that keeps its elements contiguously, one after another in memory with no gaps between them, which is what makes reaching any element fast.

Both exist to answer the same question: what do you do when a program needs many values of the same kind, and naming each one individually has stopped being practical?

Why Separate Variables Do Not Scale

Say you are tracking the daily high temperature across a week so you can report the average. With one variable per day, the declarations alone take seven lines:

double temperature1{};
double temperature2{};
double temperature3{};
// and so on, through temperature7

The average is worse, because every name has to appear again:

double average{ (temperature1 + temperature2 + temperature3 + temperature4
               + temperature5 + temperature6 + temperature7) / 7.0 };

That is tedious to type, easy to typo in a way that still compiles, and it has to be repeated in full every time you want to do something else with the values, such as printing them.

Now extend the report to a full month. Every place that touches the data has to be found and revised, temperature8 through temperature31 have to be added throughout, and the divisor has to change from 7.0 to 31.0. Miss that last edit and the program keeps running and quietly reports the wrong number. At a few hundred or a few thousand values the approach stops being merely annoying and becomes impossible.

Grouping the variables in a struct improves the organisation, since the week can then be passed around as one object:

struct WeekTemperatures
{
    double monday{};
    double tuesday{};
    double wednesday{};
    // and so on, through sunday
};

But the underlying problem survives the change. Each value still has its own name, so each value still has to be written out individually, and adding days still means editing the type.

What Makes Something a Container

The defining property of a container is that its elements are unnamed. The container object itself has a name, or you could not refer to it at all, but the things inside it do not. That is precisely what lifts the limit: a collection whose elements need no names can hold as many as you like.

This is also the line that separates a container from a plain struct. A struct's members are named, so the number of them is fixed when the type is written. It is why WeekTemperatures above is not a container.

Since the elements have no names, every container has to offer some other way to reach them, and the mechanism varies from one container type to another.

You have already used a container. A std::string stores a collection of characters:

#include <iostream>
#include <string>

int main()
{
    std::string title{ "Interstellar" };

    std::cout << title << " is spelled with " << title.length() << " letters\n";

    return 0;
}

Output:

Interstellar is spelled with 12 letters

The container has a name, title. The twelve characters inside it do not.

Length Versus Size

The number of elements in a container is its length, sometimes called its count. C++ also uses the word size for this, which is unfortunate, because size equally describes how many bytes of memory an object occupies, which is what the sizeof operator reports.

This course keeps the two apart: length always means how many elements there are, and size always means how much memory is used.

What Containers Let You Do

Most containers support some substantial subset of four operations:

• Create the container, whether empty, sized for some number of elements, or filled from a list of values
• Reach elements, such as the first, the last, or any particular one
• Insert and remove elements
• Report how many elements it currently holds

What separates one container type from another is which of these it supports and how fast each one is. A type offering instant access to any element may not allow insertion in the middle at all. A type that inserts and removes cheaply may only let you walk the elements in order. There is no container that is best at everything, so choosing the right one for the access pattern you actually have is a decision with real consequences for both performance and readability.

One Element Type Per Container

C++ containers are homogenous: every element has the same type. Some containers fix that type in advance, the way a string always holds characters, but most let you choose. Container types in C++ are class templates, so you supply the element type as a template argument and get a container specialised for it, which is why one std::vector definition serves every element type rather than needing a separate container type for each.

Containers in C++ Specifically

The Containers library is the part of the standard library providing these types, and a class implementing one is called a container class.

C++ defines the word more narrowly than programming does generally. Officially, only the class types in the Containers library are containers, which means a type has to satisfy a specific list of requirements, including particular member functions. The consequence is that some things that clearly behave like containers are not containers by the standard's definition:

• C-style arrays, which are not class types at all
• std::string
• std::vector<bool>

The last two implement most of the requirements and behave like containers nearly all of the time, so they are often called pseudo-containers. This course uses "container" for the general idea and "container class" when the distinction matters.

Of everything in the library, std::vector and std::array account for the overwhelming majority of real use, and they are where this course spends its time. The rest are specialised tools for specific access patterns.

Arrays

An array stores its elements contiguously, which means element five sits immediately after element four in memory. Because the elements are evenly spaced and the layout is predictable, the address of any element can be computed directly rather than searched for, which is what gives arrays their fast access. They are also simple to reason about, which makes them the default choice for a set of related values.

C++ has three array types:

C-style arrays exist in C++ for backwards compatibility with C, and are built into the core language rather than provided by the library. The standard calls them simply "arrays", but that name now collides with std::array, so they go by C-style arrays, C arrays, naked arrays, fixed arrays, or built-in arrays depending on who is writing. This course says "C-style array" for the C type and "array" when the point applies to all of them. They are still worth learning because they appear everywhere in older code, and a later chapter covers the ways they behave badly.

All three remain in use, so all three get coverage here.

Moving Forward

The next lesson introduces std::vector and applies it to the temperature problem from the top of this lesson. std::vector gets a lot of attention, because using it well means picking up several new ideas along the way.

Usefully, the container classes share much of their interface. Once one of them makes sense, the others are mostly a matter of noting the differences, which is how later chapters will treat them.

Summary

• A container provides storage for a collection of unnamed elements, and the number it holds is its length
• Elements are unnamed so that a container can hold any number of them, which is also what distinguishes a container from a struct whose members each need a name
• Defining one variable per value does not scale: the code grows with the data and every change risks missing an edit
• Length counts elements, while size may also mean bytes of memory, as reported by sizeof
• Containers generally support creation, element access, insertion and removal, and reporting their length, and different container types make different performance tradeoffs among them
• C++ containers are homogenous and implemented as class templates, so the element type is chosen by the user
• The C++ Containers library defines "container" more strictly than general programming does, leaving C-style arrays, std::string, and std::vector<bool> as pseudo-containers
• An array stores elements contiguously, which is what makes direct access to any element fast
• The three C++ array types are C-style arrays (legacy, kept for C compatibility), std::vector (resizable, most flexible), and std::array (fixed length, lightweight)