STL Algorithms Priority Queue

STL Algorithms & Priority Queue

Folder: 06-stl-algorithms-priority-queue

What it is

This folder is a tour of the algorithm header and two container adapters. The recurring exercise is to take code written with hand loops and replace each loop with the matching STL algorithm. The five programs use a fruit theme so each one isolates a small set of tools.

How this code does it

apples.cpp is the algorithm showcase. It fills a crate of apples with std::generate, prints them with std::for_each, counts heavy ones with std::count_if, finds the heaviest with std::max_element, sums weight with std::accumulate, grows every apple with std::transform, drops the light ones with the erase-remove idiom (std::remove_if followed by vector::erase), and finally orders the crate with std::sort. The original hand-loop version of each step is left in a comment above its replacement, so the file reads as a before-and-after.

peaches.cpp covers the same ground for a jamming problem, leaning on <numeric> and <iterator> as well.

lemons.cpp builds a std::priority_queue from a vector so the best lemons come off the top first. A priority queue is a container adapter: it sits on top of a vector or deque and keeps the largest (or, with std::greater, the smallest) element at the front.

priorityQueue.cpp is the minimal adapter demo. It pushes the days of the week into a priority_queue ordered with std::greater<string>, then pops them, which prints them in sorted order.

oranges.cpp uses a std::multimap keyed by quality, then selects a range with lower_bound and upper_bound and inserts with emplace.

How a priority queue orders its elements

flowchart TD
    P["push values"] --> H["priority_queue keeps a heap"]
    H --> T["top() returns the highest-priority element"]
    T --> O["pop() removes it, heap re-orders"]
    O --> T

Loading

Build and run

g++ -std=c++17 06-stl-algorithms-priority-queue/apples.cpp -o apples
./apples   # prompts for a crate size and weights

g++ -std=c++17 06-stl-algorithms-priority-queue/priorityQueue.cpp -o pq
./pq

apples, peaches, lemons, and oranges read numbers from standard input as they run.

Notes

The skeletons and the commented hand-loop versions came from the course. My work is the algorithm replacements: choosing the right algorithm for each loop and writing the lambdas that drive them.