/

Data structures

C++20

Project PDF

Data structures: 0% done

Module 1 · What a data structure is

Data is values kept in memory

Loading the slide…

A line of words about as long as a slide’s first line, and its second.

Another line, shorter.

1 / 201 · What a data structure is

Course progress

0%

, 1 to practiseData is values kept in memory
, 1 to practiseA data structure is a layout plus the operations it makes cheap
, 1 to practiseFour operations to ask about
Your first C++ program
, 1 to practiseEvery value has a type
, 1 to practiseDecisions, loops and functions
, 1 to practiseSearching a shelf means looking at every book
, 1 to practiseTry it: count the looks
The same data, arranged for a different question
, 1 to practiseTry it: build the card box
, 1 to practiseWhat a C++ value takes up
Recap

An array is a row of slots side by side
, 1 to practiseReading by index is one sum
, 1 to practisestd::array is a C array that knows its size
, 1 to practisePassing a vector: a copy, a reference, or a const reference
Inserting in the middle shifts everything after it
, 1 to practiseTry it: remove from the middle
, 1 to practiseA dynamic array grows by doubling
, 1 to practiseTry it: build a dynamic array
, 1 to practiseWhich std::vector operations are cheap
, 1 to practiseA grid is an array of arrays
Recap

, 1 to practiseCount steps, not seconds
, 1 to practiseBig O keeps only how the cost grows
The common growth rates
, 1 to practiseO(log n): halve the problem each step
, 1 to practiseTry it: count the halvings
, 1 to practiseLoops inside loops multiply
, 1 to practiseBest, worst and average cases
, 1 to practiseSpace cost: the memory it needs
, 1 to practiseAmortised cost: the average over a whole run
, 1 to practiseRecap

, 1 to practiseA string is a sequence of characters
, 1 to practiseA std::string can change in place
, 1 to practiseBuilding a long string piece by piece
, 1 to practiseWhat common string operations cost
, 1 to practisestd::string_view looks at text without copying it
, 1 to practiseTry it: reverse a string
, 1 to practiseTwo pointers walk in from both ends
, 1 to practiseCounting characters with an array of 256
, 1 to practiseCharacters, bytes and UTF-8
Recap

A linked list is a chain of nodes
, 1 to practiseA pointer holds an address
, 1 to practiseA node is a small struct
, 1 to practiseWalking the list from the head
, 1 to practiseNodes live on the heap, until someone frees them
, 1 to practiseA class looks after its own parts
, 1 to practisestd::unique_ptr owns what it points at
Adding at either end is one step, with a tail pointer
, 1 to practiseTry it: a list class with a tail
, 1 to practiseRemoving a node means changing the one before it
, 1 to practiseTry it: remove every match
, 1 to practiseA doubly linked list points both ways
Linked lists against arrays
Recap

A stack: last in, first out
, 1 to practiseA vector’s end is a ready-made top
, 1 to practiseA template writes code once, for any type
, 1 to practiseTry it: a stack class
, 1 to practiseA stack on a linked list
The standard library’s std::stack
, 1 to practiseThe call stack keeps track of running functions
, 1 to practiseUndo and redo are two stacks
, 1 to practiseMatching brackets with a stack
Recap

, 1 to practiseA queue: first in, first out
Why erasing a vector’s front makes a slow queue
Don’t move the people, move the front
, 1 to practiseTry it: a queue with a head index
, 1 to practiseA ring buffer reuses its slots
, 1 to practiseTry it: a ring buffer
, 1 to practiseA deque works at both ends
, 1 to practiseQueues everywhere
Recap

Jump straight to the right drawer
, 1 to practiseA simple hash function for strings
Two keys, one bucket: collisions
, 1 to practiseTry it: a hash map with chaining
, 2 to practiseDeleting an entry
, 1 to practiseLoad factor and resizing
, 1 to practiseAverage O(1), worst case O(n)
Recap

, 1 to practiseFour containers for looking things up
, 1 to practisestd::unordered_map: a ready-made hash table
, 1 to practisem[key] adds the key if it is missing
Hash tables have no order; trees are sorted
, 1 to practiseSets: each value once
, 2 to practiseGrouping and counting with a map
, 1 to practiseA sorted map answers "what comes next?"
Choosing a container
Recap

A tree branches out from one root
, 1 to practiseDepth, height and subtrees
, 1 to practiseTrees are everywhere
, 1 to practiseA tree node holds a vector of children
, 1 to practiseRecursion: solve it for the children, then combine
, 2 to practiseTry it: leaves and height
, 1 to practiseDepth-first: preorder and postorder
, 1 to practiseBreadth-first: level by level, with a queue
, 1 to practiseWhen a tree is too deep for recursion
Recap

, 1 to practiseSmaller keys go left, larger keys go right
, 1 to practiseA node owns its two children
Search throws away half the tree at each step
, 1 to practiseInsert walks down to an empty spot
, 1 to practiseAn in-order walk visits the keys in sorted order
, 1 to practiseThe smallest key is the leftmost, the largest the rightmost
, 1 to practiseDeleting a key has three cases
, 1 to practiseDelete in code
, 1 to practiseSorted input makes a tree as slow as a list
, 1 to practiseCheck a tree really is a BST
Recap

A priority queue serves the most urgent first
, 1 to practiseEach parent is smaller than its children, and that is all
, 1 to practiseA complete tree fits in a vector with no gaps
, 2 to practisePush adds at the end and sifts up
, 2 to practisePop takes the root and sifts the last item down
Building a heap from a list takes O(n)
, 1 to practiseHeaps schedule work and find the top k
, 1 to practiseThe standard library has a heap: std::priority_queue
, 1 to practiseTop k with the standard heap
Recap

A graph is things and the links between them
, 1 to practiseEdges can have a direction and a weight
, 1 to practiseAn adjacency list stores each vertex’s neighbours
, 1 to practiseAn adjacency matrix is a grid of yes and no
A graph struct with neighbours and degree
, 1 to practiseTry it: a friends network
, 2 to practiseDirected and weighted graphs in code
, 1 to practiseWho can I reach? A first graph search
Recap

Autocomplete asks "which words start with this?"
, 1 to practiseA node is 26 child slots and an end flag
Insert walks down, making nodes where needed
, 1 to practisehas and startsWith differ only at the last step
, 2 to practiseCollect every word below a prefix
What a trie costs
, 1 to practiseThe price is memory
, 1 to practiseCounting through a trie
Recap

A search tree is only as fast as it is short
, 1 to practiseHeight and the balance factor
, 1 to practiseA rotation lifts one side and lowers the other
, 1 to practiseTry it: rotate left
, 1 to practiseAVL insertion: insert, then rotate on the way up
, 1 to practiseRed-black trees balance more loosely
, 1 to practisestd::set and std::map are balanced trees you can use today
, 1 to practiseB-trees: wide and shallow, for disks
Skip lists: balance by coin flips
Recap

, 1 to practiseWhich group is this in, and are these two together?
Each group is a tree, and its root names it
, 1 to practiseFind climbs to the root; union links two roots
, 1 to practiseTry it: count friend circles
, 1 to practisePath compression: point straight at the root
, 2 to practiseUnion by size: hang the small tree under the big one
Together: nearly constant time
, 1 to practiseUnion-find for pixels, networks and cycles
Recap

, 1 to practiseA cache keeps answers you may need again
, 1 to practiseWhich entry goes when the cache is full?
, 1 to practiseThe classic LRU: a hash map plus a doubly linked list
, 1 to practisestd::list moves a node in O(1) with splice
An LRU cache in C++
, 1 to practiseTry it: the map-plus-list LRU
, 1 to practiseMemoising: a cache in front of a function
, 1 to practiseExpiry: entries that go stale
Recap

, 1 to practiseTotals over a range, asked again and again
, 1 to practisePrefix sums: subtract two running totals
, 2 to practiseTry it: a range-sum struct
, 1 to practisePrefix sums in two dimensions
, 1 to practiseTry it: trees in a rectangle
, 1 to practiseWhen values change, prefix sums fall behind
, 1 to practiseA Fenwick tree stores sums of power-of-two blocks
, 1 to practiseA Fenwick tree in code
Segment trees answer more kinds of question
Recap

, 1 to practiseChanging data in place forgets the past
Copy everything, or share what did not change
, 1 to practiseShared cells need shared owners: std::shared_ptr
A persistent linked list
, 1 to practiseTry it: change one item, share the rest
, 1 to practisePath copying: a new tree in O(log n)
, 1 to practiseTry it: a persistent insert
, 1 to practiseSame pointer, same contents: change detection for free
, 1 to practiseWhat persistence costs
, 1 to practiseBonus: a Bloom filter trades certainty for space
Recap

, 1 to practiseHow this challenge works
, 2 to practiseChoose a structure by the operations you need
, 1 to practiseBuild it: a stack that knows its minimum
, 1 to practiseBuild it: the k most frequent words
, 1 to practiseBuild it: an LRU cache with a size budget
, 1 to practiseBuild it: is this network a tree?
, 2 to practiseReview it: a heap that is almost right
, 3 to practisePredict what the structures do
, 2 to practiseWhich statements are true?
Recap: the whole course