вставка / вставка в хеш-таблицу, где позиция уже занята
Допустим, у меня есть что-то вроде этого:
struct equity{ ///keep in hash table
long long numSharesTraded;
list<order> buyList;
list<order> sellList; //put in priority queue
};
если я хочу вставить что-либо в buyList или sellList, нужно ли мне проверять и видеть, где в хэш-таблице находится конкретный эквити, список которого я должен добавить? … так что в итоге я получаю что-то вроде:
map[i].equity.buyList.push_back(orderI'mPushing);
?
или есть другой способ, которым я могу сделать это без необходимости искать его каждый раз? Насколько я понимаю, поиск конкретного капитала в среднем происходит за постоянное время (O (n) в худшем случае), но я бы хотел избавиться от этого поиска, если это вообще возможно …
Итак, 1) есть ли способ добавить в список без поиска, чтобы увидеть, находится ли этот эквити в хэш-таблице каждый раз, и 2) если мне придется искать каждый раз, приведет ли это к тому, что время выполнения будет значительно длиннее?
заранее спасибо
Решение
Неупорядоченные ассоциативные контейнеры из C ++ 11 (например, std::unordered_setесть похожие контейнеры в Boost.Unordered если вы не можете использовать C ++ 11) есть несколько insert() функции-члены, в частности
std::pair<iterator,bool> insert( const value_type& value );
вставляет элемент в контейнер, если контейнер еще не содержит элемент с эквивалентным ключом. Это возвращает пару, состоящую из итератора для вставленного элемента (или элемента, который предотвратил вставку) и логическое значение, обозначающее, произошла ли вставка. Есть также функция вставки в диапазоне для вставки коллекции элементов (разделенных first а также last итератор) в ваш контейнер.
Вы можете использовать это так (использовать std::unordered_map если вы хотите хранить больше вещей вместе с заказом):
struct equity { /* like before */ };
std::unordered_set<equity> orders;
auto result = orders.insert(orderI'mPushing);
if (result.second)
// handle first-time insert by reusing result.first
else
// item was already stored
Отдельные вставки амортизируются O(1) сложность, что означает, что вставка большого количества N элементы имеет O(N) сложность времени. Таким образом, в среднем, вы не должны иметь никаких штрафов от повторных поисков.
Однако, если вы занимаетесь торговлей на сверхвысоких частотах и сталкиваетесь с задержками в режиме реального времени для отдельных вставок, вы можете использовать обычную std::set который имеет более медленный, но более предсказуемый O(log N) сложность.
Другие решения
Других решений пока нет …
detector