Model answer
Use an unordered_map from key to iterator for expected O(1) lookup and a doubly linked list for recency order. Access moves the node to the front; eviction removes the tail, both in O(1).
Use the key terms, then explain the reasoning.
Linear Data Structures
C++17
C++17Choosing a Data Structure
The right structure follows from the dominant operations, ordering requirements, memory limits, input scale, and correctness constraints.
What to understand
- Operation-frequency analysis
- Ordered versus unordered data
- Memory and locality
- Worst-case guarantees
Remember this
- 1Choose from requirements, not habit
- 2Measure the hot operations
- 3Account for library guarantees
- 4Simple structures are often best
Detailed notes
Data-structure selection begins with operations and guarantees, not names. List query types, update frequency, ordering needs, input scale, memory limits, concurrency, and acceptable worst-case behaviour.
Library structures encode trade-offs: vector favours locality and indexing; list favours known-position relinking; unordered_map favours expected lookup; map favours ordered logarithmic operations; priority_queue favours repeated extrema.
How it works
- 1Rank operations by frequency and cost sensitivity.
- 2Decide whether ordering or range queries are required.
- 3Estimate data scale and memory overhead.
- 4Prefer the simplest structure that meets the guarantees, then measure.
Where it is used
- API and domain-model design
- Performance-sensitive competitive programming
- Storage and indexing decisions
Common mistakes
- Choosing a linked list only because insertion is called O(1)
- Ignoring cache locality and allocator cost
- Using a hash table when ordered traversal is required
Implementation perspective
This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.
Exam & viva
Open a prompt when you are ready to check your answer.