在std::lower_bound中使用比较运算符

Question

我的编译器拒绝编译这个简单的代码:

struct mystruct{
    int x;
    bool operator<(const mystruct& y) const{ return x < y.x; }
};

std::map<mystruct, int> test;
auto it = std::lower_bound(test.begin(), test.end(), mystruct{2});

我得到错误

error C2893: Failed to specialize function template 'unknown-type std::less<void>::operator ()(_Ty1 &&,_Ty2 &&) const'

看这个链接，似乎你只需要定义一个常量比较操作符，这正是我正在做的。我是不是漏掉了什么?

Answer 1

问题是你的地图的值类型是std::pair<const mystruct, int>，所以std::lower_bound试图比较mystruct和std::pair<const mystruct, int>。没有为它定义运算符

你不应该在std::map上使用std::lower_bound。它将在O(n)内工作，因为map没有随机访问迭代器。std::map有自己的lower_bound成员函数，它将利用树结构在O(log n)内给出结果。

auto it = test.lower_bound(mystruct{2});