Advanced Project 6 — Policy-Based Cache¶

Difficulty: Advanced · Estimated effort: 2 weeks · Prerequisites: Module 12 — Templates, Module 11 — RAII and Smart Pointers, Module 15 — SOLID and Design Patterns · Demanded pattern decisions: policy-based design, decorator

This is one of the designated integration projects, and one of the projects that requires a design-pattern decision: at least two patterns must be named and justified by a requirement, and one alternative must be considered and declined in writing.

No complete solution is provided. The policy decomposition is the exercise; the brief names the requirements, not the template parameters.

1. Scenario¶

A benchmarking course needs a small, well-understood cache to demonstrate the cost of different data structures. Students must be able to swap the eviction rule, the index structure and the value-storage strategy without rewriting the cache, and to wrap a cache with a statistics decorator that counts hits, misses and evictions without the cache knowing about statistics.

The requirements are deliberately academic: the point is to see the difference between a decision made at compile time and the same decision made at run time.

2. Problem statement¶

Build a cache that keeps a bounded number of key–value pairs, with three independently varying choices: which entry to evict, how keys are hashed and looked up, and whether values are stored by value or by pointer. Then add cross-cutting behaviour — statistics, and optionally logging — as a wrapper rather than as a change to the cache.

3. User requirements¶

[ ] Put and get values by key; a miss is reported as a miss, not as an exception.
[ ] Bound the cache and observe eviction when the bound is reached.
[ ] Choose an eviction rule at build time and swap it for another.
[ ] Choose the index structure and swap it for another.
[ ] Wrap a cache so that hit, miss and eviction counts are available without modifying the cache itself.
[ ] Compare configurations on a scripted workload and print the numbers.

4. Functional requirements¶

[ ] A Cache<Key, Value, EvictionPolicy, IndexPolicy> template (names are yours).
[ ] At least two eviction policies: least-recently-used and first-in-first-out.
[ ] At least two index policies: an unordered map and an ordered map, or a hash plus a secondary structure for the eviction order.
[ ] A statistics decorator with the same interface as the cache, forwarding to the wrapped one.
[ ] A documented hit/miss outcome type, so the caller cannot ignore a miss accidentally.
[ ] A scripted workload runner with a deterministic access sequence from a seed.
[ ] Errors for invalid capacity, an unknown key on removal, and a policy that cannot evict.

5. Non-functional requirements¶

[ ] The cache holds no statistics counters — that is the decorator's job, and the tests prove it by using an undecorated cache.
[ ] Configurations are interchangeable at compile time, with each configuration instantiated at least once so nothing is silently unexercised.
[ ] No policy reaches into another policy's data; the interface between them is small and documented.
[ ] The bound is never exceeded: capacity is checked after every insertion.
[ ] Builds warning-free with g++ -std=c++17 -Wall -Wextra -Werror.

6. Suggested features¶

A value-storage policy: by value, or by unique_ptr, with the trade-off measured.
An expensive-recomputation demo: a factory function that builds a value, so a miss can be seen as real work.
A second decorator that logs every operation, composed with the statistics one — and a measurement of what the wrappers cost.
A short benchmark comparing four configurations on the same workload, printed as a table.

7. OOP concepts involved¶

Concept	Required	Where it appears
Multiple classes	yes	Cache, eviction policies, index policies, storage policies, decorators, workload runner
Relationships	yes	Decorator wraps (and owns) a cache; cache ┈┈> policies as template parameters; index ──> entries
Encapsulation	yes	The bound and the eviction structure are invariants of the cache; no policy mutates another's state
Inheritance or composition	yes	The decorator uses interface inheritance plus ownership; policies use composition
Polymorphism	yes	Runtime dispatch through the decorated interface; compile-time dispatch through policies — the contrast is the lesson
The STL	yes	`std::unordered_map`, `std::map`, `std::list` for recency order, `<algorithm>` and `<random>` for the workload
Exception handling	yes	Bad capacity and inconsistent policy combinations refused with clear types

8. Suggested design considerations¶

The pattern decision you must make and justify¶

Policy-based design, for the three choices. Template parameters make a wrong combination a compile error and cost nothing at run time. The alternative is runtime strategies behind interfaces: uniform types, swap-at-run-time, one indirection per call. You must choose, and the requirement that decides it here is swap the eviction rule without rewriting the cache — which both satisfy. Say what actually settled it for you, and give the measured difference if you can.

Decorator, for statistics. The requirement is precise: counts must be available without modifying the cache. That is exactly the decorator. The alternative is a base class with hooks, which changes the cache and is therefore not the same thing; declining that is the declined-pattern item, and the reason is the requirement itself.

Ideas worth weighing and recording: adapter, if you want to expose a cache through a different interface (operator[] versus get) — mildly earned; observer, for eviction notifications — probably not earned, since the decorator already counts them.

Other design points¶

Keep the policy interface small. If an eviction policy needs to know about hashing, the split is wrong. Three narrow interfaces beat one wide one, and the tests will tell you which you built.

A miss is not an error. Making a miss an exception will make the cache unusable with the workload runner and teaches the wrong lesson about control flow versus failure.

Instantiate every configuration. A template that is never instantiated is not code; it is an intention. The workload runner instantiating four combinations is also what spots the compile errors in the combinations you did not think about.

9. Minimum viable version¶

A cache with one eviction policy (LRU), one index (unordered map plus a list), a bound, hit/miss outcomes, and a small workload in main. No templates yet, or one template parameter only.

10. Intermediate extension¶

Add the second eviction policy and the second index policy as template parameters, plus the statistics decorator. Prove with a test that an undecorated cache keeps no counters — for example by using it in a test that would fail if a shared counter existed.

11. Advanced extension¶

Add the storage policy, the logging decorator composed with the statistics one, and the four-configuration benchmark table. Then write the design note: the two patterns, the declined alternative, the measured cost of the wrappers, and the decision you would reverse.

12. Testing checklist¶

[ ] A get for an absent key reports a miss and inserts nothing
[ ] Putting the same key twice replaces the value and does not grow the cache
[ ] The cache never exceeds its bound, after any sequence of puts (checked every step)
[ ] LRU evicts the least recently used entry, not the least recently inserted
[ ] FIFO evicts the earliest inserted entry, where the two policies differ
[ ] The statistics decorator's hit + miss equals the number of gets
[ ] Eviction counts match the number of puts beyond the bound
[ ] The undecorated cache exposes no counters and behaves identically (same values returned)
[ ] Two decorators composed produce the same values as one, with both sets of counts correct
[ ] A capacity of zero is refused at construction
[ ] Removing an absent key is reported as a miss, not a failure
[ ] The same seed produces the same workload and the same counts, twice

13. Documentation checklist¶

[ ] The policy interfaces, each with its contract in one paragraph
[ ] Which combinations are valid, and how a wrong combination fails (compile time or run time)
[ ] The decorator's interface and how it forwards
[ ] The benchmark table with the compiler flags it was measured under
[ ] Why the statistics could not go inside the cache, restated as the requirement

14. Self-evaluation rubric¶

Criterion	Excellent looks like	Weight
Policy decomposition	Three independent choices with narrow interfaces; combinations instantiated	30%
Decorator use	Statistics and logging added without touching the cache; composition tested	20%
Pattern reasoning	Compile-time versus run-time decision argued with evidence	20%
Correctness	Bound, eviction order and hit/miss accounting all verified	20%
Measurement	Wrapper cost and configuration comparison reported with numbers	5%
Documentation	Contracts, valid combinations and evidence written down	5%