Stage 1 · Lesson 5 of 8
Sets, maps and priority queues
set and map keep elements sorted in a balanced tree, so inserting, erasing and finding cost O(log n). lower_bound on a set finds the first element not below a value, which answers "what is the next larger item" while the data changes.
multiset allows duplicates, and map counts or groups things by key. priority_queue is a : it always gives the largest element (or the smallest, with greater), which is what and many scheduling greedies need. Knowing which container answers which question quickly is half of many easier problems.
Common traperasing a value from a with erase(x), which removes every copy instead of one.
A question to check yourself, an AI practice session and 2 cheat sheet entries come with the full roadmap. Unlock
Resources for this stage
Start with· follow one of these
- CourseFreeLearnCpp.com
LearnCpp.com · Beginner
Free and thorough: read the chapters on vectors, references, lambdas and the standard library if C++ is new to you
- BookFreeCompetitive Programmer's Handbook
Antti Laaksonen · Beginner
Chapter 1 covers C++ for contests, input and output and working with numbers; Chapter 2 covers complexity
Practise
Keep handy
Also worth your time
A clear walk through time and space complexity, the language you need to read constraints
- USACO GuideGo deeper
The General section has practical pages on choosing a language, fast input and output and debugging