Glossary

111 terms from Data Structures and Algorithms in C++, in plain words, each with the chapter that teaches it.

Search the glossary

#

-O2: A compiler flag that turns on optimization. It drops work whose result is unused, so a timing can show 0 unless you use the result.

A

Adjacency list: A way to store a graph as a map from each place to a vector of its neighbors. Alex's map keeps "Roastery" -> Burnside, Hawthorne, Sellwood.
Algorithm: A step-by-step method for doing a job, such as checking each order in turn until you find the one you want.
Amortized: Cost averaged over many operations. A vector's push_back is occasionally slow when it must move everything to a bigger block, but it averages out to O(1).
Array: Items stored side by side in numbered slots, so any index is reached in one step.
at(): A bounds-checked way to read an item that throws std::out_of_range if the index (vector) or key (map) is missing. Plain [] on a vector isn't checked.
Average case: The cost you can expect in a typical run. Hash map lookups are O(1) in the average case because collisions are rare.

B

Balanced tree: A tree whose subtrees have similar heights, so its height is about log₂ n and lookups are O(log n). Inserting sorted IDs into a plain BST makes an unbalanced chain instead.
Base case: The input a recursive function answers directly without calling itself, such as seconds == 0 in countdown. Without it the recursion never stops.
Big-O notation: A way to describe how the number of steps grows as the input size n grows, ignoring constants and smaller terms. O(1) constant time is the same steps however big the data; O(log n) logarithmic time comes from halving the data each step; O(n) linear time grows in step with n; O(n²) quadratic time usually comes from a loop inside a loop.
Binary search: Finding an item in sorted data by checking the middle and discarding the half that can't hold the target, so n items need about log₂ n steps.
Binary search tree (BST): A binary tree where everything in a node's left subtree is smaller and everything in its right subtree is bigger. Insert and contains take O(height) steps.
Binary tree: A tree where each node has at most two children, called left and right.
Breadth-first search (BFS): A graph search that visits the start, then all its neighbors, then their neighbors, ring by ring, using a queue and a visited set. It finds the route with the fewest stops.
Bucket: One slot in the internal array of a hash map; a key's hash picks which bucket its pair is stored in.

C

Call stack: The pile of notes for function calls that haven't finished yet, each holding local variables and where to carry on. It works last in, first out.
came_from: A map BFS fills in, recording for each place which place it was reached from. Walking it backward from the goal rebuilds the route, then std::reverse puts it in order.
Capacity: The number of spare slots a std::vector has reserved. When it runs out, the vector moves everything to a bigger block.
Child, parent: In a tree, a node's children are the nodes directly below it, and it is their parent.
Class: A blueprint for making objects, with their own data members and member functions. Stack<T> is a class.
Class template: One class definition that works for any type, like Stack<std::string> or Stack<char>. Templates must be fully visible where used, so they live in a header file.
Collision: Two different keys whose hashes land in the same bucket. The map then checks the few entries stored there.
Comparator: A function (or lambda) of two items that returns true when the first should go before the second. It tells std::sort or std::stable_sort how to order structs like Sam's orders.
const: A keyword marking something that can't change. A const method doesn't modify the object, and a stored hash map key is const so its bucket never changes.
CSV: A plain text file with one record per line and values separated by commas, like the planner's roads.csv and deliveries.csv.

D

Data structure: A way of arranging data so a particular job is easy and fast, such as a vector for ordered items or a hash map for lookups by key.
Depth-first search (DFS): A graph search that goes as far as possible down one road before backing up, written with recursion or a stack. It finds everything reachable from a place.
Dequeue, enqueue: Enqueue adds an item at the back of a queue; dequeue takes one off the front.
Dijkstra's algorithm: An algorithm that finds the fastest route in a weighted graph. It would fix the planner's problem that fewest stops isn't fewest minutes, and is taught in the next book.
Divide and conquer: Solving a problem by splitting it in half, solving each half, then combining the answers, as merge sort does.
Doubly linked list: A linked list where each node also points back to the previous node. std::list is one.
Dynamic array: An array that grows when it fills up. std::vector is one: it keeps spare capacity and moves to a bigger block when it runs out.

E

Edge: A connection between two vertices in a graph, such as a road between two places.
Exceptions (runtime_error, out_of_range, invalid_argument): Standard exception types that stop a program when thrown. at() throws out_of_range for a missing index or key, stoi throws invalid_argument on bad text, and the planner throws runtime_error for a missing file.

F

FIFO, LIFO: FIFO (first in, first out) is how a queue serves items, like a line at the counter. LIFO (last in, first out) is how a stack works, so the latest change is undone first.
Functor: A struct or class that defines `operator()` so its objects can be called like functions. It is used to supply custom behavior, such as the hash function that lets a struct like `CityProduct` be a key in a `std::unordered_map` (e.g. `CityProductHash`).

G

g++ -std=c++20 -Wall -Wextra: A `g++` compile command that builds a program using the C++20 standard and turns on extra compiler warnings. The `-o` option names the output program, as in `g++ -std=c++20 -Wall -Wextra file.cpp -o file`.
Graph: Vertices joined by edges, such as places joined by roads. It suits maps with loops that a vector or tree can't hold.

H

Hash function: A function that turns a key into a whole number, which the map uses to pick a bucket. The same key always gives the same number.
Hash map: A structure that stores key-value pairs and finds a value by its key in O(1) on average, like a coat check ticket.
Hash set: A hash map with keys and no values. contains(x) and insert(x) are O(1) on average, so a `seen` set can find duplicates in one pass.
Hashable: A type that can be a hash map key or set item because it has a std::hash and an ==. Strings and numbers are; std::pair and std::vector are not.
Head: The first node of a linked list. The list keeps only its head, and removing the head is a special case.
Heap: A binary tree with every level full except perhaps the last, stored in a vector with no links. In a min-heap every parent is no bigger than its children, so the smallest item is at index 0.
Heapify: Rearranging a vector into a heap in place in O(n) steps. In C++ that's std::make_heap, with std::push_heap and std::pop_heap to add and remove.
Height: The number of levels in a tree, from the root down the longest path to a leaf. A balanced tree of a million IDs has height about 20.

I

Immutable: Can't be changed after it's made, like a const object. C++ strings are mutable, so += appends in place.
In place: Changing a vector itself instead of making a new one, like reverse_in_place swapping from both ends with O(1) extra space.
In-order traversal: Visiting a tree's left subtree, then the node, then the right subtree. On a BST the values come out sorted.
Index (hash index): A hash map built once from a vector, keyed by something like a SKU, so every later lookup is O(1) instead of an O(n) loop.
Insertion sort: A sort that works like sorting a hand of cards: take each item and slide the bigger ones right to make a gap for it. It is O(n²) but fast on nearly sorted lists.
Introsort: The algorithm behind std::sort: a quicksort that switches to heap sort if it recurses too deep, and to insertion sort on short ranges. It is O(n log n) even in the worst case but not stable. Quicksort and heap sort are other O(n log n) methods.
Iterator: An object that points at one element of a container, such as begin() or the result of std::lower_bound. Reverse iterators rbegin() and rend() walk backward.

L

Lambda: A small nameless function written right where it is needed, often as a sort comparator.
Linear search: Checking items one at a time from the start until you find the target. It takes up to a million steps on Kettle & Crane's million orders.
Linked list: A chain of nodes, each holding a value and a link to the next, where the first is the head. The last link is nullptr.

M

Max-heap: A heap with the largest item first. std::priority_queue is one by default; add std::greater<> to get a min-heap.
Member function: A function that belongs to a class and is called with a dot, like stack.push(x).
Memoization: Saving the answers to calls already made so a function doesn't work them out again. It is covered in the next book.
Merge sort: Split the list in half, sort each half recursively, then merge the sorted halves. It is O(n log n) and stable.
Min-heap: A heap where every parent is no bigger than its children, so the smallest item is on top. In C++ you get one from std::priority_queue by adding std::greater<>.

N

Neighbor: A vertex joined to another by an edge, such as Burnside to the Roastery.
Node: One item in a linked list or tree, holding a value and links to other nodes. In a graph, nodes are also called vertices.
nullptr: The value of a pointer that points at nothing. It ends a linked list and marks an empty child in a tree.

O

Off-by-one error: A mistake of exactly one in an index or comparison. Binary search's classic ones are `low < high` instead of `<=`, and `low = middle` instead of `middle + 1`.
Ownership: Which object is responsible for freeing a resource. Each Node owns the next through a std::unique_ptr, so the whole chain is freed with its first node.

P

Pre-order traversal: Visiting a tree's node before its subtrees. It is handy for printing a tree's shape, as print_tree did.
Priority queue: A queue that serves the most urgent item first, regardless of arrival order. std::priority_queue wraps a heap with push, top and pop.
Push, pop, peek: Push adds an item to the top of a stack, pop removes the top item, and peek looks at it without removing it. All are O(1).

Q

Queue: A first-in, first-out line of items, like support tickets answered in arrival order. std::queue has push, front and pop, all O(1).

R

RAII: The C++ habit of tying a resource's cleanup to an object's lifetime. The std::ifstream in load_roads closes its file automatically when the function ends.
Recursion: A function solving a problem by calling itself on a smaller piece of it, until it reaches a base case.
Recursive case: The part of a recursive function that makes the problem smaller and calls itself on it.
Root, leaf: The root is the top node of a tree; a leaf is a node with no children.

S

Segmentation fault: A crash from using memory the program shouldn't, such as following a nullptr or overflowing the stack.
Self-balancing tree: A tree, such as an AVL or red-black tree, that rearranges nodes as you insert to keep its height near log₂ n, avoiding the chain that sorted input creates. std::map is usually a red-black tree.
Shifting: Moving items along a list to open or close a gap. Inserting or erasing at the front of a vector shifts every other item, which costs O(n).
SKU: Stock-keeping unit: a product's stock code, such as HE-5, used as a key to look products up quickly.
Slice: A piece of a vector or string. Building one with std::vector(begin()+a, begin()+b) or std::string::substr copies it in O(k), so changing it doesn't change the original.
Space: The memory an algorithm needs, which Big-O can describe too. has_duplicate uses O(1) extra space, while a copy of the vector would be O(n).
Spaceship operator (operator<=>): A C++20 operator that, when written `= default`, makes the compiler generate all comparisons by comparing members in the order written. It lets a heap order a Delivery by deadline, then café name.
Stable sort: A sort that keeps equal items in their original order. Steam & Co and Little Owl both have 144, and Steam & Co stays first. std::stable_sort is stable; std::sort may reorder equal items.
Stack: A last-in, first-out pile where you add and remove at the top only. It suits undo and bracket matching, and std::stack's pop() returns nothing.
Stack overflow: The crash when the call stack grows past its fixed memory, usually from a missing base case or very deep recursion. On Linux it shows as a segmentation fault.
std::chrono::steady_clock: A precise clock for timing code: read now() before and after, subtract to get a duration, and call .count() for the number.
std::deque: A double-ended queue (say "deck") with O(1) push and pop at both ends that still allows indexing like orders[i]. It can serve as a stack or a queue.
std::find: A library function that searches a range for a value one item at a time, so it is O(n).
std::format: C++20 text formatting using codes like :<12 (left-align), :>4 (right-align) and :02d (a whole number at least 2 wide, padded with zeros), so 9:30 prints as 09:30.
std::iota: A library function that fills a range with 1, 2, 3 and so on.
std::lower_bound: A tested O(log n) binary search that returns an iterator to where a value would go in a sorted vector, at its first copy if present. upper_bound returns the position after any copies.
std::map: A sorted, tree-based key-value map with O(log n) operations, in contrast to the O(1) average of unordered_map. It needs only < on its keys, so a std::pair can be a key.
std::move: Transfers ownership of a value (such as a unique_ptr) instead of copying it. push_front uses it to hand the old head to the new node.
std::pair: Two items kept together, compared first then second. It has no std::hash, so it can be a key of a std::map but not of an unordered_map.
std::partial_sort: Puts only the first k items by a comparator at the front, in order, and leaves the rest unsorted. It costs O(n log k), so it's a quick way to get the top few.
std::printf: The C-style print function that takes a format string; %g prints a number plainly and %.2f prints two decimals.
std::reverse: Turns a vector around in place; BFS uses it to flip the route it built backward.
std::sort: The library's in-place O(n log n) sort. It orders numbers and strings naturally, or structs with a comparator, and may reorder equal items.
std::span: A read-only view of a run of items with no copying; subspan(1) is the view without the first item. A vector converts to one.
std::stoi: Converts text to an int, as in to_minutes. It throws invalid_argument if the text isn't a number.
std::string_view: A window onto another string's characters with no copying, so its substr is O(1). It prints garbage if the original string dies or changes.
std::stringstream: A stream made from a string, which with std::getline and ',' as separator splits a CSV line into pieces. std::ifstream reads a file and closes it automatically.
std::unique_ptr: A smart pointer that owns the thing it points to and deletes it when it goes away. A unique_ptr can't be copied, only moved with std::move.
std::vector: C++'s dynamic array. Index reads and push_back are cheap, but inserting or erasing at the front or middle shifts items, costing O(n).
Subtree: A node together with everything below it; it is itself a tree.

T

Traversal: Visiting every node in turn, such as walking a linked list from the head until nullptr, or a tree in-order.
Tree: A structure that stores items in levels, like a family tree or folders in folders. It has a root at the top, with children below.

U

Undefined behavior: What happens when code does something C++ doesn't define, like popping an empty stack or using [] out of range. It may crash, return garbage or seem to work.

V

Vertex: A point in a graph, such as a place on Alex's map. Also called a node.
visited set: The set of places a search has already reached, so none is handled twice. Without it BFS would loop forever around Roastery, Burnside, Hawthorne.

W

Weighted graph: A graph whose edges carry numbers, such as minutes of driving.
Worst case: The most work an algorithm can need for an input of size n, the slowest input and the one that hurts users. Big-O is usually quoted for it.