5 STL Containers II — set, map, stack, queue

6 STL Containers II — set, map, stack, queue

Week 2, Session 1. CSS 342.

6.1 Warmup

Find All Duplicates in an Array (LeetCode #442). Given nums where every element is in [1, n] and each appears once or twice, return the elements that appear twice.

We will solve this two ways: first with unordered_set, then with the flip-sign trick that uses no extra memory.

// Approach 1: O(n) time, O(n) space
class Solution {
 public:
  vector<int> findDuplicates(vector<int>& nums) {
    unordered_set<int> seen;
    vector<int> result;
    for (int n : nums) {
      if (seen.count(n) == 1) result.push_back(n);
      else seen.insert(n);
    }
    return result;
  }
};

// Approach 2: O(n) time, O(1) extra space
class Solution {
 public:
  vector<int> findDuplicates(vector<int>& nums) {
    vector<int> result;
    for (int n : nums) {
      int idx = abs(n) - 1;             // value to index
      if (nums[idx] < 0) result.push_back(idx + 1);
      else nums[idx] = -nums[idx];      // mark visited
    }
    return result;
  }
};

The flip-sign approach is clever and trades clarity for space. In an interview, write the unordered_set version first because it is obvious. Then, when the interviewer asks “can you do it without the extra space?”, you have the flip-sign version ready. Knowing both is the right answer.

6.2 Learning objectives

Store and look up unique elements using set and unordered_set and explain the performance difference.
Insert, look up, and iterate key-value pairs using map and unordered_map.
Implement LIFO and FIFO access patterns using stack and queue.
Use priority_queue to always access the maximum (or minimum) element.
Select the appropriate STL container for a given problem constraint.

6.3 `set` vs. `unordered_set`

Both store unique elements with O(1) average insert/lookup… wait, no. Let us be precise.

	`set`	`unordered_set`
Underlying structure	Red-black tree (BST)	Hash table
Insert / find / erase	O(log n)	O(1) average, O(n) worst
Iteration order	Sorted	Unspecified
Memory overhead	Lower	Higher

#include <set>
#include <unordered_set>

set<int> s;                    // sorted set
s.insert(10);
s.insert(5);
s.insert(20);

if (s.count(10) == 1) cout << "10 is in s" << endl;

for (int x : s) cout << x << " ";    // 5 10 20 — sorted!

unordered_set<int> us = {10, 5, 20};
// for (int x : us) cout << x;  // 10 5 20 or 20 10 5 or...

s.count(x) returns 0 or 1. (For multiset it can be higher.) I use s.count(x) == 1 as the membership idiom — it reads cleanly and is consistent across set, unordered_set, map, unordered_map.

Calling s.find(x) != s.end() works too, but it is two iterator operations and harder to read. Stick with count.

6.4 `map` vs. `unordered_map`

Same tradeoff. map is sorted by key (O(log n)); unordered_map is hashed (O(1) average). Use unordered_map unless you specifically need keys in sorted order.

#include <map>
#include <unordered_map>

unordered_map<string, int> freq;
freq["the"] = 5;
freq["dog"] = 2;
freq["the"]++;          // freq["the"] is now 6

if (freq.count("cat") == 0) cout << "cat not seen" << endl;

6.4.1 Iterating a map

for (const auto& [word, count] : freq) {        // C++17 structured binding
  cout << word << " -> " << count << endl;
}

Pre-C++17 you would write const auto& p : freq then access p.first and p.second. The structured-binding form is cleaner. Use it.

operator[] on a map has a subtle behavior: if the key is not there, it inserts a default-constructed value and returns a reference. So if (freq["cat"] > 0) actually adds "cat" to the map with value 0. Use count to check first.

6.4.2 Word frequency in eight lines

#include <unordered_map>
#include <iostream>
#include <sstream>
using namespace std;

int main() {
  string sentence = "the dog and the cat and the bird";
  unordered_map<string, int> freq;
  stringstream ss(sentence);
  string word;
  while (ss >> word) freq[word]++;
  for (const auto& [w, c] : freq) cout << w << ": " << c << endl;
}

That stringstream pattern (stringstream ss(s); while (ss >> word)) tokenizes by whitespace without any manual index tracking. Internalize it.

6.5 `stack` — LIFO

A pile of plates. Push on top, pop from top, peek at top.

#include <stack>

stack<int> stk;
stk.push(1);
stk.push(2);
stk.push(3);

cout << stk.top() << endl;   // 3
stk.pop();
cout << stk.top() << endl;   // 2

top() returns the top element; pop() removes it but does not return it. So the read-and-remove idiom is two calls:

int x = stk.top();
stk.pop();

A classic stack problem is balanced parentheses:

bool balanced(const string& s) {
  stack<char> stk;
  for (char c : s) {
    if (c == '(') stk.push(c);
    else if (c == ')') {
      if (stk.empty()) return false;
      stk.pop();
    }
  }
  return stk.empty();
}

6.6 `queue` — FIFO

A waiting line. Push at the back, pop from the front.

#include <queue>

queue<int> q;
q.push(1);
q.push(2);
q.push(3);

cout << q.front() << endl;   // 1 (oldest)
q.pop();
cout << q.front() << endl;   // 2

Queues power breadth-first search (BFS), which we will see in Chapter 26. For now, here is the most common queue-based pattern — counting steps in a grid:

// Watering Plants flavored example: count steps to water n plants, returning
// to the well whenever you run out.
int waterPlants(const vector<int>& plants, int capacity) {
  int steps = 0;
  int water = capacity;
  for (int i = 0; i < (int)plants.size(); ++i) {
    if (water < plants[i]) {
      steps += i + i;          // walk back, walk forward
      water = capacity;
    }
    water -= plants[i];
    steps += 1;
  }
  return steps;
}

That problem does not actually need a queue — but it has the same “process in order” rhythm that queues impose. Once you see the rhythm, it appears everywhere.

6.7 `priority_queue` — heap-backed

A queue where the highest-priority element comes out first. By default it is a max-heap — the largest element is top().

#include <queue>

priority_queue<int> pq;
pq.push(3);
pq.push(7);
pq.push(1);

cout << pq.top() << endl;     // 7
pq.pop();
cout << pq.top() << endl;     // 3

For a min-heap (smallest on top), use greater<int>:

priority_queue<int, vector<int>, greater<int>> minPq;

That declaration is ugly. Memorize it anyway — you will use it constantly in graph algorithms and “K-largest” problems.

The first time you see priority_queue<int, vector<int>, greater<int>> you will think C++ hates you. By the time you get to Dijkstra in Chapter 27 you will type it without thinking. That is the entire arc of learning C++ — what was painful in week 2 is muscle memory by week 10.

6.8 Container selection — the rough rule

Need	Use
Sequence, indexed access	`vector`
Unique elements, fast lookup	`unordered_set`
Unique elements, sorted	`set`
Key → value, fast lookup	`unordered_map`
Key → value, sorted by key	`map`
LIFO	`stack`
FIFO	`queue`
Repeatedly take min or max	`priority_queue`

When in doubt, start with vector or unordered_map. They cover 80% of cases. Reach for set/map when you need sorted iteration, and priority_queue when you need only the extreme element.

6.9 Try it

Given a vector of strings, return the words that appear more than once. Use unordered_map<string,int> to count, then a second pass to collect repeats.

vector<string> duplicates(const vector<string>& words) {
  unordered_map<string, int> freq;
  for (const auto& w : words) freq[w]++;
  vector<string> result;
  for (const auto& [w, c] : freq) {
    if (c > 1) result.push_back(w);
  }
  return result;
}

If you wanted them in alphabetical order, you would use map<string,int> instead.

6.10 Self-check

1. You need to look up whether a string is in a collection of 10 million strings. Order does not matter. Which container?

a. vector<string> with linear scan
b. unordered_set<string>
c. set<string>
d. stack<string>

b. O(1) average lookup beats O(log n) when you do not need sorted order. Vector is O(n) per query.

2. What does freq["cat"] do when freq is an unordered_map<string,int> and "cat" is not present?

a. Throws an exception.
b. Returns -1.
c. Inserts "cat" with value 0 and returns a reference to that value.
d. Compile error.

c. This is why "check first with count" matters — accidentally inserting empty keys is a common bug.

6.11 Challenges

Two Sum (#1) — unordered_map for O(n).
Valid Parentheses (#20) — classic stack.
Top K Frequent Elements (#347) — unordered_map + priority_queue.
Number of Recent Calls (#933) — queue.

6.12 Where this fits

You now have a vocabulary for the right container at the right time. The next chapter cracks open the box: how do these containers actually allocate memory, and what does it mean when something is a pointer?

You are here	Coming up
`set`/`map`/`stack`/`queue`/`priority_queue`, container selection	Chapter 4: pointers, references, `new`/`delete`, the heap