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