C++ STL二進制搜索（LOWER_BOUND，UPPER_BOUND）

Question

我實現了一個二進制搜索這樣的：

typedef std::vector<Cell>::iterator CellVectorIterator; 

typedef struct _Point { 
    char x,y; 
} CoordinatePoint; 

typedef struct _Cell { 
    ... 
    CoordinatePoint coordinates; 
} Cell; 

struct CellEqualityByCoordinates 
{ 
    bool 
    operator()(const Cell& cell1, const Cell& cell2) const 
    { return cell1.coordinates.x == cell2.coordinates.x && cell1.coordinates.y == cell2.coordinates.y; } 
}; 

CellVectorIterator FindCellByCoordinates (CellVectorIterator first, CellVectorIterator last, const Cell &val) 
{ 
    return std::upper_bound(first, last, val, CellEqualityByCoordinates()); 
} 

不過，這並不總能找到一個值。

這是什麼問題？

Answer 1

您的比較函數不適用於二分查找。它不應該確定平等，它應該確定一個順序關係。具體來說，如果第一個參數明確地位於第二個參數之前，它應該返回true。如果參數應該被認爲是平等的，或者第二個會在第一個之前出現，它應該返回false。您的範圍還需要按照相同的標準進行排序，以便二分查找工作。

一個例子功能可能的工作：

bool operator()(const Cell& cell1, const Cell& cell2) const 
{ 
    if (cell1.coordinates.x < cell2.coordinates.x) return true; 
    if (cell2.coordinates.x < cell1.coordinates.x) return false; 
    return cell1.coordinates.y < cell2.coordinates.y; 
} 

，可兼作短路布爾評價一節課會是這樣的一個類似的例子：

bool operator()(const Cell& cell1, const Cell& cell2) const 
{ 
    return (cell1.coordinates.x < cell2.coordinates.x) || 
     (!(cell2.coordinates.x < cell1.coordinates.x) && 
      cell1.coordinates.y < cell2.coordinates.y); 
} 

都表現出屬性調用strict weak ordering 。經常需要在標準庫集合和搜索算法中進行各種排序和/或搜索。

又一實例利用std::pair，已經有可用的適當的std::less過載，做上述中，並且因此使得此相當少的複雜：

bool operator()(const Cell& cell1, const Cell& cell2) const 
{ 
    return std::make_pair(cell1.coordinates.x, cell1.coordinates.y) < 
      std::make_pair(cell2.coordinates.x, cell2.coordinates.y); 
} 

類似的算法可用於通過std::tie元組。

當然，所有這些都假定您有一個實際的有序序列，首先按照相同的比較邏輯進行排序。 （我們只能假設是真實的，因爲沒有這樣的證據）。