1

所以假设我有这样的事情：

 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) 如果我每次都必须搜索，这会导致运行时间大大延长吗？

提前致谢

4

1 回答 1

0

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

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

如果容器尚未包含具有等效键的元素，则将元素插入容器。这将返回一个对，该对由一个指向插入元素（或阻止插入的元素）的迭代器和一个表示插入是否发生的布尔值组成。还有范围插入功能可将一组项目（由 afirst和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)复杂性的常规。

于 2013-03-30T23:01:00.680 回答