Sort vector of objects for binary search

Question

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.

Answer 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;
    }
};