哪个STL容器用于Orderbook表示？

Question

我正在构建一个应用程序，它接收来自不同货币交易所的价格数据更新。现在我需要选择最有效的容器。容器将使用Entry类型的元素

struct Entry
{
    std::string exchange_name;
    double price;
    double amount;
}

条目必须按其价格升序排序：

Ex.Name    Price    Amount
  "A"       1.2       23
  "B"       1.3       3
  "A"       1.4       1.2
  "C"       1.5       4
  "A"       1.6       2

容器上将有许多插入和删除操作。我猜最高可以达到每秒200个。容器内的值不能为const，因此可以针对特定条目更改数量。

到目前为止，我的结论是std::list可能是一个很好的选择，因为它是allows constant time insert and erase operations anywhere within the sequence的。

std::list是此应用程序的最佳选择，还是我应该使用其他容器？

Answer 1

那么，列表插入将是固定的时间，但是你的列表应该是有序的，因此，你需要首先找到一个合适的插入位置。这将花费O(N)时间！因此，更有效的方法是使用基于有序树的容器，比如std::multimap。插入或搜索将占用O(log(N))时间。价格应该是关键。