Which Container Answers Your Next Question?

Alice has three jobs before the library opens. Returns must leave in arrival order. A shelf report needs alphabetical totals. A repair desk always takes the most urgent job. All three jobs store records, but their next questions differ.

Ask the same four questions

A container holds values and promises costs for certain operations. A pattern combines operations with a rule that keeps them correct. This module joins the containers you already know. It starts with questions, because choosing a name first hides the actual work.

Module 2 asked four questions. First, is the data a sequence, or do you look it up by key? Second, do you read by position, or search by value? Third, where does it grow and shrink? Fourth, how large is the collection, and how large is one element?

Keep all four answers on paper. One answer can outweigh another. A sorted sequence still needs expensive shifts when insertions happen throughout it. A linked list supports cheap insertion only after you already hold the place. Looking for that place still takes work.

The word invariant means a fact your program keeps true after each change. For a queue, arrival order remains intact. For a sorted vector, values remain in order. When choosing a container, name both the invariant and the operation you need next.

Sequence, key, or a restricted exit

A sequence keeps positions meaningful. Start with vector when you append, index, and scan small values. Choose array when its size belongs to the type. Choose string for a sequence of characters. Its byte positions do not automatically become human language character positions.

Deque supports both ends and indexing. It suits a line that gains customers at the back and loses them at the front. List suits changes around known iterators and moving whole linked ranges. It does not offer fast access to the middle by index.

A container adaptor exposes a restricted set of operations over another container. Stack exposes the newest item. Queue exposes the oldest. Priority_queue exposes an extreme according to its comparison rule. That restriction can express your algorithm's promise more clearly than a larger interface.

Do not choose priority_queue when you need an arbitrary key next. Its top is cheap, but searching inside is not its job. Do not choose stack just because the story has a pile. The departure rule, rather than the picture in the story, decides the useful interface.

Ordered keys, duplicates, and stored values

Set stores unique keys in sorted order. Multiset keeps repeated keys too. Map associates each unique key with a value. Multimap permits several entries with equivalent keys. All four support ordered searching, so asking for the next key makes sense.

The unordered forms use hashing. Unordered_set and unordered_multiset store keys; unordered_map and unordered_multimap also store mapped values. Their normal lookup cost is average constant time. Their worst case is linear, and their iteration order is not a sorted report.

The decision about duplicates comes from the statement. Two tickets with the same price remain two tickets. Two sightings of the same book may describe one distinct book. Losing a duplicate can change the answer even when the program still prints a plausible number.

When all values arrive before the questions, a sorted vector deserves another look. Sorting once can buy binary search and cheap indexing afterward. When values change between questions, set or map may fit better. Sorted storage is useful, but sorted storage alone does not provide fast rank queries.

Size and representation finish the choice

Bitset stores a fixed number of binary answers. A plain integer mask can represent a small fixed collection. Vector<bool> offers a runtime length of packed flags, with special reference behaviour. None replaces a map when the keys are sparse labels with associated records.

Pair and tuple group fields into one value. They are not replacements for the outer container. A priority_queue of pairs can choose the smallest distance, then the smallest node number. A vector of pairs can hold roads. The two layers answer different questions.

Large records deserve care. Moving a small index can be cheaper than moving a long record repeatedly. Keep records in stable storage when their identities must survive reordering. Then sort a vector of indexes, provided later changes do not invalidate the storage those indexes describe.

Also estimate the total memory, including overhead. A million linked nodes cost more than their payload alone. A vector may reserve spare capacity. An adjacency list contains many inner vectors. These costs are reasons to inspect constraints, not reasons to reject a container without measuring its workload.

Route three small jobs

For library returns, Alice answers: sequence, oldest first, back arrivals, front removals. Queue expresses that exit rule. If staff must also inspect both ends, deque becomes useful. The record count changes at runtime, so array is not the natural starting choice.

For alphabetical shelf totals, Maria answers: look up by shelf name, update a count, print keys in order. Map<string,int> fits those requirements. If the report is rare, an unordered_map plus a sorted key list is another design. Its extra sorting must appear in the cost.

For the repair desk, David answers: repeatedly take the smallest promised completion time. A min-priority_queue fits when only the next job matters. Cancellation adds another requirement. Then keep current records by id and discard stale heap entries when they surface, as Module 7 introduced.

These routes are not proofs of every future algorithm. A new requirement can change the answer. Sliding windows need expiry as well as an extreme. Dijkstra needs a current distance table as well as a heap. Later lessons add those invariants without changing the four starting questions.

queue<int> returns;             // Oldest first.
map<string, int> shelfCount;     // Key lookup and sorted reporting.
priority_queue<int> urgency;     // Largest currently waiting value.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> returns;
    for (int id : {8, 3, 8}) returns.push(id);
    while (!returns.empty()) {
        cout << returns.front() << '\n'; returns.pop();
    }
}

8
3
8

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
    map<string,int> count;
    for (string shelf : {"Z", "A", "Z"}) ++count[shelf];
    for (const auto& [shelf, n] : count) cout << shelf << ' ' << n << '\n';
}

A 1
Z 2

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> jobs;
    for (int x : {4, 9, 4}) jobs.push(x);
    while (!jobs.empty()) { cout << jobs.top() << '\n'; jobs.pop(); }
}

9
4
4

Follow the labelled branch for the operation you actually require. The final row revisits size and payload, rather than treating them as optional questions.

The deque stores indexes. A partial window has no reported maximum. Lesson 02 explains why some active indexes can disappear before they expire.

#include <list>
#include <iostream>
int main() { std::list<int> a{7,8}; std::cout << a[1]; }

#include <queue>
int main() { std::queue<int> q; q.push(3); int x=q.pop(); return x; }

3
2 1 2
2 2 1

0 0 1

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n), b(n);
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;
    // Compare all three complete departure orders.
}

5
4 4 1 4 4

#include <iostream>
#include <vector>
using namespace std;
int main() { int n; cin>>n; vector<int> a(n); for(int& x:a) cin>>x;
    // Count adjacent equal pairs without reordering the sequence.
}

2

6
4 1 4 2 2 4

#include <iostream>
#include <vector>
using namespace std;
int main() { int n; cin>>n; vector<int> a(n); for(int& x:a) cin>>x;
    // Report how many different labels repeat at least twice.
}

2

Next, maintain a moving window without rescanning its contents.