binary_search return 始终为真 C++

Question

我被这个问题困住了，我正在处理位置向量。在一种情况下，该向量相对于对偶的第一个分量 "position" 排序，在另一种情况下相对于另一个分量排序，在这两种情况下，对偶的另一个元素保持不变。例如我有：

 1 1, 1 3, 1 7, 1 11  //second case

现在我想使用 binary_search 算法来查找其中一个向量中是否存在特定位置，但即使不存在，答案也是肯定的！

这是我的代码

using namespace std;

class position{
     int r;
     int c;
public:
     position(int r=0, int c=0): r(r), c(c){
     };

position &operator=(position p);

int getr(){
    return r;
};
int getc(){
    return c;
};
friend bool operator>(const position &p, const position &q);
friend bool operator<(const position &p, const position &q);
friend bool operator==(const position &p, const position &q);

};

bool operator>(const position &p, const position &q);{
    return((p.r>q.r)&&(p.c>q.c));
};

bool operator<(const position &p, const position &q);{
    return q>p;
};

bool operator==(const position &p, const position &q);{
    return((p.r==q.r)&&(p.c==q.c));
};

 int main(){
 vector<position> R;

 for(int i=0;i<10;i++)
    R.push_back(position(1,2*i));

 for(int i=0;i<R.size();i++)
    cout<<R[i];
 cout<<endl;
 posizione a(1,7);

 cout<<binary_search(R.begin(),R.end(),a);

 }

Answer 1

您的比较器存在缺陷，因为它没有创建严格的顺序。

尝试：

bool  operator > (const position&p, const operator&q){
    return((p.x>q.x)|| (p.x==q.x && p.y>q.y));
}

问题详细解释：

使用您自己的实现：

偶数 {1,4} 不会大于 {1,3} 因为 1 不大于 1，所以逻辑 and 将 return 为假。
但是 {1,3} 不会大于 {1, 4}。

如果两对none大于另一对，原则上应该是相等的。事实并非如此，您的比较器不适合二进制搜索。

Answer 2

您的 operator > 不保证严格排序。在处理 comapring 多个成员变量时，我发现最好使用 std::tie。以下应该会给你正确的结果

bool  operator > (const position&p, const operator&q){
    return std::tie(p.x, p.y) > std::tie(q.x, q.y);
}

Answer 3

STL 要求 operator<，而不是 operator>。您应该遵循它的示例，这样您在使用其他算法时就不会感到意外。
您的比较不正确，并且会 return 误报。尽管其他答案正确地解释了如何解决此问题，但无论如何您实际上应该使用 std::pair<int, int> 。它为您实现了该功能以及更多功能。

using Position = std::pair<int, int>;

std::vector<Position> v{make_positions()};
Position a{1, 5};
std::sort(v.begin(), v.end());
bool exists = std::binary_search(v.begin(), v.end(), a);

binary_search return 始终为真 C++

binary_search return always true c++

c++

syntax-error

binary-search