我的问题非常简单 - 有 unordered_map＆LT; INT，INT＆GT; 我需要跟踪最大密钥最小开销。没有在任何时刻，但在特定的闯关。详细信息如下：

My question is really simple - having unordered_map<int, int> I need to track maximum key with minimum overhead. Not at any moment, but at certain "checkpoints". More details below.

在我的交易应用程序，我想用 unordered_map 来店里手持订单项目。它应该映射 INT 到 INT ，其中关键是价格和价值是音量。 （其实价格是十进制但我在内部使用的Int64）

In my trading application I would like to use unordered_map to store OrderBook items. It should map int to int where key is price and value is volume. (actually price is decimal but i'm using int64 internally)

我要使用两个 unordered_map - 一个用于出价订单，一个是报价命令。

I'm going to use two unordered_map - one for bid orders and one for offer orders.

我需要知道出价 - 一个地图，发最小的另一个关键地图最大关键。通常情况下我有一包数的更新 - 我需要重新计算买入价和只提供在所有更新处理。例如，假设我有这样的手持订单

I need to know Bid - maximum key of one map and Offer minimum key of another map. Normally I have "several" updates in one pack - and I need to recalculate Bid and Offer only when all updates are processed. For example assume I have such orderbook

100 1
102 1
104 1

Bid (max of key) is 104.

现在我有两个更新：

remove key 104
add 103 1
end of transaction

执行应该如下：

Executing should be as follows:

1

100 1
102 1

Bid undefined (transaction in progress)

2

100 1
102 1
103 1

Bid = 103

我如何能做到这一点的用最小的延迟？延迟是最基本的要求，如果忽略延迟我可以做很多事情：

How can I do that with minimum latency ? Latency is primary requirement, if ignore latency I can do a lot of things:

这样看来，我需要一些简单的算法来跟踪最大/的一些设置分，而无需每次重新计算呢？

So it seems i need some simple algorithm to track max / min of some set without recalculating it every time?

推荐答案

您可以采取的AVL树的实现在你选择的语言，并通过信息扩展节点是什么在左树和最小密钥在右边的树最大密钥（通过引入minkey和maxkey领域IE）。

You could take an implementation of an AVL-Tree in your language of choice, and extend the nodes by the information what the minimum key in the left tree and the maximum key in the right tree is (i.e. by introducing minkey and maxkey fields).

这样做的保养应该是相当容易。对于一个新的节点，只需设置minkey = maxkey =键。在插入，无论什么时候遵循左侧或右侧路的决定，相应地更新当前节点的minkey或maxkey领域。同样的删除和旋转。通过这种方式，你永远有最低和最高的顶级节点可用。

The maintenance of this should be fairly easy. For a new node, simply set minkey = maxkey = key. On insert, whenever you make the decision to follow the left or the right path, update the minkey or maxkey field of the current node accordingly. Similarly on delete and rotations. This way, you'll always have the minimum and maximum available in the top node.

所添加的beneift将是查找可能是稍快，查找可以被终止，只要所搜索的关键字大于maxkey比minkey低级或更大。

The added beneift would be that lookups could be slightly faster, lookup can be terminated as soon as the searched key is lower than minkey or greater than maxkey.

但对我来说，是看不出来，你其实需要的是，以找到一个很好的平衡搜索树（如AVL树）的最小/最大关键应该是O（log n）的平均值，因此可能整个事情是不值得的努力。

But to me it is not apparent that you in fact would need that, as to find the minimum/maximum key in a well balanced search tree (such as an AVL Tree) should be O(log n) averaged, hence maybe the whole thing is not even worth the effort.

如果您需要快速插入/删除unordered_map（即哈希图），你至少可以达到分期常量tiome的最小值和最大值，通过维护下列数据结构：

If you need the fast insert/delete of an unordered_map (i.e. a hash map), you can at least reach amortized constant tiome for min and max, by maintaining the following data structure:

class umapminmax {
   map<int, int> themap;
   int min, max;
}

您必须插入和删除，只有通过这个类，记录最小值/最大值。每当最小或最大的密钥被删除，您需要扫描所有的钥匙，以获得新的最小值/最大值。这种扫描是O（n）。但是，如果它不发生过于频繁，访问的最小的平摊时间/最大的将仍然是恒定的。

You must insert and delete only through this class and record the minima/maxima. Whenever the minimum or the maximum key gets deleted, you need to scan all your keys to get the new minimum/maximum. This scanning is O(n). But if it doesn't happen too often, the amortized time of accessing the minimum/maximum will still be constant.

如果你知道，OTOH，它是可能的最小/最大价值往往去掉，然后O（log n）的一个搜索树的解决方案可能会以最快的速度，你可以得到的。

If you know, OTOH, that it is likely that the minimum/maximum value is removed often, then the O(log n) solution with a search tree will probably be the fastest you can get.

不过，从你如何描述你的应用程序，甚至以下是可以想象的：

Still, from how you describe your application, even the following is imaginable:

如果是这样的话，你可以申请多一点的逻辑：要说最大的密钥被删除。代替扫描的地图为新的最大现在，设置一个标志（另一个新字段），指示该最大密钥无效。然后，当偶然用钥匙是大于或等于插入无效的最大另一个值，你可以记录下这关键的最大值和复位标志，以便在指示最大有效。 当检索最大的，但是，你必须参考该标志，然后执行扫描，如果它说，这是无效的。

If this is the case, you can apply a bit more logic: Say that the maximum key gets deleted. Now, instead of scanning the map for the new maximum, set a flag (another new field) that indicates that the maximum key is not valid. Then, when by chance another value with a key that is greater or equal than the invalid maximum is inserted, you can just record this key as maximum and reset the flag so that in indicates the maximum is valid. When retrieving the maximum, however, you must consult the flag and perform a scan if it says it is invalid.

你看，你真的需要一个模型实现​​，做与真实数据的一些统计数据。

You see, you really need a model implementation and do some statistics with real world data.