如何根據多個參數在容器中查找對象的範圍

Question

我在尋找從大型集合中提取對象的最佳方法，它們的位置來自兩個排序的參數。

例子：

struct Object{ 
    Time start; 
    Time end; 
    //... data 
}; 

現在，任何時候t我想迅速找到所有對象「存在」這段時間內，即t是對象的start和end值之間。

我想到的方法是使用：

std::multimap<Time, object*> objectsOrderedByStart; 
std::multimap<Time, object*> objectsOrderedByEnd; 

（multimap因爲可能有很多對象具有相同Time值，這是分類鍵）

每次我創建Object我將它添加到每個multimap，它會自動將對象放置在start和end的排序列表中。

然後我在那裏objectsOrderedByStart和t>Time對象objectsOrderedByEnd其中t<End尋找所有對象，然後只服用那些在這兩個結果集「查詢」我的時間t有效對象。但是這看起來效率低下，我能想到的找到聯合的唯一方法是逐個查看一個結果集並查看該對象是否在另一個結果集中。

但是我懷疑這不是最有效的方法。當迭代每個multimap而不是逐個迭代時，我可以通過跳過元素來進行迭代，然後如果我太過分並從最後一個跳過點一個接一個地迭代，則會退回。或者，我可以保留一個multimap，然後在每個object內部對等以查看它的end時間。

但我懷疑有更好的方法來組織這些數據並找到那些對我感興趣的範圍？

Answer 1

您可以使用兩個手動排序的數組而不是兩個multimaps，然後使用std::lower_bound和std::upper_bound或手動編碼的二進制搜索來搜索它們。

Answer 2

我想你應該看看Boost.ICL