Sort vector of objects for binary search

问题:

I have the following class:

struct EdgeExtended {
    int neighborNodeId;
    int weight;
    int arrayPointer;
    bool isCrossEdge;

};

I want to have a vector of such objects, sort it by neighborNodeId. Then I want to search for a particular neighborNodeId and return a reference to the found object inside the vector by binary search. Previously I used a map for that, so it was something like that:

map<int, EdgeExtended> neighbours;
.....

auto it = neighbours.find(dnodeId);
if (it != neighbours.end()) {
    edgeMap = it->second; 
}

Instead of

map<int, EdgeExtended> neighbours;

I want to have

vector<EdgeExtended> neighbours;

and retain as much as the old code the same.

I want to benchmark if the vector is faster than the map, since I am building thousands of vectors(or maps) and each vector (map) is relatively small (~10 items). I do not know how to a) make objects sortable by neighborNodeId and b) how to use binary search that searches for a particular member of the class (neighborNodeId). Sorry for the noob question. I am counting on your help.

回答1:

You need a custom comparator function that takes two EdgeExtended objects and compares the fields you're interested in and that you can pass to both sort and binary_search as a third or fourth argument, respectively.

It can be conveniently done with a lambda function:

auto Comp = [](const EdgeExtended& e1, const EdgeExtended& e2)
{
    return e1.neighborNodeId < e2.neighborNodeId;
};

If you stuck pre-C++11, write a class with overloaded operator() instead:

struct Comp {
    bool operator()(const EdgeExtended& e1, const EdgeExtended& e2) const
    {
        return e1.neighborNodeId < e2.neighborNodeId;
    }
};

回答2:

Extending on jrok's answer, if you encounter similar problems more often, a reusable templated comparator which uses any member of a class comes in very handy.

template<class T, class U>
class CompareByMember {
    U (T::*mem);          // ugly syntax for member pointer of type U in class T
public:
    CompareByMember(U (T::*mem)) : mem(mem) {}
    bool operator()(const T &a, const T &b) {
        return (a.*mem) < (b.*mem);     // ugly syntax for member pointer access
    }
};

As you can see, the syntax for pointers to class members is pretty strange, but once wrapped in this functor you don't have to care about it. One remaining "issue" is that you'd have to write the template parameters <T, U> each time you want to use this functor. But using type deduction this problem is solved, introducing a little helper function (note that its name is lower case):

template<class T, class U>
CompareByMember<T,U> compareByMember(U (T::*mem)) {
    return CompareByMember<T,U>(mem);
}

This results in client code like this:

std::vector<EdgeExtended> v = ...;
std::sort(v.begin(), v.end(), compareByMember(&EdgeExtended::neighborNodeId));

Simple demonstration

For member functions, a similar templated functor can be written, using the only slightly different member function pointer syntax. You can also overload the call operator in the functor to accept raw pointers of T as well as any smart pointer wrapping around T* (using templates again).