可能實現的std ::的equal_range

Question

std::equal_range上cppreference.com文檔顯示了一個可能的實現：

template<class ForwardIt, class T> 
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last, 
       const T& value) 
{ 
    return std::make_pair(std::lower_bound(first, last, value), 
          std::upper_bound(first, last, value)); 
} 

但這看起來更優化的同時仍然很簡單：

template<class ForwardIt, class T> 
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last, 
       const T& value) 
{ 
    first = std::lower_bound(first, last, value); 
    return std::make_pair(first, 
          std::upper_bound(first, last, value)); 
} 

因爲該解決方案是很明顯的，有什麼理由不使用？

Answer 1

上cppreference給出的實現是可能的實施，不一定是最優化的實施。我認爲這是爲了清楚起見，以便讀者能夠更好地理解該算法在內部執行的操作，而不是作爲所有可能的最快實現的指導。

只要您優化實現，您可能會考慮使用一些邏輯來檢查範圍是否較小，如果是，則使用線性搜索而不是二分查找。

查看實際實施以瞭解其結構可能會有幫助。看一看，比如the libstdc++ implementation，它比cppreference中給出的更清晰但效率更低的版本更加難讀。該版本 - 截至撰寫本文時爲止 - 使用完全不同的方法：

1. 使用初始二進制搜索來搜索元素的任何副本。
2. 在剩餘窗口中使用二級二分查找來查找該範圍內元素的第一個和最後一個副本。

這種方法可能會比您提出的要快，因爲可以共享兩個二進制搜索中的大量工作。