CODEWITHSUNDEEP
c++binary-search
Sergej Fomin
Sergej Fomin

Reputation: 2002

C++ binary search for a class

I have a class and I want to implement binary_search (from library) to it:

#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);
}

Is that possible? Should I overload '==' and '<' operators (tried, didn't succeed) or something else?

Thank you in advance!

Upvotes: 1

Views: 2310

Answers (2)

darune
darune

Reputation: 10982

Yes. Although you just need to implement operator<. Also the argument to binary_search is mismatched and the container must be pre-sorted.

Link to working example:

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

Operator less:

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

Pre-sort container and 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;

Upvotes: 2

sp2danny
sp2danny

Reputation: 7644

Since you send an int as the 3rd argument to binary_search, just an operator< will not be enough, because you need to support both int<T_value and T_value<int

The suggestion is to create a comparator class with the members:

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

and send an instance as a fourth parameter.

Furthermore, the vector should be sorted before binary_search is invoked. You could do this with std::sort, but now you need to support a 3rd type of comparison, a 3rd member of the comparator class could do that, like:

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

The end result might look something like this

Upvotes: 3

Related Questions