如何找到距離大於19.0f的排序列表中的第一個元素？

pair<float,float> origin; 
list<pair<float,float> > points; 
float distance=19.0f;

如何找到具有比距離（19.0f）的距離更大的名單第一要素排序？如何申請列表二進制搜索？（迭代效率不夠，列表很長）？有沒有更優雅的解決方案？

2012-10-20 Damir

你需要一個隨機存取容器（如std :: vector）來進行二分搜索。所以我害怕在std :: list上進行二分搜索是不可能的。也許你應該使用std :: multiset來代替？ – john

@john：如果沒有必要重複，可能只是一個'set'。 –

你不能做一個鏈表二進制搜索。考慮將其替換爲vector或multiset。

2012-10-20 10:05:38

名單是不是真的適合二進制搜索。這是由於這一事實，你只能在一個列表訪問元素順序（你只能從元素k-1存取權限元素k），所以如果你必須使用一個列表，你沒有其他選擇，而不是線性的級第一搜索元素大於distance。

如果你想做，你可以使用的容器，如vector允許的元素的直接訪問（如myvector[i]）

2012-10-20 10:05:54 alestanis

不能有效鏈表上執行二進制搜索二進制搜索，這是因爲隨機存取時間爲O(n)，而O(1)是二進制搜索正常工作所必需的。

您需要通過列表迭代，沒有其他的辦法了，除非你選擇不同的數據結構。

2012-10-20 10:06:05 phant0m

使用find_if。如前所述，binary_search不能在std::list上使用，因爲您無法訪問列表中的隨機元素。

2012-10-20 10:07:39 Zoneur

你可以使用boost::flat_set它實現定期載體之上的有序容器的語義。

2012-10-20 13:32:30

回答