c++ - 插入/放置到位置已被占用的哈希表中

Question

假设我有这样的东西:

 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);

?

或者是否有另一种方法可以让我不必每次都搜索它？根据我的理解，平均而言，寻找特定 Assets 的时间是恒定的( O(n) 最坏情况)，但如果可能的话，我想摆脱这种搜索......

所以 1) 有没有一种方法可以添加到列表中而无需每次都搜索以查看该 Assets 是否已经在哈希表中，以及 2) 如果我每次都必须搜索，这是否会导致运行时间大幅增加更长？

提前致谢

Answer 1

来自 C++11 的无序关联容器(例如 std::unordered_set，如果你不能使用 C++11，Boost.Unordered 中有类似的容器)有几个 insert() 成员函数，特别是

std::pair<iterator,bool> insert( const value_type& value );

将一个元素插入到容器中，如果容器中还没有包含具有等效键的元素。这将返回一对由指向插入元素(或阻止插入的元素)的迭代器和表示插入是否发生的 bool 值组成的对。还有范围插入函数，用于将项目集合(由 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) 复杂度。