哪個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))時間。價格應該是密鑰。