array and deque: A Size You Fix, and a Line That Grows at Both Ends

Kenji's step counter shows one number per day, Monday to Sunday. There are exactly seven days, and he knows that when he writes the program. Alice has a different problem. Customers join her shop line at the back and are served from the front, and a VIP may go straight to the front. This lesson gives each of them a container that fits: std::array for the week, and std::deque for the line.

Two problems a vector does not quite fit

Kenji first stores his week in a C array, as the C track taught. Then he passes it to a function, and the array forgets its own size.

#include <iostream>
using namespace std;

void show(int steps[]) {
    cout << "inside show: " << sizeof(steps) << " bytes\n";
}

int main() {
    int steps[7] = {3000, 4500, 12000, 8000, 12000, 2000, 6000};
    cout << "in main: " << sizeof(steps) << " bytes\n";
    show(steps);
    return 0;
}

in main: 28 bytes
inside show: 8 bytes

In main, seven ints of 4 bytes are 28 bytes. Inside show, the parameter is only a pointer to the first box, and a pointer is 8 bytes on the Playground. GCC 12 warns about it even without -Wall: warning: 'sizeof' on array function parameter 'steps' will return size of 'int*' [-Wsizeof-array-argument]. So a C array passed to a function arrives without its size, and the C track's fix was a second parameter for the count.

Alice's line could live in a vector. Joining at the back is push_back, which is cheap. But serving from the front means erasing v.begin(), and a VIP means inserting there. Both shift every other customer by one box. Module 2's lesson 02 measured 100,000 front inserts on a vector at about a third of a second. So the week wants a fixed size that the type remembers, and the line wants two cheap ends.

The picture: a deque is blocks and a map

A deque (say "deck", short for double-ended queue) is a sequence that grows at both ends. It does not keep one long block like a vector. It keeps several small blocks of the same size. A short list of pointers, called the map, says which block comes first, second and third.

When the last block is full, push_back adds a new block after it. When the first block has no room in front, push_front adds a new block before it. Either way, no element moves. Only the map gets one more pointer. When a pop empties a block, the deque frees that block.

Now watch it move. Each step below is one call on the same deque. Look for a block arriving at the back, a block opening in front, and the two pops that free a block.

This picture uses 4 elements per block so that the crossings show. The real block on GCC 12 is 512 bytes, which holds 128 ints, and its library even sets up one block before the first push. Lesson 05 measures all of that. So a deque grows at the front by adding a block in front, and nothing already stored has to move.

The syntax you need on day one

#include <array>
#include <deque>

array<T, N> a{...};          N elements of T; N is fixed in the code
a[i]                          the element at index i, 0 to N - 1
a.size()                      N, always
a.at(i)                       like a[i], but checks i first
a == b                        true when every element is equal

deque<T> d;                   an empty deque of T
d.push_back(x);               add x at the back
d.push_front(x);              add x at the front
d.pop_back();                 remove the back element
d.pop_front();                remove the front element
d.front()   d.back()          the first and the last element
d[i]                          the element at index i, 0 to d.size() - 1
d.size()    d.empty()         how many, and whether there are none

So an array is declared with a type and a count, and a deque has a cheap push and pop at each end.

std::array: a C array that knows its size

A std::array keeps its elements in exactly the same boxes as a C array. The difference is in the type: the count is part of it. So a function that takes const array<int, 7>& receives the whole week, and size() still answers 7.

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

int goal_days(const array<int, 7>& steps) {
    int count = 0;
    for (int s : steps) {
        if (s >= 10000) {
            count++;
        }
    }
    return count;
}

int main() {
    array<int, 7> steps{3000, 4500, 12000, 8000, 12000, 2000, 6000};
    cout << "days: " << steps.size() << '\n';
    cout << "Wednesday: " << steps[2] << '\n';
    cout << "days at 10000 or more: " << goal_days(steps) << '\n';
    cout << "sizeof: " << sizeof(steps) << " bytes\n";
    return 0;
}

days: 7
Wednesday: 12000
days at 10000 or more: 2
sizeof: 28 bytes

The range-for inside goal_days works because the function still knows where the week ends. And sizeof is 28, the same as the C array: no hidden count is stored beside the elements. The 7 lives in the type, which the compiler knows, so it costs no memory at run time.

So a std::array is the same memory as a C array, with the count written into its type.

An array copies and compares

A C array cannot be copied with =. GCC 12 stops at b = a; with error: invalid array assignment, and == on two C arrays compares their addresses, not their boxes. A std::array behaves like an int here: = copies every element, and == compares every element.

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

int main() {
    array<int, 3> monday{5, 7, 9};
    array<int, 3> copy = monday;
    copy[0] = 100;
    cout << monday[0] << ' ' << copy[0] << '\n';
    cout << (monday == copy) << '\n';
    copy[0] = 5;
    cout << (monday == copy) << '\n';
    return 0;
}

5 100
0
1

Changing copy did not touch monday, so the copy was real. The comparison printed 0 (false) while one element differed and 1 (true) once all three matched. This is called value semantics: the array is one value, like a number. So pass it to a function by const& when you only read it, or a whole copy is made.

The size is part of the type

array<int, 7> and array<int, 8> are two different types, as different as int and double. A function written for a week will not take eight days. Bob tries it with goal_days from above.

array<int, 8> eight{};
cout << goal_days(eight) << '\n';

GCC 12 refuses: error: invalid initialization of reference of type 'const std::array<int, 7>&' from expression of type 'std::array<int, 8>'. That is a gift. A C function would have taken any int* and read past the end. So the compiler checks the count for you, and the count must therefore be known when the program is compiled.

deque: a line with two open ends

A vector is open at one end. A deque is open at both. This program replays the widget's eleven calls and prints the line after each group of them. Watch the values, not the blocks: the deque hides its blocks from you.

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

void show(const string& call, const deque<int>& d) {
    cout << call << ":";
    for (int x : d) {
        cout << ' ' << x;
    }
    cout << '\n';
}

int main() {
    deque<int> d;
    for (int x = 10; x <= 50; x += 10) {
        d.push_back(x);
    }
    show("five push_back", d);
    d.push_front(5);
    d.push_front(1);
    show("two push_front", d);
    d.pop_back();
    show("pop_back", d);
    d.pop_front();
    d.pop_front();
    show("two pop_front", d);
    return 0;
}

five push_back: 10 20 30 40 50
two push_front: 1 5 10 20 30 40 50
pop_back: 1 5 10 20 30 40
two pop_front: 10 20 30 40

The second push_front put 1 before 5, so the front is always the newest push_front. Like pop_back on a vector, both pops remove and return nothing. So a deque is a vector with a second door at the front.

Indexing still works

A deque keeps d[i], d.at(i) and d.size(), numbered from the front, 0 to d.size() - 1. A push_front renumbers everything: the old d[0] becomes d[1].

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

int main() {
    deque<int> d{20, 30, 40};
    cout << "d[0] = " << d[0] << ", size " << d.size() << '\n';
    d.push_front(10);
    cout << "d[0] = " << d[0] << ", d[1] = " << d[1] << ", size " << d.size() << '\n';
    for (size_t i = 0; i < d.size(); i++) {
        d[i] *= 2;
    }
    cout << "last: " << d[d.size() - 1] << '\n';
    return 0;
}

d[0] = 20, size 3
d[0] = 10, d[1] = 20, size 4
last: 80

Behind d[i], the deque works out which block holds element i, and which slot inside it. So a read costs two steps where a vector needs one. It is still a fixed amount of work, whatever the size. So index a deque as freely as a vector, and remember that the front moves.

The empty deque: Zara's first test

Zara always runs the empty case first. She asks an empty line who is at the front.

deque<int> line;
cout << "first in line: " << line.front() << '\n';

It compiled with no message at the runner's flags. On Compiler Explorer's GCC 12.2, in one run, it printed first in line: 0 and ended normally. That 0 is not a customer. front() on an empty deque is undefined behaviour: the standard says nothing about what happens, so a different day may print another number or crash. A quiet wrong 0 is the worst kind of answer. So check if (!line.empty()) before front(), back() or a pop.

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

int main() {
    array<string, 3> medals{"gold", "silver", "bronze"};
    for (size_t i = 0; i < medals.size(); i++) {
        cout << i + 1 << ": " << medals[i] << '\n';
    }
    return 0;
}

1: gold
2: silver
3: bronze

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

int main() {
    deque<int> d{20, 30};
    d.push_front(10);
    d.push_back(40);
    cout << "front " << d.front() << ", back " << d.back() << ", size " << d.size() << '\n';
    return 0;
}

front 10, back 40, size 4

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

int main() {
    deque<int> line;
    line.push_back(101);
    line.push_back(102);
    line.push_front(7);

    for (int turn = 1; turn <= 4; turn++) {
        if (line.empty()) {
            cout << "turn " << turn << ": nobody waiting\n";
        } else {
            cout << "turn " << turn << ": serving ticket " << line.front() << '\n';
            line.pop_front();
        }
    }
    return 0;
}

turn 1: serving ticket 7
turn 2: serving ticket 101
turn 3: serving ticket 102
turn 4: nobody waiting

int n;
cin >> n;
array<int, n> a{};

#include <iostream>
using namespace std;

int main() {
    array<int, 7> steps{};
    cout << steps.size() << '\n';
    return 0;
}

array<int, 7> week{};
array<int, 8> eight{};
week = eight;

deque<int> line;
line.pop_front();
cout << line.front() << '\n';

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

void c_week(int steps[7]) {
    cout << sizeof(steps) << '\n';
}

void std_week(const array<int, 7>& steps) {
    cout << sizeof(steps) << '\n';
}

int main() {
    int a[7] = {1, 2, 3, 4, 5, 6, 7};
    array<int, 7> b{1, 2, 3, 4, 5, 6, 7};
    c_week(a);
    std_week(b);
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const array<string, 7> days{"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};

    int w = 0;
    cin >> w;
    for (int week = 0; week < w; week++) {
        array<int, 7> steps{};
        for (int d = 0; d < 7; d++) {
            cin >> steps[d];
        }

        // Print this week's total, one space, and the name of the day
        // with the most steps (the earliest such day on a tie).
    }
    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    deque<int> row;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        // Odd x goes to the front of row, even x to the back.
    }

    // Print row from front to back, separated by single spaces.

    return 0;
}

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

int main() {
    const array<string, 7> days{"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
    int k;
    cin >> k;
    array<int, 7> steps{};
    for (int& s : steps) {
        cin >> s;
    }

    // For each start day, add k days in a row, wrapping after Sunday.
    // Keep the best total and its start day (the earliest on a tie).

    return 0;
}

Next, lesson 02 goes through every operation of both containers, one by one, each with its cost.