Practice Lab 27 — Inventory lookups, measured¶

Difficulty: Intermediate · Estimated time: 5 hours · Module 14: STL with OOP

Two containers, one workload, and numbers. This lab is decided by a measurement, not by a preference.

At a glance¶


Difficulty	Intermediate
Estimated time	5 hours
Module	Module 14 — The STL with OOP
Concepts practised	Containers and their guarantees, iterators, algorithms and lambdas, erase-remove, complexity measurement, comparison counts, choosing a container from a workload
Prerequisite	Practice Lab 26
Class design	the record types are given; the containers are your choice, with evidence

Scenario¶

A warehouse system looks up stock items by code thousands of times a session, and prints reports in code order once an hour. It also inserts new items during a delivery, and removes discontinued ones in batches.

Three implementations exist in different branches of the project, each written by somebody who had a reason:

a sorted container with binary search,
a balanced tree keyed by code,
a hash map keyed by code.

All three pass the same tests. The argument about which to ship has been going on for a fortnight, and this lab ends it with a measurement.

Problem statement¶

Implement the warehouse's catalogue twice, and measure both.

A StockItem record: code, description, quantity on hand, reorder level, and a category.
Implementation A: a sorted container with a binary search, using a standard algorithm rather than a hand-written loop.
Implementation B: a hash container keyed by the code, plus a documented way to produce the ordered report.
The same operations on both: insert, find, remove, update quantity, list in code order, list by category, and report items below the reorder level.
Query rewrites: at least three hand-written loops replaced by standard algorithms, with the output compared before and after — including one erase-remove idiom.
A comparison count: your lookups must count how many key comparisons they perform, printed with each measurement, so the complexity claim is not merely asserted.
A measurement harness: the same workload at two sizes (for example 1 000 and 100 000 items), reporting comparison counts and elapsed work for each operation, per implementation.

In container-notes.md:

The workload, stated in one sentence, and which operation the sentence makes dominant.
The comparison-count table for both implementations at two sizes, with the ratio explained.
The container you would ship, the cost you accepted, and what would change your mind.
The three rewrites, each with the output comparison that proves behaviour is unchanged.

Learning objectives¶

By the end of this lab you will be able to:

Choose a container from a stated workload rather than from habit, and justify it with a measurement.
Use standard algorithms, including find_if, transform, count_if and erase-remove.
Write a lambda that captures what it needs and nothing more.
State the complexity of your main operations and show it with comparison counts at two sizes.
Report honestly when the measurement contradicts the expectation you started with.

Functional requirements¶

Both implementations satisfy the same interface — the same operations with the same behaviour, so the measurement compares like with like.
Duplicate codes are refused in both, in one place.
Removal refuses an unknown code; batch removal removes every match and reports the count.
The ordered report is identical in both implementations, and the order is stable for equal keys.
Category and reorder reports are identical in both.
Comparison counting is inside the container's lookup path, so it reflects the real work.
The two sizes are run in the same program, with the same workload, and the numbers printed side by side.
At least one measurement contradicts a naive expectation — a hash lookup is not automatically faster at 1 000 items; explain the result rather than hiding it.
No hand-written linear search remains in the lookup paths — searched for and recorded.
A comparison with a std::map-based version is included, since the project's third branch claims it.

Constraints¶

Header and source per implementation, with a documented build command, so both can be compiled and run from one main.
No container other than standard ones — the exercise is choosing among them, not writing one.
No -O3 claims: compile the way the course teaches, and say in the notes what optimisation level you used and that it is not the point.
Timing is secondary; the comparison counts are the evidence. Where you do time, run each measurement enough times to be meaningful, and say how many.
No warnings.

Starter task¶

In container-notes.md, before coding:

Write the workload in one sentence: which operation dominates, how often it happens, and whether order is ever needed.
Predict the comparison counts for a 1 000-item catalogue: linear scan, binary search, tree, hash.
Choose the container you expect to ship, and write the cost you are accepting.
Write the three loops you will rewrite as algorithms, and the output check you will use.

Implementation tasks¶

Implement StockItem and the shared interface.
Implement implementation A with the sorted container and binary search.
Implement implementation B with the hash container and an ordered report.
Add the comparison counter and thread it through the lookup path.
Rewrite the three loops, and compare outputs before and after each.
Write the harness, run both sizes, and record the table.
Add the third branch's std::map version for comparison, and record its numbers too.

Test cases¶

#	Action	Expected result
1	Find a present code, both implementations	Same item; comparison counts recorded
2	Find an absent code	Documented absence; no linear scan in the hash version
3	Insert a duplicate code	Refused in both
4	Remove an unknown code	Refused in both
5	Batch removal of a category	Same removals; count printed; erase-remove used
6	Ordered report	Identical in both implementations
7	Reorder report	Identical in both
8	1 000 items: 1 000 lookups	Comparison counts per implementation, with the ratio
9	100 000 items: 1 000 lookups	The same, and the ratio compared with case 8
10	The `std::map` version	Its counts recorded, and compared
11	Output comparison for each rewritten loop	Identical before and after
12	Search for a hand-written lookup loop	None in the lookup paths — recorded

Boundary cases to run deliberately: an empty catalogue; a single item; a category with no items; a reorder level of zero; a code that sorts last.

Expected behaviour¶

catalogue size 1000
  A sorted vector + lower_bound : 1000 lookups, 10000 comparisons  (10 per lookup)
  B unordered_map               : 1000 lookups,  1000 comparisons  (1 hash + 1 comparison)
  C std::map                    : 1000 lookups, 18000 comparisons  (18 per lookup)
catalogue size 100000
  A sorted vector + lower_bound : 1000 lookups, 17000 comparisons
  B unordered_map               : 1000 lookups,  1000 comparisons
  C std::map                    : 1000 lookups, 34000 comparisons
ordered report: identical across all three implementations
erase-remove: 37 items removed, identical set removed by all three
at 1000 items the hash's advantage is small - the hash costs are fixed overhead;
at 100000 it is the difference between 1 and 17-34 comparisons per lookup

Extension challenge¶

Add a second query: "which items were ordered by this supplier?" — a many-to-many lookup, and one that needs to be fast for a different access pattern.

Record in container-notes.md:

Whether the existing container can serve it, and what you would add (an index, a second map, a sorted vector) — with the cost of maintaining consistency between them.
The comparison counts for the new query in your chosen structure, against a linear scan.
The rule you would apply to decide whether an index is worth maintaining, in one sentence.
The change cost: files, operations, lines.

Debugging challenge¶

The hash version is dramatically slower than the sorted vector, and the code looks right:

struct StockItemHash {
    std::size_t operator()(const StockItem& item) const {
        return item.category().size();      // "categories vary, so this should spread well"
    }
};
std::unordered_map<StockItem, int, StockItemHash> items_;

Reproduce it — build a catalogue of 1 000 items across five categories — and answer:

How many buckets does your hash produce effectively, and what does the container do with the rest?
Which equality does the container need, and does your type's == mean what the container assumes?
Write the corrected hash, and say what property it must have that the original lacked.
Which test case in the table exposed it, and what did the comparison count show?

Reflection questions¶

State your workload in one sentence. Which operation did it make dominant, and did the measurement agree?
Where did the measurement contradict your prediction, and what did you learn from the contradiction?
erase-remove: what does remove_if actually do, and what does the erase do? Say it in one sentence each.
Your ordered report needs ordering from a hash container. What does that cost, and when is it too much?
Which hand-written loop was hardest to replace, and what did the algorithm require of your type?
If the workload changed to "inserts dominate, lookups rare, order never needed", which container wins, and what would you have to change in your code?

Completion checklist¶

[ ] It builds from a documented command with -Wall -Wextra -Werror and no warnings
[ ] Both implementations satisfy the same behaviour, verified by identical output
[ ] Comparison counts printed for both, at two sizes
[ ] The std::map version's counts recorded for comparison
[ ] At least three loops rewritten with algorithms, each verified by output comparison
[ ] The erase-remove idiom is used and demonstrated
[ ] No hand-written lookup loop remains in the lookup paths — searched for and recorded
[ ] One measurement that contradicted the expectation is explained
[ ] All twelve test cases run, with output recorded
[ ] container-notes.md states the workload, the table, the choice and the rejected option's cost
[ ] The debugging challenge was explained before being fixed