Top-of-Book Ticker

You are building the ticker component of a market data feed: after every order book event, it must publish the current top of book (best bid and best ask).

You receive a sequence of events. Each event is one of:

• an add event with an order_id, a side, a price and a qty: a new limit order enters the book. side is B for a bid (buy) or S for an ask (sell). Prices are integer ticks. order_id values of add events are unique.
• a cancel event with an order_id: the order leaves the book. A cancel may reference an id that was never added or was already cancelled; treat that as a no-op.

Implement top_of_book(events) returning one entry per event: the pair (best_bid, best_ask) immediately after applying that event. The best bid is the highest live bid price, the best ask is the lowest live ask price. A side with no live orders has no price. Order quantity never changes and does not affect the top of book in this problem.

struct Event {
    std::string kind;        // "add" or "cancel"
    long long order_id = 0;
    char side = 0;           // 'B' or 'S'; unused on a cancel
    long long price = 0;
    long long qty = 0;
};

std::vector<std::pair<std::optional<long long>, std::optional<long long>>> top_of_book(
    const std::vector<Event>& events);

The Event struct is declared in the scaffold and the tests build the stream with it: an add is {"add", 1, 'B', 100, 5} and a cancel is {"cancel", 1}. Each result entry is {best_bid, best_ask}, with std::nullopt for a side with no live orders.

Orders are never matched against each other. A bid at or above the best ask does not trade: both orders stay live until they are cancelled, so the book can be crossed (best bid greater than or equal to best ask).

Example

std::vector<Event> events = {
    {"add", 1, 'B', 100, 5},
    {"add", 2, 'S', 102, 3},
    {"add", 3, 'B', 101, 2},
    {"cancel", 3},
};
top_of_book(events);
// {{100, std::nullopt}, {100, 102}, {101, 102}, {100, 102}}

Constraints

• Up to \(10^6\) events.
• Prices are positive integers; multiple live orders may share a price.
• Your solution must handle the event volume comfortably: recomputing the best price by scanning every live order on every event will not finish in time.