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 neighbours; ..... auto it = neighbours.find(dnodeId); if (it != neighbours.end()) { edgeMap = it->second; } ``` Instead of ``` map neighbours; ``` I want to have ``` vector 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…

Accepted Answer

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

Sort vector of objects for binary search

Solution

Problem