注文表記のためのSTLコンテナはどれですか？

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))時間がかかります。価格はキーにする必要があります。