4  STL Containers I — vector, pair, and iterators

5 STL Containers I — vector, pair, and iterators

Week 1, Session 2. CSS 342.

5.1 Warmup

Find the Middle Index in Array (LeetCode #1991). Given a vector of integers, return the smallest index i such that the sum of elements to the left equals the sum to the right. Return -1 if there is none.

Spend ten minutes. Brute force is fine for a first cut.

class Solution {
 public:
  int findMiddleIndex(vector<int>& nums) {
    int total = 0;
    for (int n : nums) total += n;
    int leftSum = 0;
    for (int i = 0; i < (int)nums.size(); ++i) {
      // cout << "i=" << i << " left=" << leftSum
      //      << " right=" << total - leftSum - nums[i] << endl;
      if (leftSum == total - leftSum - nums[i]) return i;
      leftSum += nums[i];
    }
    return -1;
  }
};

One pass to compute total, one pass with leftSum running. O(n) time, O(1) extra space. The trick is realizing that rightSum = total - leftSum - nums[i]. If you brute-forced it with two nested loops, that is O(n²) — fine for correctness, but we will revisit complexity in Chapter 13 and you will want the O(n) version.

This warmup is doing double duty. We are practicing vector iteration and I am previewing a complexity argument we will not make rigorous until week 7. Most of the warmups in this book do the same — they teach something and they smuggle in something else.

5.2 Learning objectives

  1. Declare, populate, and traverse a std::vector using both range-based and iterator-based loops.
  2. Use std::pair to bundle two values and access each component.
  3. Apply swap, min, max, and reverse from <algorithm> to vector data.
  4. Articulate the difference between a range-based loop and an iterator loop, and choose appropriately.
  5. Trace through binary search on a sorted vector at a conceptual level (O(log n) preview).

5.3 std::vector — the workhorse

A vector is a dynamic array. It grows as you push to it, you index into it with [], and it knows its own size. If you only learn one STL container this quarter, this is the one. Realistically you will use it in every assignment.

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

int main() {
  vector<int> scores;          // empty
  scores.push_back(95);
  scores.push_back(82);
  scores.push_back(77);

  cout << "size: " << scores.size() << endl;
  cout << "first: " << scores[0] << endl;
  cout << "last: " << scores.back() << endl;

  scores[1] = 88;              // index-write
  cout << scores[1] << endl;
}

5.3.1 Construction shortcuts

vector<int> a;                       // empty
vector<int> b(5);                    // five zeros: [0,0,0,0,0]
vector<int> c(5, -1);                // five -1s:  [-1,-1,-1,-1,-1]
vector<int> d = {3, 1, 4, 1, 5, 9};  // init list
vector<int> e(d.begin(), d.end());   // copy of d
vector<vector<int>> grid(3, vector<int>(4, 0));  // 3×4 of zeros

The last one comes up constantly. Memorize the form.

5.3.2 Three ways to traverse

vector<int> v = {10, 20, 30, 40};

// 1. Index-based
for (int i = 0; i < (int)v.size(); ++i) {
  cout << v[i] << " ";
}

// 2. Range-based ("for each")
for (int x : v) {
  cout << x << " ";
}

// 3. Iterator-based
for (auto it = v.begin(); it != v.end(); ++it) {
  cout << *it << " ";
}

All three produce 10 20 30 40. They are not interchangeable, though:

  • Index when you need i. Common case: comparing v[i] to v[i-1], or modifying based on position.
  • Range-based when you only need the value and you are not modifying the vector during the loop.
  • Iterator when you need to call v.erase(it) or pass the iterator to an STL algorithm.

The size-cast. v.size() returns size_t, which is unsigned. Comparing it to a signed int with i < v.size() works but the compiler may warn. I cast to int explicitly: i < (int)v.size(). The textbook does not. Both are valid. Pick one and stick to it.

5.3.3 Modify by reference

If you want to modify each element in place, you need auto&:

for (auto& x : v) {       // note the &
  x *= 2;
}
// v is now {20, 40, 60, 80}

Without the & you modify a copy and lose the change. This is the most common range-for bug.

5.4 std::pair

A pair bundles two values of possibly different types. Access them as .first and .second.

#include <utility>      // for pair
#include <string>

pair<string, int> p("Alice", 95);
cout << p.first << ": " << p.second << endl;

auto q = make_pair("Bob", 88);   // type deduced

You will see pairs everywhere — sorted vectors of (name, score), BFS queues holding (row, col), return types like pair<int,int>. C++17 has structured bindings which let you unpack pairs cleanly:

auto [name, score] = p;
cout << name << " scored " << score << endl;

5.5 STL algorithms you should know on day one

#include <algorithm>

vector<int> v = {5, 2, 8, 1, 9, 3};

swap(v[0], v[5]);            // {3, 2, 8, 1, 9, 5}
int mn = *min_element(v.begin(), v.end());   // 1
int mx = *max_element(v.begin(), v.end());   // 9
reverse(v.begin(), v.end()); // reverses in place
sort(v.begin(), v.end());    // ascending

The pattern: STL algorithms take a range defined by begin() and end() iterators. The end is one past the last element. You can pass the whole vector by calling them with v.begin(), v.end(), or just a slice: sort(v.begin() + 2, v.end()) sorts everything from index 2 onward.

The two-iterator pattern is the STL’s single biggest design choice. Once you internalize it, every STL algorithm is the same shape: pass it a range, and it does the thing. I will repeat that point about thirty times this quarter.

5.6 Binary search — a preview

You will not implement binary search formally until Chapter 14. But here it is, because you will use it in the warmups before then:

int binarySearch(const vector<int>& v, int target) {
  int lo = 0;
  int hi = v.size() - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;          // <-- overflow-safe midpoint
    // cout << "lo: " << lo << ", hi: " << hi << ", mid: " << mid << endl;
    if (v[mid] == target) return mid;
    if (target < v[mid]) hi = mid - 1;
    else lo = mid + 1;
  }
  return -1;
}

Two things to commit to memory right now, even before we analyze them:

  1. mid = lo + (hi - lo) / 2 — not (lo + hi) / 2. The naive form overflows when lo + hi exceeds INT_MAX. The safe form does not. Every binary search in this book uses the safe form. You should too.
  2. lo <= hi, not lo < hi. With <= the loop terminates when the range is empty; with < it terminates one step early and you miss single-element ranges. There are valid binary-search variants that use < — they are just trickier. Start with <=.

Forgetting to subtract 1 when assigning to hi. hi = mid; looks innocent but causes infinite loops when the range has exactly two elements. Use hi = mid - 1; and lo = mid + 1;.

5.7 Try it

Given a vector v of integers, write a function that returns a new vector containing only the even-indexed elements (index 0, 2, 4…). Use a range-based for if you can. (You cannot — range-based does not give you the index. Use index-based.)

vector<int> evenIndexed(const vector<int>& v) {
  vector<int> result;
  for (int i = 0; i < (int)v.size(); i += 2) {
    result.push_back(v[i]);
  }
  return result;
}

For the brave: write the same function using only iterators (v.begin(), v.end(), it += 2). It works, and it is uglier than the index version. The index version is the right tool here.

5.8 Self-check

1. Which form prevents integer overflow when computing the midpoint of lo and hi?
c. Subtracting first keeps the intermediate value bounded by hi. The naive (lo + hi) / 2 overflows when both are near INT_MAX.
2. What does for (auto x : v) x *= 2; do?
b. Without &, x is a copy. To modify in place use for (auto& x : v).

5.9 Challenges

  1. Smallest Index With Equal Value (#2057) — vector traversal + modulo.
  2. Running Sum of 1d Array (#1480) — in-place vs. new vector.
  3. Build Array from Permutation (#1920) — nums[nums[i]] style indexing.
  4. Concatenation of Array (#1929) — push_back ritual.

5.10 Where this fits

You now have a container, a pair, and a way to loop over both. The next chapter introduces associative containers — set, map, and their unordered cousins — and the LIFO/FIFO containers stack and queue.

You are here Coming up
vector, pair, range/iterator loops, midpoint trick Chapter 3: sets, maps, stacks, queues, priority queues