Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

C++ for DSA

Editorial

A few containers, and the one slow move in each

A data-structures solution in C++ leans on a handful of containers from the standard library: vector, string, unordered_map and unordered_set, deque, priority_queue, and map and set. C++ is the fastest of the four judge languages, and each container is still slow at one thing that looks harmless. On our judge, erasing the front of a vector of 100,000, one at a time, took 383 ms; a deque did it in 0.1 ms. Searching a vector of 100,000 with find, 10,000 times, took 305 ms; an unordered_set answered in 0.7 ms.

This lesson covers each container's fast moves and its slow one, then the traps C++ hides in its types, passing by reference, the stack, input and output, and what the judge runs: g++ 10.2, C++17.

Six dashed panels in two rows, each a C++ container drawn as the shape of its data, with a green pill for its fast move and a red pill for its slow one. Vector: tiles 5, 3, 8, 1 and an empty slot at the end with an arrow into it; end: 1 step, front: shifts all. String: tiles c, o, d, e and an empty slot at the end; +=: 1 step, s = s + c: copies. Unordered_map: keys the and cat pointing to 2 and 1; lookup: 1 step, m[k]: inserts k. Deque: tiles 2, 3, 4 with arrows into both ends; both ends: 1 step, middle: shifts. Priority_queue: a small heap of 5 over 2 and 4, with 1 below; push, pop: log n, no find at all. Map and set: a small search tree of 31 over 25 and 40, with 20 below 25; lower_bound: log n, every op: log n. Focal line: know the slow move before it costs a submission. Title: each container has one slow move.

The shape of a solution

A program is one file: #include <bits/stdc++.h> brings in the whole standard library, using namespace std; saves the std:: prefixes, helpers go above main, and containers go into a helper by const reference, so they aren't copied:

#include <bits/stdc++.h>
using namespace std;

int sum(const vector<int>& nums) {          // helpers above main; containers by const reference
    int total = 0;
    for (int x : nums) total += x;
    return total;
}

int main() {
    vector<int> nums = {5, 3, 8};
    cout << sum(nums) << " " << nums.size() << "\n";
}

From here on, most blocks show only what goes inside main; the lines around it are the same as above.

vector: cheap at the end, slow at the front

A vector is one row of slots: reading by index and adding or removing at the end take one step, and inserting or erasing at the front moves every value. A grid is a vector of vectors, built with a size and a starting value for each row:

vector<int> nums = {5, 3, 8};
nums.push_back(1);                          // at the end: O(1)
int last = nums.back();
nums.pop_back();                            // from the end: O(1)
nums.insert(nums.begin(), 9);               // at the front: every value moves, O(n)
int first = nums.front();
nums.erase(nums.begin());                   // O(n) again
cout << last << " " << first << " " << nums.size() << " " << nums[1] << "\n";
vector<vector<int>> grid(2, vector<int>(3, 0));   // 2 rows of 3 zeros, each row its own vector
grid[0][1] = 7;
cout << grid[0][1] << " " << grid[1][1] << "\n";

Erasing the front 100,000 times took 383 ms. When a job needs the front, use a deque.

string: you can change it, so += is cheap

Unlike Python's and Java's, a C++ string can change in place: s[0] = 'm' works, and s += c appends at the end in one step on average. What copies is building a new string from an old one, s = s + c, which copies all of s every time:

string s = "code";
cout << s[0] << " " << s.back() << " " << s.substr(1, 2) << " " << s.size() << "\n";
s[0] = 'm';                                 // a string can change in place
s += 's';                                   // and grows at the end: O(1) on average
cout << s << "\n";
cout << ('c' - 'a') << " " << char('a' + 2) << "\n";   // letters as numbers and back
string t = "mode";
t += "s";
cout << (s == t) << "\n";                   // == compares the letters

For 100,000 letters, s += 'a' took 0.2 ms and s = s + 'a' took 565 ms.

unordered_map and unordered_set

Both hash their keys, so adding, finding and erasing take one step on average. count[w]++ counts, because a missing key starts at 0; count(key) and find(key) ask without adding anything; and insert on a set returns whether the value was new:

vector<string> words = {"the", "cat", "and", "the", "hat"};
unordered_map<string, int> count;
for (const string& w : words) count[w]++;   // a missing key starts at 0
cout << count["the"] << " " << count.count("dog") << " " << count.size() << "\n";
unordered_set<string> seen;
vector<string> repeats;
for (const string& w : words)
    if (!seen.insert(w).second) repeats.push_back(w);   // .second is false when it was already there
cout << repeats.size() << " " << repeats[0] << "\n";

That [] adds a missing key is useful for counting and a trap for asking: the bugs section shows a map that grows from a lookup. As a table fills, it rehashes into a bigger one; reserve(n) sizes it once. 2,000,000 inserts took 188 ms without reserve and 97 ms with it.

deque, stack and queue

deque is open at both ends and still indexable, all in one step. stack and queue are narrower faces on top of it: push, pop and top for a stack, push, pop, front and back for a queue. Their pop returns nothing, so read the value first:

deque<int> d = {2, 3, 4};
d.push_front(1);
d.push_back(5);
cout << d.front() << " " << d.back() << " " << d[2] << "\n";   // both ends and an index: O(1)
stack<int> st;
for (int x : {1, 2, 3}) st.push(x);
cout << st.top() << " ";
st.pop();
cout << st.top() << "\n";
queue<int> q;
for (int x : {1, 2, 3}) q.push(x);
cout << q.front() << " " << q.back() << "\n";

priority_queue: the largest on top

priority_queue is a heap, and in C++ it puts the largest on top, the opposite of Python's heapq and Java's PriorityQueue. Give it greater<int> for the smallest first. Pairs compare by their first value, then their second, which breaks ties:

priority_queue<int> largest;                // a max-heap: the largest on top
for (int x : {5, 1, 4, 2}) largest.push(x);
cout << largest.top() << "\n";
priority_queue<int, vector<int>, greater<int>> smallest;   // greater<int>: the smallest on top
for (int x : {5, 1, 4, 2}) smallest.push(x);
smallest.pop();
cout << smallest.top() << "\n";
vector<string> names = {"email", "deploy", "lunch"};
vector<int> priority = {2, 1, 2};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> jobs;   // (priority, arrival)
for (int i = 0; i < 3; i++) jobs.push({priority[i], i});
while (!jobs.empty()) {
    cout << names[jobs.top().second] << (jobs.size() > 1 ? " " : "\n");
    jobs.pop();
}
Three dashed panels, each a heap after pushing 5, 1, 4 and 2, drawn as a tree with its top ringed. Left, titled C++ default, priority_queue<int>: 5 on top over 2 and 4, with 1 below 2; a pill reads top: 5. Middle, titled Python and Java, heapq, PriorityQueue: 1 on top over 2 and 4, with 5 below 2; top: 1. Right, titled C++ flipped, greater<int>: the same tree as the middle, top: 1. Under them: the same four pushes, only the comparison decides which end is on top. Focal line: for the smallest first in C++, add greater<int>. Title: priority_queue faces the other way.

map and set: sorted, with lower_bound

map and set keep their keys in order in a balanced tree, so every operation takes O(log n), and they answer what a hash map can't: lower_bound(x) is the first key at or above x, upper_bound(x) the first above it, and prev steps back one. When nothing qualifies, they return end():

map<int, string> byAge = {{25, "bo"}, {31, "ana"}, {40, "cy"}};
auto it = byAge.lower_bound(30);            // the first key at or above 30
cout << it->first << " " << prev(it)->first << " " << byAge.begin()->first << "\n";
set<int> ages = {25, 31, 40};
cout << *ages.upper_bound(31) << " " << (ages.lower_bound(41) == ages.end()) << "\n";

Sorting with comparators

sort takes a comparator that answers "does a go before b?", and it must say no for equal values: <, never <=, or the sort's behaviour is undefined. sort isn't stable; stable_sort keeps equal items in their order. On a sorted vector, lower_bound finds a position in O(log n):

vector<pair<string, int>> people = {{"ana", 31}, {"bo", 25}, {"cy", 31}};
stable_sort(people.begin(), people.end(),
            [](const auto& a, const auto& b) { return a.second < b.second; });   // strictly less, never <=
for (const auto& [name, age] : people) cout << name << " ";
cout << "\n";
sort(people.begin(), people.end(), [](const auto& a, const auto& b) {
    if (a.second != b.second) return a.second > b.second;   // age high to low
    return a.first < b.first;                               // then by name
});
for (const auto& [name, age] : people) cout << name << " ";
cout << "\n";
vector<int> nums = {5, 3, 8, 1};
sort(nums.begin(), nums.end());
cout << lower_bound(nums.begin(), nums.end(), 5) - nums.begin() << "\n";   // the index of the first >= 5

Numbers: overflow, unsigned sizes and the start of a sum

Overflowing an int is undefined in C++: the program may print a wrapped number or do something stranger. Widen before you multiply with 1LL * n * n. / and % cut towards zero. Two traps hide in the types the library picks. size() is unsigned, so on an empty vector size() - 1 isn't -1, it wraps to the largest 64-bit value. And accumulate adds in the type of its start value, so start with 0LL for a big sum:

int n = 100000;
cout << 1LL * n * n << "\n";                // widen first: n * n alone overflows int
cout << -7 / 2 << " " << -7 % 2 << "\n";    // both cut towards zero
vector<int> empty;
cout << empty.size() - 1 << "\n";           // size() is unsigned: 0 - 1 wraps around
vector<int> big(100000, 1000000000);
cout << accumulate(big.begin(), big.end(), 0LL) << "\n";   // 0LL: the sum is a long long
cout << INT_MAX << " " << LLONG_MAX << "\n";
Top panel, titled int: 0 − 1: a number line from −2 to 2 with a green arrow from 0 back to −1 and a pill reading −1, as expected. Middle panel, titled size_t: 0 − 1: a number line from 0 to max, with a dashed red arrow leaving 0 and coming down at max, under a pill reading 18,446,744,073,709,551,615. Below, a crossed card reads i < v.size() - 1, on an empty vector: runs (almost) forever; a ticked card reads i + 1 < v.size(), on an empty vector: stops before the first step. Focal line: never subtract from a size: add to the index instead. Title: size() − 1 wraps around.

Pass containers by reference

A parameter of type vector<int> gets its own copy of the vector, every call. const vector<int>& reads the caller's, and vector<int>& can change it. A helper called once per cell of a grid with the grid passed by value is a classic timeout. 100,000 calls with a 10,000-value vector took 105 ms by value and under 0.1 ms by reference.

Recursion: the judge's stack is deep

On our judge, a depth-first search down a chain of 2,968,750 nodes finished, and one of 3,250,000 was stopped for using too much memory, the lists for the chain included. That's deep enough for any input here. Other judges and real programs give a thread far less, often a few megabytes, so a recursion as deep as the input is still worth turning into a loop with an explicit stack when the input can be long: Depth-First and Breadth-First Search shows how.

Input and output

cin and cout keep in step with C's scanf and printf unless you tell them not to, and cin flushes cout before every read. Two lines at the top of main turn both off. endl writes a newline and then flushes; '\n' just writes the newline:

ios::sync_with_stdio(false);                // stop keeping cin in step with C's scanf
cin.tie(nullptr);                           // and stop flushing cout before every read
int n;
cin >> n;
long long total = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    total += x;
}
cout << total << '\n';                      // '\n', not endl: endl flushes on every line

Reading 1,000,000 numbers took 151 ms as cin comes and 58 ms with the two lines. Printing 300,000 lines took 567 ms with endl and 24 ms with '\n'.

Pick the container for the job

Below, each job is a mix of operations repeated 100,000 times. Pick the C++ container you'd use; each operation's cost appears with the total work for the whole job, and every container you try keeps its verdict, so you can compare them.

Which Collection? C++

Bugs that cost a submission

A sum that starts as an int.

vector<int> big(100000, 1000000000);
cout << accumulate(big.begin(), big.end(), 0) << "\n";   // the 0 is an int, so the sum is an int

It printed 276447232, not 100,000,000,000,000: with a start value of 0, every step adds in int, which overflows. Start with 0LL.

A lookup that adds keys.

unordered_map<string, int> stock = {{"cat", 1}};
for (string w : {"dog", "eel", "fox"})
    if (stock[w] > 0) cout << w;            // reading with [] inserts w, at 0
cout << stock.size() << "\n";

It printed 4: each stock[w] added w with the value 0, so three lookups grew the map from 1 key to 4. Ask with count or find.

A loop to size() - 1 on an empty vector.

vector<int> v;                              // empty
long long runs = 0;
for (size_t i = 0; i < v.size() - 1; i++)  // 0 - 1 is 18,446,744,073,709,551,615
    if (++runs == 1000000) break;           // without this, it would run for centuries
cout << runs << "\n";

It ran until the guard stopped it, 1,000,000 times, and would have gone on for centuries: v.size() - 1 is 18,446,744,073,709,551,615 when v is empty. Write i + 1 < v.size(), or check for empty first.

A priority_queue expected to give the smallest.

priority_queue<int> pq;
for (int x : {5, 1, 4}) pq.push(x);
cout << pq.top() << "\n";                   // expected the smallest

It printed 5. Declare it with greater<int>, as in the priority_queue section.

Check yourself

Quiz

1 / 6

Multiple choice

You push 5, 1 and 4 into priority_queue<int> pq. What is pq.top()?

Practice problems

This section's problems, in C++:

  1. Reading & Printing Values: cin with the two fast lines.
  2. Linear Search and Check if an Array is Sorted: a vector by index.
  3. Reverse an Array In Place: two indices and swap.
  4. Count Vowels and Consonants and Toggle Case: a string changed in place.
  5. Count Words in a Sentence: words into an unordered_map.
  6. C++ Standard Library Overview: the containers above, side by side.

Then Introduction to Recursion, before the patterns.