order.cpp

#include <set>
#include <cassert>
#include <optional>
#include <algorithm>
#include <unordered_map>

struct Order {
    using id_type = uint64_t;

    enum Side {
        SELL = 0,
        BUY,
    };

    id_type id;
    Side side;
    float price;

    Order(id_type id, Side side, float price) noexcept
        : id(id), side(side), price(price) {}

    bool operator<(const Order &rhs) const noexcept {
        // Move sell orders to the head and buy to the tail
        if (side != rhs.side)
            return side == SELL;

        if (price != rhs.price)
            return price < rhs.price;

        // If the have the same price and side,
        // order to return the first added
        if (side == SELL)
            return id < rhs.id;
        else
            return id > rhs.id;
    }
};

class OrderBook {
    public:
        explicit OrderBook() noexcept : cur_id(0) {}

        std::optional<Order> addOpenOrder(Order::Side side, float price) {
            auto ret = orders.emplace(cur_id, side, price);
            ++cur_id;
            if (ret.second) {
                indexes.emplace(std::make_pair(cur_id - 1, ret.first));
                return std::optional(*ret.first);
            } else {
                return std::optional<Order>();
            }
        }

        bool deleteOrder(Order::id_type id) {
            auto it = indexes.find(id);
            if (it != indexes.end()) {
                orders.erase(it->second);
                indexes.erase(it);
                return true;
            }

            return false;
        }

        std::optional<Order> bestOpenOrder(Order::Side side) const noexcept {
            if (orders.empty())
                return std::optional<const Order>();

            typename map_type::const_iterator it;
            if (side == Order::SELL) {
                it = std::cbegin(orders);
            } else {
                it = std::cend(orders);
                std::advance(it, -1);
            }

            // The list of orders may not be empty, but it may not contain an order
            // of the side we are looking for
            if (side != it->side)
                return std::optional<const Order>();

            return std::optional(*it);
        }

    private:
        using map_type = std::set<Order>;
        using index_type = std::unordered_map<Order::id_type, typename map_type::const_iterator>;
        map_type orders;
        index_type indexes;
        Order::id_type cur_id;
};

int main() {
    OrderBook book; 
	auto order1 = book.addOpenOrder(Order::BUY, 10).value();
	assert (book.bestOpenOrder(Order::BUY).value().id == order1.id);
	auto order2 = book.addOpenOrder(Order::BUY, 10).value();
	assert (book.bestOpenOrder(Order::BUY).value().id == order1.id);
	auto order3 = book.addOpenOrder(Order::BUY, 12).value();
	auto order4 = book.addOpenOrder(Order::SELL, 11).value();
	assert (book.bestOpenOrder(Order::SELL).value().id == order4.id);
	auto order5 = book.addOpenOrder(Order::SELL, 11).value();
	assert (book.bestOpenOrder(Order::SELL).value().id == order4.id);
	auto order6 = book.addOpenOrder(Order::SELL, 20).value();
	assert (book.bestOpenOrder(Order::BUY).value().id == order3.id);
	assert (book.bestOpenOrder(Order::SELL).value().price == 11);
	assert (book.deleteOrder(order3.id));
	assert (book.bestOpenOrder(Order::SELL).value().price == 11);
	assert (book.bestOpenOrder(Order::BUY).value().id == order1.id);
    return 0;
}