Embercode
✕
The STLLesson 6 of 17

90 min read

Module assignment: bookshop order desk

What you will build

This assignment brings together everything in the module. You will write a program that runs a small bookshop order desk. The program reads commands from the input, one per line. It keeps a shelf of books, a line of customer orders, and a count of how many copies of each title have been sold. Each command prints one or more lines of output.

The assignment is graded. Read the whole page before you write any code. The spec, the examples and the rubric tell you exactly what a correct program prints, and the checklist tells you what to finish, in what order. The hints and the reference solution are hidden below their headings, so try each step yourself first.

You will need the containers from the module. The orders wait in a line, so they need a queue. The shelf is looked up by title and printed in alphabetical order, so it needs a map. The sold counts are updated constantly and need no order until the top list is printed, so an unordered_map fits. The top list needs a sort, which you will write with a comparator, the same way as in lesson four.

The spec

The program reads lines from standard input until the input ends. A line is one command. The first word of the line is the command name, and the rest of the words are its arguments. Titles and customer names are single words made of letters only, so Dune is a title and The Dune is not. Blank lines are skipped.

The commands are these.

  • STOCK title copies adds copies copies of title to the shelf. If the title is already on the shelf, the copies are added to the old count. Nothing is printed.
  • ORDER customer title joins the back of the order line. The program prints queued customer title at position P, where P is the number of orders in the line after this one joins, counting from 1.
  • SERVE takes the order at the front of the line. If the line is empty, the program prints no orders. If the title has at least one copy on the shelf, one copy leaves the shelf, the sold count for that title goes up by one, and the program prints served customer title. If the shelf has no copies left, the program prints out of stock title for customer, and the order is dropped. It is not put back in the line.
  • SHELF prints every title with at least one copy on the shelf, in alphabetical order, one per line as title copies. If no title has any copies, it prints shelf empty.
  • TOP k prints up to k titles that have sold at least one copy. The titles are ordered by sold count, highest first. Titles with the same sold count are ordered alphabetically. Each line reads title sold. Nothing is printed if no title has sold.
  • Any other first word prints unknown command.

Two more rules matter. Every output line ends with a newline. The program ends normally when the input ends, with exit code 0, whatever the commands were.

Example 1

Here is the first example. Read the input and the output carefully, and check each output line against the spec before you look at the solution.

STOCK Dune 2
STOCK Emma 1
ORDER Asha Dune
ORDER Ravi Emma
ORDER Mei Dune
ORDER Dan Dune
SERVE
SERVE
SERVE
SERVE
SERVE
SHELF
TOP 2

The output is:

queued Asha Dune at position 1
queued Ravi Emma at position 2
queued Mei Dune at position 3
queued Dan Dune at position 4
served Asha Dune
served Ravi Emma
served Mei Dune
out of stock Dune for Dan
no orders
shelf empty
Dune 2
Emma 1

Walk through the first SERVE. The front order is Asha's, for Dune. Dune has two copies, so one leaves the shelf, Dune's sold count becomes 1, and the program prints served Asha Dune. The second SERVE gives Ravi's order for Emma, which has one copy, so Emma's shelf count drops to 0 and its sold count is 1. The third SERVE serves Mei for Dune, which uses the last copy, so Dune's sold count is 2. The fourth SERVE is Dan's order for Dune. There are no copies left, so the program prints out of stock Dune for Dan and drops the order. The fifth SERVE finds the line empty.

The shelf has no copies left, so SHELF prints shelf empty. Then TOP 2 lists the two titles that sold. Dune sold 2 and Emma sold 1, so Dune comes first.

Example 2

The second example checks the less common paths: an unknown command, blank lines, a title that gets copies in two steps, and a TOP with nothing sold yet.

TOP 5
STOCK Emma 3
STOCK Emma 1
ORDER Lu Emma
HELLO
 
SERVE
 
SHELF
TOP 1

The output is:

queued Lu Emma at position 1
unknown command
served Lu Emma
Emma 3
Emma 1

The first TOP 5 prints nothing, because no title has sold. The two STOCK lines add up to 4 copies. The HELLO line is not a command, so the program prints unknown command. The blank lines are skipped and print nothing. The SERVE takes Lu's order, which uses one copy, so Emma has 3 left, and the sold count is 1. Then SHELF prints Emma 3, and TOP 1 prints Emma 1.

Test your program with both examples before you go on. A program that passes only the first example is not finished.

Constraints

The input can contain up to 200000 lines. The program must run each input of that size in under one second. The counts can be large, so use int for the copies and sold counts, and remember that a single title can take up to 200000 copies. Every title and customer name is at most 20 letters long.

The program must not crash, whatever the input. That means it must check a queue or a stack for emptiness before reading its front or top, and it must not read past the end of a line. A command missing an argument, such as ORDER Asha, is not in the tests, so you do not need to handle it, but the program must still not crash on the lines the spec describes.

Requirements checklist

Tick each item when you have done it, and keep the checklist in your notes while you work.

  • Write the output for Example 1 by hand, from the spec, before you run any code.
  • Read the input one line at a time with getline, and skip blank lines.
  • Split each line into words with istringstream, and read the command word first.
  • STOCK adds copies to a map keyed by title, so SHELF can print in alphabetical order.
  • ORDER pushes the pair (customer, title) onto a queue, and prints the position as the queue size.
  • SERVE checks that the queue is not empty before it reads the front, and then pops it.
  • SERVE checks the shelf count before it sells, and prints the correct message either way.
  • SHELF prints the titles with copies above zero, and prints shelf empty when there are none.
  • TOP collects the titles with sold counts above zero, sorts them with ties broken alphabetically, and prints at most k lines.
  • Any unknown command prints unknown command.
  • The program passes both examples exactly, including the spacing of every line.
  • The program runs 200000 commands in under one second, and it does not crash on any input the spec describes.
  • You have written one short note that says which container you used for each job, and why.

Grading rubric

The grade depends on what the program does on the hidden tests. Each level includes the level below it.

60 percent. The program compiles with g++ -std=c++17, and it passes Example 1 for STOCK, ORDER, SERVE with a sale, and no orders. The queue positions are right. The program does not crash on these inputs. A program at this level stores the orders in the wrong order, or prints the positions wrongly, but it is otherwise working.

80 percent. Everything at 60 percent, and also the out-of-stock path, where the order is dropped and the message is printed. The SHELF command prints the titles in alphabetical order with the right counts, and prints shelf empty when needed. The TOP command prints the titles with the highest sold counts first, but its ties may not yet be in alphabetical order. The program prints unknown command for an unknown word. The program passes both examples.

100 percent. Everything at 80 percent, and also the following. TOP breaks ties alphabetically, and it handles a k that is larger than the number of titles that sold, and a k of zero. The program runs 200000 lines in under one second. It checks emptiness before each front, top and pop. The note on the data structures names the right container for each job, with a reason in one sentence each, and the code keeps each job in a clearly named part.

Order is part of the answer, so a line in the wrong place counts as a wrong line. Check the spacing too, because the tests compare whole lines.

Hints

Try each hint only after you have tried the step without it. Each hint is hidden below its heading.

Hint 1: the reading loop

Show hint

Read each line with getline(cin, line) inside a while loop, then put the line into an istringstream. Read the command word with >> into a string. If the read fails, the line was blank, so continue to the next line. Use continue rather than break, because the input may have more lines.

Hint 2: the three data structures

Show hint

Create one map<string, int> for the shelf, one queue of pairs for the orders, and one unordered_map<string, int> for the sold counts. Each name has one job. The shelf is printed in alphabetical order, so the map gives you that for free. The orders leave in the order they joined, so the queue is right. The sold counts are only updated and read, so the hash map is cheap.

Hint 3: the position in ORDER

Show hint

After you push the new order onto the queue, its position is the queue's size. The queue size counts the new order too, so you do not need to add one. Print the position after the push, not before.

Hint 4: the SERVE branches

Show hint

Start SERVE with the empty check, and print no orders and stop the branch there. Then copy the front pair into two local variables, and pop the queue. Only after the pop should you look at the shelf count. A common bug is to read the shelf count for the title without checking that a copy exists, which leaves the count negative.

Hint 5: a shelf count that is zero

Show hint

If you write shelf[title] on a title that is not on the shelf, the map creates it with the value 0. That is correct for the sale check, but it means SHELF must skip titles with a count of 0. The filter copies > 0 in the loop handles this. Do not rely on the map being empty.

Hint 6: the TOP comparator

Show hint

Put each title with a positive sold count into a vector of pairs, with the sold count first. Sort with a lambda. Return true when the first pair should come first. Compare the sold counts first, highest first, then compare the titles alphabetically. Then print at most k entries, checking i < k and i < rows.size() in the loop, so a large k is safe.

Hint 7: when a line has more words than you expect

Show hint

Extra words after a valid command are ignored by >>, which is what the spec wants. A missing argument makes the read fail, and the variable keeps its old value or stays empty. The spec says these lines are not in the tests, so do not spend time on them. Focus on the commands the spec describes.

Reference solution

Read the reference solution only after you have a working program, or after you have tried for an hour. Compare your version with it, and note any place where your output differs. Each difference is a bug, even if the difference looks small.

Show reference solution
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    map<string, int> stock;
    unordered_map<string, int> sold;
    queue<pair<string, string>> orders;
 
    string line;
    while (getline(cin, line)) {
        istringstream in(line);
        string cmd;
        if (!(in >> cmd)) continue;
 
        if (cmd == "STOCK") {
            string title;
            int copies;
            in >> title >> copies;
            stock[title] += copies;
        } else if (cmd == "ORDER") {
            string customer, title;
            in >> customer >> title;
            orders.push({customer, title});
            cout << "queued " << customer << " " << title << " at position " << orders.size() << endl;
        } else if (cmd == "SERVE") {
            if (orders.empty()) {
                cout << "no orders" << endl;
                continue;
            }
            auto [customer, title] = orders.front();
            orders.pop();
            if (stock[title] > 0) {
                stock[title]--;
                sold[title]++;
                cout << "served " << customer << " " << title << endl;
            } else {
                cout << "out of stock " << title << " for " << customer << endl;
            }
        } else if (cmd == "SHELF") {
            bool any = false;
            for (auto& [title, copies] : stock) {
                if (copies > 0) {
                    cout << title << " " << copies << endl;
                    any = true;
                }
            }
            if (!any) cout << "shelf empty" << endl;
        } else if (cmd == "TOP") {
            int k;
            in >> k;
            vector<pair<int, string>> rows;
            for (auto& [title, count] : sold) {
                if (count > 0) rows.push_back({count, title});
            }
            sort(rows.begin(), rows.end(), [](const auto& a, const auto& b) {
                if (a.first != b.first) return a.first > b.first;
                return a.second < b.second;
            });
            for (int i = 0; i < k && i < (int)rows.size(); i++) {
                cout << rows[i].second << " " << rows[i].first << endl;
            }
        } else {
            cout << "unknown command" << endl;
        }
    }
    return 0;
}

Why each part is there. The map gives the alphabetical shelf. The queue keeps orders first in, first out, so SERVE always takes the oldest. The unordered_map is cheap to update for every sale. The TOP branch builds its own vector, because the hash map has no order to read. The sort costs O(s log s) for s titles that sold, and that is far less than the number of commands in the worst case.

The SERVE branch reads the front into copies, auto [customer, title] = orders.front();, before pop. Because auto makes a copy, the values survive the pop. Reversing those two lines would read a value that has already been removed.

Starter program

Start from this program, which reads the lines and echoes each one. Run it on Example 1 to see the input come back. Then replace the echo with your command handling. Keep the reading loop, and keep the three containers in separate, clearly named variables.

C++ · editable

When you test, type the lines of the example into the Input box, one per line, and compare the output with the expected output word for word. A difference in one space is a real difference, because the grader compares lines exactly.

Submitting your work

Run your final program on both examples, typing each example into the Input box. Read the note you wrote about the containers. If one of the rubric items is not met, go back to the checklist and find the item that is not ticked. Fix that item, then run both examples again.

The most common reasons for a lost mark are the order of the output, a missing newline, a shelf count that goes negative, and a TOP list that prints too many lines when k is small. Check each of these before you submit.

What this assignment tested

  • Choosing a queue for first-in, first-out work, and a stack or priority queue only where the job calls for one.
  • Choosing a sorted map when output must be in key order, and a hash map when only lookup and update matter.
  • Writing a comparator for a sort with two keys, and checking emptiness before reading a front or top.
  • Parsing input line by line, with blank lines and unknown commands handled.
  • Explaining each choice of container in one sentence, with its cost.
Practice this topic: coding problems for The STL →

Stuck? Ask the tutor

Ask about anything in this lesson. Answers are short and use simple words.

Sign in to ask the tutor.

← Choosing the right container