我正在尝试进行 binary_search,包括一个整数对 vector 和一个整数,如下所示:
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<pair<size_t,size_t> > int_pairs;
bool operator<(const size_t& l, const pair<size_t,size_t>& r)
{return r.first < l;} // useful for binary search
int main(){
int_pairs pairs_vec;
pairs_vec.push_back(pair <size_t,size_t>(1,2));
pairs_vec.push_back(pair <size_t,size_t>(2,2));
size_t i(2);
binary_search(pairs_vec.begin(),pairs_vec.end(),i);
}
编译器告诉我 operator<
未定义:
erreur: no match for ‘operator<’ (operand types are ‘const long unsigned int’ and ‘std::pair<long unsigned int, long unsigned int>’)
我的做法是否正确?我尝试以多种不同方式更改运算符的定义,但似乎没有任何效果。
最佳答案
这不起作用的原因是 operator<
未从您调用的点查找 binary_search
,而是稍后从它的 body 内部 - 那是在命名空间内 std
.
自 std::pair
已经定义了 relational operators在命名空间 std
,它们将您的重载隐藏在全局范围内,并且永远不会通过名称查找找到。
解决方案是不使用 operator<
根本。创建你自己的不与任何东西冲突的比较器类,重载它的 operator()
,并使用 binary_search
的另一个重载让您指定自定义比较器。像这样:
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<size_t, size_t> my_pair;
typedef vector<pair<size_t,size_t> > int_pairs;
struct Comp {
// important: we need two overloads, because the comparison
// needs to be done both ways to check for equality
bool operator()(my_pair p, size_t s) const
{ return p.first < s; }
bool operator()(size_t s, my_pair p) const
{ return s < p.first; }
};
int main(){
int_pairs pairs_vec;
pairs_vec.push_back(pair <size_t,size_t>(1,2));
pairs_vec.push_back(pair <size_t,size_t>(2,2));
size_t i(2);
binary_search(pairs_vec.begin(),pairs_vec.end(),i, Comp());
}
旁注:
您对 operator<
的尝试错了,因为你在函数内切换了操作数的顺序。严格弱排序比较器的契约规定,如果第一个操作数出现在第二个操作数之前,它必须返回真(这适用于整个标准库中的所有比较函数)。
bool operator<(const size_t& l, const pair<size_t,size_t>& r)
{
return r.first < l; // Wrong!
}
正如上面评论中所说,如果用于比较的操作数是不同类型的,则需要两个重载。检查与 <
是否相等,你需要两个测试:
(!(a < b) && (!b < a))
关于c++ - binary_search 与 std::pair 使用自定义运算符,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18406479/