是否有一個類似地圖的容器的實現，其中實數是鍵，並且可以通過鍵範圍檢索一組對象？

Question

對的列表或向量可用作此類容器，但除非使用某種索引，否則訪問時間將爲O（N）。是否可以使用內置索引的這種容器的C++實現，以便訪問時間爲O（log（N））？

是否有兩個或兩個以上的實數可用作密鑰的實現？ （仍然比O（N）訪問時間快）？

Answer 1

二叉搜索樹可能是解決方案。您可以在O(log(N))時間範圍內找到最低鍵和最高鍵。通過簡單地遍歷樹，檢索兩個對象之間的對象應該是O(k)（其中k是找到的對象的數量）。

std::map應該是一個很好的開始，與std::map::lower_bound和std::map::upper_bound一起使用（兩者都保證有最大的對數複雜度）。