时间戳

首页 > 解决方案 > C++二分查找类

c++ - C++二分查找类

问题描述

我有一个类，我想为它实现 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);
}

那可能吗？我应该重载 '==' 和 '<' 运算符（尝试过，没有成功）还是其他什么？

先感谢您！

标签： c++binary-search

解决方案

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

建议是创建一个包含成员的比较器类：

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

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

此外，向量应该在binary_search调用之前进行排序。您可以使用 来执行此操作std::sort，但现在您需要支持第三种比较类型，比较器类的第 3 个成员可以执行此操作，例如：

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

最终结果可能看起来像这样

推荐阅读