C++ 二进制搜索 class

Question

我有一个 class，我想对其实施 binary_search（来自库）：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class T_value{
public:

    T_value(const int _timestamp, const string _value) :
        timestamp(_timestamp),
        value(_value)
    {}
    int get_time() {return timestamp;}


private:
    int timestamp;
    string value;
};

int main()
{

    T_value one(1, "one"),
    two(3, "two"),
    three(43, "three"),
    four(-1, "four");
    vector<T_value> v{one,two,three, four};

    cout << binary_search(begin(v), end(v), 3);
}

这可能吗？我应该重载“==”和“<”运算符（尝试过，但没有成功）还是其他？

提前致谢！

Answer 1

由于您将 int 作为第三个参数发送给 binary_search，仅 operator< 是不够的，因为您需要同时支持 int<T_value 和 T_value<int

建议创建比较器 class 成员：

bool operator()(const T_value& lhs, int rhs) const
bool operator()(int lhs, const T_value& rhs) const

并发送一个实例作为第四个参数。

此外，向量应该在 binary_search 之前排序调用。你可以用 std::sort 来做到这一点，但现在你需要支持第三种比较，比较器的第三个成员 class 可以做到这一点，例如：

bool operator()(const T_value& lhs, const T_value& rhs) const

最终结果可能类似于 this

Answer 2

是的。虽然你只需要实现operator<。 binary_search 的参数也不匹配，容器必须是 pre-sorted.

Link 工作示例：

http://coliru.stacked-crooked.com/a/0343dd205abac6f2

运算符少：

bool operator<(const T_value& other) const {
    return timestamp < other.timestamp;//you may wan't another sort criteria
}

Pre-sort 容器和 binary_search:

std::sort(v.begin(), v.end());
cout << (binary_search(begin(v), end(v), T_value(3, "not used") ) ? "found" : "not found") << std::endl;

C++ 二进制搜索 class

C++ binary search for a class

c++

binary-search