帶「最大和最小鍵」跟蹤的unordered_map？

Question

我的問題很簡單 - 有unordered_map<int, int>我需要以最小的開銷跟蹤maximum key。不是在任何時候，而是在某些「檢查站」。以下更多細節。

在我的交易應用程序中，我想用unordered_map來存儲OrderBook項目。它應該映射int到int其中關鍵是價格和價值是音量。 （實際價格是十進制但我在內部使用int64）

我打算使用兩個unordered_map - 一個用於bid訂單和一個用於offer訂單。

我需要知道Bid - 一張地圖的最大關鍵字和另一張地圖的最小關鍵字Offer。通常我在一個包中有「幾個」更新 - 我只需要在處理所有更新時重新計算出價和出價。例如，假設我有這樣手持訂單

100 1 
102 1 
104 1 

Bid (max of key) is 104. 

現在我有兩個更新：

remove key 104 
add 103 1 
end of transaction 

執行應該如下：

1：

100 1 
102 1 

Bid undefined (transaction in progress) 

2：

100 1 
102 1 
103 1 

Bid = 103 

我該怎麼做最小延遲？延遲是最基本的要求，如果忽略延遲我可以做很多事情：

• 非常容易：只要掃描所有按鍵，並找到最好的買入/賣出價，如果前一個已被刪除
• 我甚至可以用有序映射

所以看來我需要一些簡單的算法來跟蹤某些設置的最大/最小值，而無需每次重新計算它？

Answer 1

你可以用你選擇的語言來實現一個AVL樹，並通過左樹中的最小密鑰和右樹中最大密鑰的信息來擴展節點（即通過引入minkey和maxkey字段）。

維護這應該是相當容易的。對於新節點，只需設置minkey = maxkey = key。在插入時，無論您何時決定遵循左側還是右側路徑，都應相應地更新當前節點的minkey或maxkey字段。同樣在刪除和旋轉。通過這種方式，您始終可以在頂級節點中獲得最小和最大值。

增加的好處是查找速度可能會稍微快一些，只要搜索到的關鍵字低於minkey或大於maxkey，查找就會終止。

但是對我來說，事實上你並不需要這麼做，因爲在平衡良好的搜索樹（如AVL樹）中查找最小/最大鍵應該是O（log n）平均值，因此也許整件事情都不值得。

如果您需要快速插入/刪除unordered_map（即哈希映射），你至少可以達到攤銷的最小和最大恆tiome，通過保持數據結構如下：

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

您必須插入，只有通過這個類中刪除並記錄最小值/最大值。無論何時刪除最小或最大密鑰，都需要掃描所有密鑰以獲取新的最小/最大值。這個掃描是O（n）。但是，如果不經常發生，獲取最小/最大值的分期時間仍將保持不變。

如果您知道，OTOH經常會刪除最小值/最大值，那麼使用搜索樹的O（log n）解決方案可能會以最快速度獲得。

不過，從如何描述你的應用程序，甚至以下是可以想象的：

• 它經常發生，即最大被刪除。但是，在下一次詢問當前最大值之前，通常會插入新的最大值。

如果是這種情況，您可以應用更多的邏輯：假設最大的密鑰被刪除。現在，而不是掃描新的最大值的地圖，設置一個標誌（另一個新的字段），指出最大的密鑰無效。然後，如果插入另一個大於或等於無效最大值的鍵值，則可以將此鍵記錄爲最大值並重置該標誌，以便in表示最大值有效。 但是，如果檢索到最大值，則必須查閱該標誌並執行掃描，如果該標誌無效。

你看，你真的需要一個模型實現，並用真實世界的數據做一些統計。