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'

查看 this link，您似乎只需要定义一个常量比较运算符，这正是我正在做的。我在这里遗漏了什么吗？

Answer 1

问题在于您的地图的值类型是 std::pair<const mystruct, int>，因此 std::lower_bound 正在尝试将 mystruct 与 std::pair<const mystruct, int> 进行比较。并且没有为此定义运算符。

无论如何，您都不应该在 std::map 上使用 std::lower_bound。它将在 O(n) 中工作，因为映射没有随机访问迭代器。 std::map 有自己的 lower_bound 成员函数，它将利用树结构为您提供 O(log n) 的结果。

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

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

Comparison operator to be used in std::lower_bound

c++

operator-overloading

stl-algorithm