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元组。

当然，所有这些都假定您有一个实际的有序序列，首先按照相同的比较逻辑进行排序。 （我们只能假设是真实的，因为没有这样的证据）。