Chapter 18 · Iterators and Algorithms
Exercise · Chapter 18

Chapter 18 — Iterators and Algorithms: VecTools

You are completing vectools, a small library that performs five common operations on std::vector<int>. For each operation you implement two versions that must agree on every input:

  • A hand* version that walks the vector with an explicit iterator loop — you write the begin()/end()/++it/*it machinery yourself so you see the abstraction in full.
  • An algo* version that delegates to a standard <algorithm> (std::find, std::count_if, std::sort, std::max_element), passing a free-function predicate or comparator.

The grader confirms that both versions agree, so a mismatch in either direction is caught immediately. The "two ways, same result" structure is the lab's physical demonstration of Chapter 18's central lesson: the standard library algorithms are not magic — they run the same iterator loop you would have written by hand, just packaged with a name.

Why free functions, not lambdas? Lambdas are the natural next step as predicates, but they are introduced in Chapter 20. The Chapter 18 way is a plain free function whose address decays to a function pointer:

C++
bool isEven(int n) { return n % 2 == 0; }
std::count_if(v.begin(), v.end(), vectools::isEven);  // function pointer

This is also historically how all C++ algorithm predicates worked before C++11. Lambdas will make this more concise in Chapter 20; for now, the free-function form is what you use.

Your tasks

The starter compiles and runs immediately (make build is green), but every function returns a wrong placeholder, so make test is RED. Fill in the >>> YOUR CODE HERE <<< blocks in starter/vectools.cpp. Each task label below maps 1:1 to a TASK block in the starter:

Task 1a — isEven(n) — return true iff n is divisible by 2. This is the predicate passed by name to std::count_if in Task 3b. Negative numbers count too: isEven(-4) == true.

Task 1b — greaterThan(a, b) — return true iff a > b. This is the comparator passed by name to std::sort in Task 4b. Use strictly > — not >=: equal elements must not claim to come before each other (strict-weak-ordering rule; violating it is undefined behaviour in std::sort).

Task 2a — handFind(vec, target) — search vec for target using an explicit iterator loop; return the 0-based index of the first match, or -1 if not found. Write the loop with auto it { vec.begin() }; … ++it; *it. Convert the winning iterator to an index with std::distance(vec.begin(), it). Do NOT call any <algorithm>.

Task 2b — algoFind(vec, target) — same contract as handFind; implement by calling std::find(vec.begin(), vec.end(), target). The returned iterator must be checked against vec.end() before dereferencing (notes 18.2).

Task 3a — handCountEven(vec) — count even elements using an explicit iterator loop; test *it % 2 == 0; tally manually. Do NOT call any <algorithm>.

Task 3b — algoCountEven(vec) — same contract; call std::count_if(vec.begin(), vec.end(), vectools::isEven). Pass the free function isEven (no lambdas — Chapter 20). Cast the std::ptrdiff_t return to int.

Task 4a — sortAscending(vec) — sort the vector in ascending order using std::sort(vec.begin(), vec.end()). The default comparator uses operator<.

Task 4b — sortDescending(vec) — sort descending by calling std::sort(vec.begin(), vec.end(), vectools::greaterThan). Pass the free function greaterThan as the comparator.

Task 5 — largest(vec) — return the largest element, or 0 for an empty vector. Call std::max_element(vec.begin(), vec.end()). Guard the empty-range trap: the returned iterator equals vec.end() when the vector is empty — dereferencing it is undefined behaviour. Check first; return the 0 fallback.

You do not edit vectools.h or tests/tests.cpp — only starter/vectools.cpp.

Success criteria

  • isEven and greaterThan are tested directly before being used in algorithms.
  • handFind / algoFind are checked against each other (they must agree on every input), and edge-tested: empty vector, single element, duplicates (first occurrence wins), target absent.
  • handCountEven / algoCountEven are cross-checked: all-even, all-odd, empty, single element, negative numbers (-4 is even).
  • sortAscending / sortDescending are checked element-by-element: already-sorted input, all-same elements, single element, empty vector.
  • largest handles: normal case, single element, empty vector (must return 0, not crash), all-same, all-negative, mixed signs.
Concepts practiced
  • Iterator objects — begin(), end(), dereference *it, advance ++it, sentinel test it != end() (notes 18.2)
  • Half-open range [begin, end) — begin() is valid, end() must not be dereferenced (notes 18.2)
  • std::find — searches a range; returns an iterator or end() (notes 18.3)
  • std::count_if — counts predicate matches using a free-function predicate (notes 18.3)
  • std::sort — default ascending and custom descending via a free-function comparator; strict-weak-ordering rule (notes 18.3)
  • std::max_element — returns an iterator; empty-range guard required. max_element itself is not in the note; the iterator-return + end()-guard pattern it shares with std::find is (notes 18.2)
  • Function pointers as predicates/comparators — free functions passed by name to algorithms (Chapter 18 scope; lambdas arrive Chapter 20)
  • std::distance — converts an iterator to an index (Chapter 18 / 17 pointer arithmetic)
  • Reused from earlier chapters: std::vector construction and .begin()/.end() (Ch 16), const references and pass-by-ref (Ch 12), namespaces and header/source split (Ch 2), for loops (Ch 8)
Constraints

Allowed: std::vector, iterator objects (.begin(), .end(), ++it, *it, it != end), <algorithm> algorithms, std::distance, free-function predicates and comparators, everything from Chapters ≤ 18.

Required idioms:

  • handFind and handCountEven must use explicit iterator loops — no <algorithm> inside those two functions.
  • algoCountEven must pass vectools::isEven as the predicate (a free function pointer).
  • sortDescending must pass vectools::greaterThan as the comparator.
  • largest must guard the empty-range case before dereferencing std::max_element's return value.

Forbidden (not taught yet):

  • Lambdas — Chapter 20. Use free functions (isEven, greaterThan) instead.
  • std::function — Chapter 20.
  • C++20 ranges (std::ranges::sort, etc.) — out of scope here.
  • new/delete — Chapter 19.
Build & run locally
shell
make            # compile-check starter/vectools.cpp  (warning-clean)
make test       # grade your code against the unit tests  <-- the main goal
make solution   # run the grader against the reference if you get stuck
make test-solution   # verify the reference solution (must be green)
make clean      # remove build artefacts
Hints
Tasks 1a & 1b — isEven and greaterThan

Both are one-liners:

C++
bool isEven(int n)   { return n % 2 == 0; }
bool greaterThan(int a, int b) { return a > b; }

The greaterThan placeholder returns false for everything, so sortDescending will leave the vector in its original order — a clear test failure.

Tasks 2a & 3a — the iterator loop (handFind, handCountEven)

The canonical iterator loop from notes 18.2:

C++
for (auto it { vec.begin() }; it != vec.end(); ++it)
{
    // *it is the current element
}

For handFind, once *it == target, convert to an index:

C++
return static_cast<int>(std::distance(vec.begin(), it));

std::distance counts the steps from begin to it — for a std::vector iterator this is O(1) because vector iterators support random access.

Task 2b — checking the std::find iterator before using it (algoFind)
C++
auto it { std::find(vec.begin(), vec.end(), target) };
if (it == vec.end())
    return -1;                   // not found — do NOT dereference here
return static_cast<int>(std::distance(vec.begin(), it));

Always check it != vec.end() before writing *it. Dereferencing end() is undefined behaviour — the iterator points one past the last element, not at any real value (notes 18.2).

Task 3b — passing a free function to std::count_if
C++
int algoCountEven(const std::vector<int>& vec)
{
    return static_cast<int>(
        std::count_if(vec.begin(), vec.end(), vectools::isEven));
}

vectools::isEven decays to a bool(*)(int) function pointer. That is the Chapter 18 predicate form — lambdas ([](int n){ return n%2==0; }) do the same thing but aren't introduced until Chapter 20.

Task 1b — strict-weak-ordering in the comparator (greaterThan)

std::sort requires the comparator to be a strict weak ordering: comp(x, x) must always return false (irreflexivity). Using >= breaks this: when a == b, a >= b is true, meaning a claims to come before b and b claims to come before a simultaneously. That contradiction gives std::sort undefined behaviour.

Use strictly >:

C++
bool greaterThan(int a, int b) { return a > b; }

When a == b, a > b is false — neither claims priority. Correct.

Task 5 — the empty-range guard for std::max_element (largest)
C++
int largest(const std::vector<int>& vec)
{
    auto it { std::max_element(vec.begin(), vec.end()) };
    if (it == vec.end())
        return 0;    // empty range — fallback; do NOT dereference
    return *it;
}

When vec is empty, vec.begin() == vec.end() and std::max_element returns vec.end() immediately. The placeholder return 0 is accidentally correct for the empty case but wrong for everything else — the grader has non-empty cases that will still fail.

Stretch goals
  • Add handMin and algoMin (using std::min_element) and test them the same way. Reinforce the empty-range guard.
  • Add algoContains(vec, target) returning bool, implemented with std::find. Once you have it, observe that handFind(v, t) != -1 is equivalent — exactly what the standard library's std::ranges::contains (C++23) does under the hood.
  • Add handFindIf and algoFindIf using std::find_if with a free-function predicate of your choice. This previews std::find_if from notes 18.3.
  • Add a printAll(vec) that uses a range-based for loop (Ch 16) — then rewrite it as std::for_each with a free function, and compare readability. Notes 18.3 addresses when std::for_each adds value vs. when a plain loop is clearer.
  • Once you reach Chapter 20 (lambdas), rewrite algoCountEven and sortDescending to use inline lambda predicates instead of free functions. Notice that the call sites become single self-contained expressions — that is the payoff lambdas deliver.
starter/vectools.cpp C++ 
// Chapter 18 — Iterators and Algorithms · Project: VecTools   (STARTER)
// ─────────────────────────────────────────────────────────────────────────────
// Fill in the TASK blocks below. Each maps 1:1 to a task in the README and to a
// declaration in ../vectools.h. The bodies currently return WRONG-but-compiling
// placeholders — that is why `make test` is RED right now. Your job: turn it GREEN
// by implementing the real logic.
//
//     make build         compile your code (should already work)
//     make test          grade it (RED until you fill in the tasks)
//     make solution      run the reference if you get stuck
//
// THE PATTERN YOU ARE BUILDING TOWARDS:
//   Every "hand*" function walks the vector with an explicit iterator loop —
//   the same loop the standard library runs internally. Every "algo*" function
//   delegates to a standard <algorithm>, using a free function as the
//   predicate/comparator (NO lambdas — those arrive in Chapter 20).
//
// ITERATOR MENTAL MODEL (notes 18.2):
//
//   auto it { vec.begin() };   // cursor pointing at the FIRST element
//
//   vec.begin()        vec.end()
//       |                  |
//       v                  v
//   [ 3 ][ 1 ][ 4 ][ 1 ] one-past-last  <-- DO NOT dereference end()!
//
//   *it      -> value at the cursor     (dereference)
//   ++it     -> advance cursor by one
//   it != end -> test: are we still inside the range?
//
// CS6340 / LLVM LENS:
//   LLVM passes iterate over BasicBlock::iterator, Function::iterator, etc.
//   The identical begin()/end()/++it/!= pattern you drill here shows up verbatim
//   in every real pass. Being fluent now means you can read LLVM source code
//   without stopping.

#include "../vectools.h"
#include <algorithm>   // std::find, std::count_if, std::sort, std::max_element
#include <iterator>    // std::distance

namespace vectools
{
    // ─── TASK 1a: isEven — free-function predicate ────────────────────────────
    // Return true if n is even (divisible by 2).
    // Used as the predicate argument to std::count_if in algoCountEven.
    // NO lambdas — this IS the Chapter 18 way to pass behaviour to an algorithm.
    //
    //   >>> YOUR CODE HERE <<<
    //
    bool isEven(int /*n*/)
    {
        return false;   // placeholder — always says "not even"
    }
    // ─────────────────────────────────────────────────────────────────────────

    // ─── TASK 1b: greaterThan — free-function comparator ──────────────────────
    // Return true iff a > b (a should come BEFORE b in descending order).
    // Passed to std::sort as a strict-weak-ordering comparator.
    //
    // IMPORTANT: do NOT use `>=` or `<=` — that would violate strict weak
    // ordering (equal elements would each claim to come before the other), which
    // is undefined behaviour in std::sort. Use strictly `>`.
    //
    //   >>> YOUR CODE HERE <<<
    //
    bool greaterThan(int /*a*/, int /*b*/)
    {
        return false;   // placeholder — always says "no swap needed" (no ordering)
    }
    // ─────────────────────────────────────────────────────────────────────────

    // ─── TASK 2a: handFind — explicit iterator loop ────────────────────────────
    // Search `vec` for `target` using an iterator loop. Return the 0-based index
    // of the first match, or -1 if not found.
    //
    // Skeleton:
    //   auto it { vec.begin() };
    //   while (it != vec.end()) {
    //       if (*it == target) return <index>;
    //       ++it;
    //   }
    //   return -1;
    //
    // To get the index from an iterator, use std::distance(vec.begin(), it),
    // which counts how many steps from begin to it.
    //
    // DO NOT call std::find or any other <algorithm> here.
    //
    //   >>> YOUR CODE HERE <<<
    //
    int handFind(const std::vector<int>& /*vec*/, int /*target*/)
    {
        return -1;   // placeholder — always says "not found"
    }
    // ─────────────────────────────────────────────────────────────────────────

    // ─── TASK 2b: algoFind — wrapping std::find ────────────────────────────────
    // Use std::find(vec.begin(), vec.end(), target) to search.
    // std::find returns an ITERATOR — you must:
    //   1. Check it against vec.end() (not-found case).
    //   2. If found, convert to an index: std::distance(vec.begin(), it).
    //
    //   >>> YOUR CODE HERE <<<
    //
    int algoFind(const std::vector<int>& /*vec*/, int /*target*/)
    {
        return -1;   // placeholder
    }
    // ─────────────────────────────────────────────────────────────────────────

    // ─── TASK 3a: handCountEven — iterator loop ────────────────────────────────
    // Count elements where *it % 2 == 0 using an explicit iterator loop.
    // DO NOT call std::count_if or any other <algorithm>.
    //
    //   >>> YOUR CODE HERE <<<
    //
    int handCountEven(const std::vector<int>& /*vec*/)
    {
        return 0;   // placeholder — always says "zero even elements"
    }
    // ─────────────────────────────────────────────────────────────────────────

    // ─── TASK 3b: algoCountEven — wrapping std::count_if ─────────────────────
    // Use: std::count_if(vec.begin(), vec.end(), vectools::isEven)
    //
    // Pass the FREE FUNCTION isEven as the predicate (no lambdas!).
    // std::count_if returns a std::ptrdiff_t; cast it to int before returning.
    //
    //   >>> YOUR CODE HERE <<<
    //
    int algoCountEven(const std::vector<int>& /*vec*/)
    {
        return 0;   // placeholder
    }
    // ─────────────────────────────────────────────────────────────────────────

    // ─── TASK 4a: sortAscending — std::sort, default ordering ─────────────────
    // Sort vec in ascending order using std::sort(vec.begin(), vec.end()).
    // The default comparator uses operator< — smallest element goes first.
    //
    //   >>> YOUR CODE HERE <<<
    //
    void sortAscending(std::vector<int>& /*vec*/)
    {
        // placeholder: does nothing — vec stays unsorted
    }
    // ─────────────────────────────────────────────────────────────────────────

    // ─── TASK 4b: sortDescending — std::sort with free-function comparator ────
    // Sort vec in descending order using std::sort with the greaterThan
    // comparator declared in this namespace:
    //   std::sort(vec.begin(), vec.end(), vectools::greaterThan)
    //
    // greaterThan(a, b) returns true iff a > b — std::sort puts `a` before `b`
    // when the comparator says "a should come first". Passing greaterThan
    // therefore puts larger elements first.
    //
    //   >>> YOUR CODE HERE <<<
    //
    void sortDescending(std::vector<int>& /*vec*/)
    {
        // placeholder: does nothing — vec stays unsorted
    }
    // ─────────────────────────────────────────────────────────────────────────

    // ─── TASK 5: largest — std::max_element, with empty-range guard ──────────
    // Return the largest element in vec, or 0 if vec is empty.
    //
    // EMPTY-RANGE TRAP (notes 18.2):
    //   auto it { std::max_element(vec.begin(), vec.end()) };
    //   if (it == vec.end()) return 0;   // MUST check before dereferencing!
    //   return *it;
    //
    // std::max_element returns vec.end() when the range is empty. Dereferencing
    // end() is undefined behaviour — always guard against it.
    //
    //   >>> YOUR CODE HERE <<<
    //
    int largest(const std::vector<int>& /*vec*/)
    {
        return 0;   // placeholder — happens to be correct ONLY for empty vector
    }
    // ─────────────────────────────────────────────────────────────────────────

} // namespace vectools
Run
Submit
Run in your browser — coming soon For now: copy or download the files and use make test locally (see “Build & run locally” above).