2
\$\begingroup\$

This is a follow up to my previous implementation:

The input is of the format

    ACTION [OID [SYMBOL SIDE QTY PX]]

    ACTION: single character value with the following definitions
    O - place order, requires OID, SYMBOL, SIDE, QTY, PX
    X - cancel order, requires OID
    P - print sorted book (see example below)

where

    OID: positive 32-bit integer value which must be unique for all orders

    SYMBOL: alpha-numeric string value. Maximum length of 8.

    SIDE: single character value buy or sell

    QTY: positive 16-bit integer value

    PX: positive double precision value (7.5 format)

and the output is as given in the sample output.

I would like further suggestions on this code, specifically if there can be made further optimizations on the broad design, as well as any speed ups. Also, given that the maximum length of the symbol is 8 (hard limit), can further optimizations be made on the nature of the struct ?

As an aside, is this how actual OrderBook implementations in HFT exchanges would occur ?

'orderbook.h':

#include <fstream>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

typedef std::vector<std::string> vector_str;

using orderid_t = uint32_t;
using qty_t = uint16_t;
using price_t = unsigned long long;
using symbol_t = std::string;

constexpr char string_delim = ' ';
constexpr int money_decimal_digits = 6;
constexpr long long money_scale = 100000;
namespace
{
  std::vector<std::string> split(std::string_view strv)
  {
    std::vector<std::string> result;
    size_t start = 0;
    while (start < strv.size())
    {
      size_t end = strv.find(string_delim, start);
      if (end == std::string_view::npos)
      {
        end = strv.size();
      }
      result.emplace_back(strv.substr(start, end - start));
      start = end + 1;
    }

    return result;
  }

}
enum class side_t : bool
{
  BUY,
  SELL
};

std::string format_7_5(price_t number)
{
  std::ostringstream out;
  out << number / money_scale
      << '.'
      << std::setw(money_decimal_digits) << std::setfill('0')
      << number % money_scale;
  return out.str();
}
struct Node
{
  orderid_t oid;
  qty_t qty;
  price_t price;
  symbol_t symbol;
  side_t side;
  std::list<Node>::iterator list_itr = {};
};

class OrderBook
{
  // mapping from order id to order
  std::map<orderid_t, Node *> &orders_map_;

public:
  std::map<price_t, std::list<Node>> Booklevel_sell_ = {};
  std::map<price_t, std::list<Node>> Booklevel_buy_ = {};
  OrderBook(std::map<orderid_t, Node *> &orders_map) : orders_map_(orders_map)
  {
  }

private:
  // Utility function to process book levels
  void processBookLevel(bool is_buy, const std::map<price_t, std::list<Node>> &bookLevel, vector_str &results)
  {
    // Iterating over bookLevel in reverse order
    for (auto level_itr = bookLevel.rbegin(); level_itr != bookLevel.rend(); ++level_itr)
    {
      const auto &curr_list = level_itr->second;

      if (is_buy)
      {
        // Process curr_list in normal order for buy orders
        for (const auto &item : curr_list)
        {
          results.emplace_back("P " + std::to_string(item.oid) + " " +
                               format_7_5(item.price) + " " +
                               std::to_string(item.qty));
        }
      }
      else
      {
        // Process curr_list in reverse order for sell orders
        for (auto item_ritr = curr_list.rbegin(); item_ritr != curr_list.rend(); ++item_ritr)
        {
          const auto &item = *item_ritr;
          results.emplace_back("P " + std::to_string(item.oid) + " " +
                               format_7_5(item.price) + " " +
                               std::to_string(item.qty));
        }
      }
    }
  }

public:
  void print(vector_str &results)
  {
    processBookLevel(false, Booklevel_sell_, results);
    processBookLevel(true, Booklevel_buy_, results);
  }

  vector_str insert_order(orderid_t oid, const symbol_t &symbol, side_t side, qty_t qty, price_t price)
  {
    // Check for duplicate orders by order ID.
    // If an order with the same ID already exists in our orders_map, return an error message.
    if (auto itr = orders_map_.find(oid); itr != orders_map_.end())
    {
      return vector_str{"E " + std::to_string(oid) + " Duplicate order id"};
    }

    vector_str final_lst{};

    // Lambda to push completed trade info (Fills) into a list for reporting.
    auto pushToFinalList = [&final_lst](orderid_t oid, const symbol_t &symbol, qty_t qty, price_t price)
    {
      final_lst.push_back("F " + std::to_string(oid) + " " + symbol + " " + std::to_string(qty) + " " + format_7_5(price));
    };

    auto qty_to_fill = qty; // Quantity of the order to be filled.

    // Lambda for handling the trade process.
    // It iterates through the order book, executes trades based on price conditions,
    // and modifies the order quantities or removes filled orders.
    auto handleTrade = [&](auto begin, auto end, auto priceCondition, auto eraser)
    {
      for (auto itr = begin; itr != end && priceCondition(itr->first) && qty_to_fill > 0;)
      {
        auto &curr_list = itr->second;

        // Iterate through each order in the current price level list.
        for (auto list_itr = curr_list.begin(); list_itr != curr_list.end() && qty_to_fill > 0;)
        {
          // Calculate the quantity to trade, which is the minimum of qty_to_fill and the current order's quantity.
          auto qty_to_trade = std::min(qty_to_fill, list_itr->qty);

          // Record the trade details for both participating orders.
          pushToFinalList(oid, symbol, qty_to_trade, price);                               // The newly inserted order.
          pushToFinalList(list_itr->oid, list_itr->symbol, qty_to_trade, list_itr->price); // The matched order.

          qty_to_fill -= qty_to_trade; // Decrease the remaining quantity to fill.

          // If the current order is fully filled, remove it and update iterator; otherwise, decrease its quantity.
          if (list_itr->qty <= qty_to_trade)
          {
            orders_map_.erase(list_itr->oid);    // Remove the order from the global map.
            list_itr = curr_list.erase(list_itr); // Remove the order from the current price level.
          }
          else
          {
            list_itr->qty -= qty_to_trade; // Deduct the traded quantity.
            ++list_itr;                    // Move to the next order in the list.
          }
        }

        // If the current list (price level) is empty after trades, remove it from the book.
        if (curr_list.empty())
        {
          itr = eraser(itr);
        }
        else
        {
          // Implies that the current price level is not empty after qty_to_fill is exhausted.
          break;
        }
      }
    };

    // Process trades for BUY orders against SELL book and vice versa.
    // Utilizes the handleTrade lambda with specific iterators and conditions based on the order side.
    if (side == side_t::BUY)
    {
      handleTrade(
          Booklevel_sell_.begin(), Booklevel_sell_.end(),
          [price](auto p)
          { return p <= price; }, // Matching condition for BUY: sell price should be <= buy order price.
          [&](auto itr)
          { return Booklevel_sell_.erase(itr); }); // Eraser for direct iterator (forward list).
    }
    else
    {
      handleTrade(
          Booklevel_buy_.rbegin(), Booklevel_buy_.rend(),
          [price](auto p)
          { return p >= price; }, // Matching condition for SELL: buy price should be >= sell order price.
          [&](auto itr) -> decltype(Booklevel_buy_.rbegin())
          {
            // Eraser for reverse iterator, requires conversion for erase and then to reverse iterator again.
            return std::make_reverse_iterator(Booklevel_buy_.erase(std::next(itr).base()));
          });
    }

    // If there's any quantity left unfilled after attempting to match, add the remaining part of the order to the book.
    if (qty_to_fill > 0)
    {
      // Select the appropriate book (buy or sell) based on the order side.
      std::map<price_t, std::list<Node>> &bookLevel = (side == side_t::BUY) ? Booklevel_buy_ : Booklevel_sell_;
      // Add the unfilled order to the book.
      bookLevel[price].push_back(Node{oid, qty_to_fill, price, symbol, side});
      // Keep a direct reference to the order in the global orders map for quick access.
      orders_map_[oid] = &*(bookLevel[price].rbegin());
      orders_map_[oid]->list_itr = --(bookLevel[price].end());
    }

    return final_lst; // Return the list of filled trades.
  }
};
class UnifiedOrderBook
{
  std::unordered_map<std::string, OrderBook> ob_;
  std::map<orderid_t, Node *> orders_map_;

public:
  vector_str print()
  {
    auto ans = vector_str();
    for (auto it = ob_.begin(); it != ob_.end(); ++it)
    {
      it->second.print(ans);
    }
    return ans;
  }
  bool cancel_order(orderid_t oid)
  {
    auto itr = orders_map_.find(oid);
    if (itr == orders_map_.end())
    {
      return false;
    }

    auto &curr_node = itr->second;
    auto &ob = ob_.find(curr_node->symbol)->second;
    auto &bookLevel = curr_node->side == side_t::BUY ? ob.Booklevel_buy_ : ob.Booklevel_sell_;

    // Directly accessing the price level.
    auto &priceLevel = bookLevel[curr_node->price];

    // Erase the order from the list.
    priceLevel.erase(curr_node->list_itr);

    // If the price level becomes empty after erasure, remove it from the bookLevel.
    if (priceLevel.empty())
    {
      bookLevel.erase(curr_node->price);
    }

    orders_map_.erase(itr);
    return true;
  }
  vector_str insert_order(orderid_t oid, const symbol_t &symbol, side_t side, qty_t qty, price_t price)
  {
    auto book_itr = ob_.find(symbol);
    if (book_itr == ob_.end())
    {
      auto insert_result = ob_.emplace(std::make_pair(symbol, OrderBook(orders_map_)));
      book_itr = insert_result.first;
    }
    return book_itr->second.insert_order(oid, symbol, side, qty, price);
  }
};

class SimpleCross
{
public:
  vector_str process(const std::string &line)
  {
    auto tokens_vec = split(line);
    switch (tokens_vec[0][0])
    {
    case 'P':
    {
      return uob_.print();
    }
    case 'X':
    {
      return uob_.cancel_order(static_cast<orderid_t>(std::stoul(tokens_vec[1]))) ? vector_str{line} : vector_str{"E OrderID not found"};
    }
    case 'O':
    {
      double price;
      orderid_t order_id;
      qty_t qty;
      side_t side;
      try
      {
        order_id = static_cast<orderid_t>(std::stoul(tokens_vec[1]));
      }
      catch (...)
      {
        return vector_str{"E Invalid order id"};
      }
      try
      {
        qty = static_cast<qty_t>(std::stoul(tokens_vec[4]));
      }
      catch (...)
      {
        return vector_str{"E Invalid quantity"};
      }
      try
      {
        price = std::stod(tokens_vec[5]);
      }
      catch (...)
      {
        return vector_str{"E Invalid price"};
      }
      if (tokens_vec[3] == "B")
      {
        side = side_t::BUY;
      }
      else if (tokens_vec[3] == "S")
      {
        side = side_t::SELL;
      }
      else
      {
        return vector_str{"E Invalid side provided"};
      }
      return uob_.insert_order(order_id, tokens_vec[2], side, qty, static_cast<price_t>(price * 1e5));
    }
    default:
      return vector_str{"E invalid arguments provided"};
    }
    return vector_str{"E invalid arguments provided"};
  }
  vector_str action(const std::string &line)
  {
    return process(line);
  }

private:
  UnifiedOrderBook uob_;
};

void driver(const std::string &inputFilename, const std::string &outputFilename = "")
{
  SimpleCross scross;
  std::string line;
  std::ifstream actions(inputFilename, std::ios::in);

  std::ofstream outFile;
  bool useFileOutput = !outputFilename.empty();

  if (useFileOutput)
  {
    outFile.open(outputFilename, std::ios::out);
  }

  while (std::getline(actions, line))
  {
    vector_str results = scross.action(line);
    for (vector_str::const_iterator it = results.begin(); it != results.end(); ++it)
    {
      if (useFileOutput)
      {
        outFile << *it << std::endl;
      }
      else
      {
        std::cout << *it << std::endl;
      }
    }
  }
}

Main CPP program


#include "orderbook.h"

int main(int argc, char **argv)
{

  std::string filename = "actions.txt";
  if (argc > 1)
  {
    filename = argv[1];
  }
  driver(filename);
  return 0;
}

Sample Input

O 10000 AAPL B 10 100.0
O 10001 AAPL B 10 99.0
O 10002 AAPL S 5 101.0
O 10003 AAPL S 5 100.0
O 10004 AAPL S 6 100.0
X 10002
O 10005 AAPL B 10 99.0
O 10006 AAPL B 10 100.0
O 10007 AAPL S 10 101.0
O 10008 AAPL S 10 102.0
O 10008 AAPL S 10 102.0
O 10009 AAPL S 10 102.0
P
O 10010 AAPL B 13 102.0

Sample Output

F 10003 AAPL 5 100.000000
F 10000 AAPL 5 100.000000
F 10004 AAPL 5 100.000000
F 10000 AAPL 5 100.000000
X 10002
F 10006 AAPL 1 100.000000
F 10004 AAPL 1 100.000000
E 10008 Duplicate order id
P 10009 102.000000 10
P 10008 102.000000 10
P 10007 101.000000 10
P 10006 100.000000 9
P 10001 99.000000 10
P 10005 99.000000 10
F 10010 AAPL 10 102.000000
F 10007 AAPL 10 101.000000
F 10010 AAPL 3 102.000000
F 10008 AAPL 3 102.000000
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Welcome to Code Review! Incorporating advice from an answer into the question violates the question-and-answer nature of this site. You could post improved code as a new question, as an answer, or as a link to an external site - as described in I improved my code based on the reviews. What next?. I have rolled back the edit, so the answers make sense again. \$\endgroup\$ Oct 29, 2023 at 19:59
  • 1
    \$\begingroup\$ @Avengerx9 please see the feedback from flags by going to your profile and in the Impact section click the link under "X helpful flags" \$\endgroup\$ Oct 30, 2023 at 0:28
  • 1
    \$\begingroup\$ Please use the contact form instead, this will put you in contact with people who may or may not be able to help you. Moderators are ill-equipped for legal matters so if you ask them/us, we will simply decline the flag. \$\endgroup\$
    – Mast
    Oct 30, 2023 at 7:02

1 Answer 1

3
\$\begingroup\$

There are no include guards for the header.

 using orderid_t = uint32_t;

uint32_t is not defined. I recommend

#include <cstdint>

using orderid_t = std::uint32_t;

(similarly for the other fixed-width types). Note that this will fail to compile on platforms that don't have an exactly-32-bit integer type, so you might to consider std::uint_fast32_t or std::uint_least32_t as a more portable alternative.

There's a lot in this header file that I would expect to be only in the implementation. In particular, there are definitions of functions with external linkage, which will prevent linking of programs that include this header into multiple translation units.

We should put the minimum necessary declarations into the header for users to be able to call our functions. Everything non-public should go into a separate implementation file.

split() takes argument of std::string_view, but we forgot to include <string_view> standard header.

Moving to the main function, we're still producing no diagnostic when we fail to read input. A simple way to get started would be to set the streams to throw exceptions on failure:

  std::ifstream actions(inputFilename, std::ios::in);
  actions.exceptions(std::ios::failbit | std::ios::badbit);

The driver() function is complicated by switching between file and standard-output streams within it. It's better to set up the input and output streams as references to base-class std::istream and std::ostream and then the rest of the code doesn't need to know which stream type it's using:


void driver(const std::string &inputFilename, const std::string &outputFilename = "")
{
    std::ifstream actionsFile;
    std::istream& actions = inputFilename.empty() ? std::cin : (actionsFile.open(inputFilename), actionsFile);
    actions.exceptions(std::ios::failbit | std::ios::badbit);

    std::ofstream outFile;
    std::ostream& output = outputFilename.empty() ? std::cout : (outFile.open(outputFilename), outFile);
    output.exceptions(std::ios::failbit | std::ios::badbit);


    SimpleCross scross;
    std::string line;
    while (std::getline(actions, line)) {
        vector_str results = scross.action(line);
        for (auto const& result: results) {
            output << result << '\n';
      }
    }
    output << std::flush;
}

When I ran the program with the provided input, I discovered a use-after-free error. This should be investigated and fixed:

valgrind --leak-check=full ./287667 <287667.in

==3826612== Memcheck, a memory error detector
==3826612== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==3826612== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==3826612== Command: ./287667
==3826612== 
F 10003 AAPL 5 100.000000
F 10000 AAPL 5 100.000000
F 10004 AAPL 5 100.000000
F 10000 AAPL 5 100.000000
==3826612== Invalid read of size 8
==3826612==    at 0x113497: std::less<unsigned long long>::operator()(unsigned long long const&, unsigned long long const&) const (stl_function.h:408)
==3826612==    by 0x115BF2: std::_Rb_tree<unsigned long long, std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > >, std::_Select1st<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::equal_range(unsigned long long const&) (stl_tree.h:2020)
==3826612==    by 0x113BB0: std::_Rb_tree<unsigned long long, std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > >, std::_Select1st<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::erase(unsigned long long const&) (stl_tree.h:2519)
==3826612==    by 0x111EDA: std::map<unsigned long long, std::__cxx11::list<Node, std::allocator<Node> >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::erase(unsigned long long const&) (stl_map.h:1119)
==3826612==    by 0x10EA36: UnifiedOrderBook::cancel_order(unsigned int) (287667.cpp:262)
==3826612==    by 0x10F252: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:294)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612==  Address 0x4dcb108 is 24 bytes inside a block of size 80 free'd
==3826612==    at 0x484399B: operator delete(void*, unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3826612==    by 0x118DF5: std::__new_allocator<std::_List_node<Node> >::deallocate(std::_List_node<Node>*, unsigned long) (new_allocator.h:168)
==3826612==    by 0x114BDB: deallocate (allocator.h:210)
==3826612==    by 0x114BDB: deallocate (alloc_traits.h:516)
==3826612==    by 0x114BDB: std::__cxx11::_List_base<Node, std::allocator<Node> >::_M_put_node(std::_List_node<Node>*) (stl_list.h:522)
==3826612==    by 0x1132CC: std::__cxx11::list<Node, std::allocator<Node> >::_M_erase(std::_List_iterator<Node>) (stl_list.h:2024)
==3826612==    by 0x111851: std::__cxx11::list<Node, std::allocator<Node> >::erase(std::_List_const_iterator<Node>) (list.tcc:158)
==3826612==    by 0x10EA0C: UnifiedOrderBook::cancel_order(unsigned int) (287667.cpp:257)
==3826612==    by 0x10F252: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:294)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612==  Block was alloc'd at
==3826612==    at 0x4840F2F: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3826612==    by 0x119255: std::__new_allocator<std::_List_node<Node> >::allocate(unsigned long, void const*) (new_allocator.h:147)
==3826612==    by 0x1171AB: allocate (allocator.h:198)
==3826612==    by 0x1171AB: allocate (alloc_traits.h:482)
==3826612==    by 0x1171AB: std::__cxx11::_List_base<Node, std::allocator<Node> >::_M_get_node() (stl_list.h:518)
==3826612==    by 0x115320: std::_List_node<Node>* std::__cxx11::list<Node, std::allocator<Node> >::_M_create_node<Node>(Node&&) (stl_list.h:710)
==3826612==    by 0x1137A9: void std::__cxx11::list<Node, std::allocator<Node> >::_M_insert<Node>(std::_List_iterator<Node>, Node&&) (stl_list.h:2005)
==3826612==    by 0x111C52: std::__cxx11::list<Node, std::allocator<Node> >::push_back(Node&&) (stl_list.h:1311)
==3826612==    by 0x10E67A: OrderBook::insert_order(unsigned int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, side_t, unsigned short, unsigned long long) (287667.cpp:217)
==3826612==    by 0x10EC16: UnifiedOrderBook::insert_order(unsigned int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, side_t, unsigned short, unsigned long long) (287667.cpp:276)
==3826612==    by 0x10F687: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:338)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612== 
==3826612== Invalid read of size 8
==3826612==    at 0x113490: std::less<unsigned long long>::operator()(unsigned long long const&, unsigned long long const&) const (stl_function.h:408)
==3826612==    by 0x115C2D: std::_Rb_tree<unsigned long long, std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > >, std::_Select1st<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::equal_range(unsigned long long const&) (stl_tree.h:2022)
==3826612==    by 0x113BB0: std::_Rb_tree<unsigned long long, std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > >, std::_Select1st<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::erase(unsigned long long const&) (stl_tree.h:2519)
==3826612==    by 0x111EDA: std::map<unsigned long long, std::__cxx11::list<Node, std::allocator<Node> >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::erase(unsigned long long const&) (stl_map.h:1119)
==3826612==    by 0x10EA36: UnifiedOrderBook::cancel_order(unsigned int) (287667.cpp:262)
==3826612==    by 0x10F252: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:294)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612==  Address 0x4dcb108 is 24 bytes inside a block of size 80 free'd
==3826612==    at 0x484399B: operator delete(void*, unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3826612==    by 0x118DF5: std::__new_allocator<std::_List_node<Node> >::deallocate(std::_List_node<Node>*, unsigned long) (new_allocator.h:168)
==3826612==    by 0x114BDB: deallocate (allocator.h:210)
==3826612==    by 0x114BDB: deallocate (alloc_traits.h:516)
==3826612==    by 0x114BDB: std::__cxx11::_List_base<Node, std::allocator<Node> >::_M_put_node(std::_List_node<Node>*) (stl_list.h:522)
==3826612==    by 0x1132CC: std::__cxx11::list<Node, std::allocator<Node> >::_M_erase(std::_List_iterator<Node>) (stl_list.h:2024)
==3826612==    by 0x111851: std::__cxx11::list<Node, std::allocator<Node> >::erase(std::_List_const_iterator<Node>) (list.tcc:158)
==3826612==    by 0x10EA0C: UnifiedOrderBook::cancel_order(unsigned int) (287667.cpp:257)
==3826612==    by 0x10F252: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:294)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612==  Block was alloc'd at
==3826612==    at 0x4840F2F: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3826612==    by 0x119255: std::__new_allocator<std::_List_node<Node> >::allocate(unsigned long, void const*) (new_allocator.h:147)
==3826612==    by 0x1171AB: allocate (allocator.h:198)
==3826612==    by 0x1171AB: allocate (alloc_traits.h:482)
==3826612==    by 0x1171AB: std::__cxx11::_List_base<Node, std::allocator<Node> >::_M_get_node() (stl_list.h:518)
==3826612==    by 0x115320: std::_List_node<Node>* std::__cxx11::list<Node, std::allocator<Node> >::_M_create_node<Node>(Node&&) (stl_list.h:710)
==3826612==    by 0x1137A9: void std::__cxx11::list<Node, std::allocator<Node> >::_M_insert<Node>(std::_List_iterator<Node>, Node&&) (stl_list.h:2005)
==3826612==    by 0x111C52: std::__cxx11::list<Node, std::allocator<Node> >::push_back(Node&&) (stl_list.h:1311)
==3826612==    by 0x10E67A: OrderBook::insert_order(unsigned int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, side_t, unsigned short, unsigned long long) (287667.cpp:217)
==3826612==    by 0x10EC16: UnifiedOrderBook::insert_order(unsigned int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, side_t, unsigned short, unsigned long long) (287667.cpp:276)
==3826612==    by 0x10F687: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:338)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612== 
==3826612== Invalid read of size 8
==3826612==    at 0x113497: std::less<unsigned long long>::operator()(unsigned long long const&, unsigned long long const&) const (stl_function.h:408)
==3826612==    by 0x116CF9: std::_Rb_tree<unsigned long long, std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > >, std::_Select1st<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::_M_lower_bound(std::_Rb_tree_node<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > >*, std::_Rb_tree_node_base*, unsigned long long const&) (stl_tree.h:1952)
==3826612==    by 0x115CBA: std::_Rb_tree<unsigned long long, std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > >, std::_Select1st<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::equal_range(unsigned long long const&) (stl_tree.h:2031)
==3826612==    by 0x113BB0: std::_Rb_tree<unsigned long long, std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > >, std::_Select1st<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::erase(unsigned long long const&) (stl_tree.h:2519)
==3826612==    by 0x111EDA: std::map<unsigned long long, std::__cxx11::list<Node, std::allocator<Node> >, std::less<unsigned long long>, std::allocator<std::pair<unsigned long long const, std::__cxx11::list<Node, std::allocator<Node> > > > >::erase(unsigned long long const&) (stl_map.h:1119)
==3826612==    by 0x10EA36: UnifiedOrderBook::cancel_order(unsigned int) (287667.cpp:262)
==3826612==    by 0x10F252: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:294)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612==  Address 0x4dcb108 is 24 bytes inside a block of size 80 free'd
==3826612==    at 0x484399B: operator delete(void*, unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3826612==    by 0x118DF5: std::__new_allocator<std::_List_node<Node> >::deallocate(std::_List_node<Node>*, unsigned long) (new_allocator.h:168)
==3826612==    by 0x114BDB: deallocate (allocator.h:210)
==3826612==    by 0x114BDB: deallocate (alloc_traits.h:516)
==3826612==    by 0x114BDB: std::__cxx11::_List_base<Node, std::allocator<Node> >::_M_put_node(std::_List_node<Node>*) (stl_list.h:522)
==3826612==    by 0x1132CC: std::__cxx11::list<Node, std::allocator<Node> >::_M_erase(std::_List_iterator<Node>) (stl_list.h:2024)
==3826612==    by 0x111851: std::__cxx11::list<Node, std::allocator<Node> >::erase(std::_List_const_iterator<Node>) (list.tcc:158)
==3826612==    by 0x10EA0C: UnifiedOrderBook::cancel_order(unsigned int) (287667.cpp:257)
==3826612==    by 0x10F252: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:294)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612==  Block was alloc'd at
==3826612==    at 0x4840F2F: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3826612==    by 0x119255: std::__new_allocator<std::_List_node<Node> >::allocate(unsigned long, void const*) (new_allocator.h:147)
==3826612==    by 0x1171AB: allocate (allocator.h:198)
==3826612==    by 0x1171AB: allocate (alloc_traits.h:482)
==3826612==    by 0x1171AB: std::__cxx11::_List_base<Node, std::allocator<Node> >::_M_get_node() (stl_list.h:518)
==3826612==    by 0x115320: std::_List_node<Node>* std::__cxx11::list<Node, std::allocator<Node> >::_M_create_node<Node>(Node&&) (stl_list.h:710)
==3826612==    by 0x1137A9: void std::__cxx11::list<Node, std::allocator<Node> >::_M_insert<Node>(std::_List_iterator<Node>, Node&&) (stl_list.h:2005)
==3826612==    by 0x111C52: std::__cxx11::list<Node, std::allocator<Node> >::push_back(Node&&) (stl_list.h:1311)
==3826612==    by 0x10E67A: OrderBook::insert_order(unsigned int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, side_t, unsigned short, unsigned long long) (287667.cpp:217)
==3826612==    by 0x10EC16: UnifiedOrderBook::insert_order(unsigned int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, side_t, unsigned short, unsigned long long) (287667.cpp:276)
==3826612==    by 0x10F687: SimpleCross::process(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:338)
==3826612==    by 0x10FD52: SimpleCross::action(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:347)
==3826612==    by 0x10C7C3: driver(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (287667.cpp:368)
==3826612==    by 0x10C9F7: main (287667.cpp:388)
==3826612== 
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.