Module 8 · set and multiset: Sorted, Unique, Found in log n
Every set and multiset Operation, One by One, With Its Cost
Free with an accountReading
Bob keeps a set of a million numbers and often asks for the first one at or above some x. Module 2 used lower_bound(v.begin(), v.end(), x) on a sorted vector, so Bob writes the same call on his set. It compiles, and every answer is right. Yet each call took 32 to 63 milliseconds in this lesson's measurement, and his program makes thousands of them. The cost lines below explain why, and give Bob a call that takes a few microseconds at most.
Checking what this lesson needs for you…
What is inside Every set and multiset Operation, One by One, With Its Cost
- Making one: empty, from a list, from a range, or a copy
- insert, and the bool it returns
- insert with a hintIntermediate
- erase: by value, by iterator, or a range
- Erasing one copy from a multiset
- find and count
- lower_bound, upper_bound and equal_range
- Why the member lower_bound beats the free one
- begin, rbegin and prev(end): the two ends
- size, empty, clear and swap
- The walk: range-for, ++it and --it
- == and < on two sets
- extract and mergeIntermediate
- What a set does not have
- Every cost in one table, and the measurement