2017-01-23 20 views
1

Я создаю приложение, которое получает обновления данных о ценах с разных валютных бирж. Теперь мне нужно выбрать наиболее эффективный контейнер. Контейнер будет использовать элементы типа Entry:Какой контейнер STL для представления Bookbook?

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 лучшим выбором для этого приложения или я должен использовать другой контейнер?

+0

Наилучший подход - найти потенциального лучшего кандидата (std :: list может быть хорошим) и измерить фактическую производительность, чтобы убедиться, что он соответствует вашим потребностям. – roalz

+0

Как вы можете заказать заказ в списке? В вашем случае вставка будет в O (log (n)) в лучшем случае, так как вам нужно найти, куда вставить в список. –

+0

http://john-ahlgren.blogspot.com/2013/10/stl-container-performance.html – jamek

ответ

1

Ну, вставка списка будет постоянным, но ваш список должен быть заказан, поэтому вам нужно сначала найти правильную позицию для вставки. Это займет O(N) раз! Таким образом, гораздо предпочтительнее использовать упорядоченный контейнер на основе дерева, такой как std::multimap. Вставка или поиск займет O(log(N)) раз. Цена должна быть ключ.

+0

Точка вставки может быть найдена в log (n), если список построен упорядоченным способом. –

+0

Нет! Поскольку, в отличие от массива, вы не можете достичь своей медианной точки менее чем за время O (N) –

+0

Однако для отображения списка потребуется сначала извлечь все элементы с карты, отобразить их и затем вставить их назад (или sth like копируя карту до ее опорожнения), которая на самом деле была бы O (N · log (N)). Если список должен отображаться постоянно, это может быть не очень хорошо. – jdehesa

 Смежные вопросы

  • Нет связанных вопросов^_^