为二进制搜索排序对象矢量

Question

我有以下课程:

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

};

我想要一个这样的对象的向量,通过neighborNodeId对它进行排序.然后我想搜索特定的neighborNodeId并通过二进制搜索返回对向量中找到的对象的引用.以前我用过地图,所以就是这样的:

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

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

代替

map<int, EdgeExtended> neighbours;

我希望有

vector<EdgeExtended> neighbours;

并保留尽可能多的旧代码.

我想测量矢量是否比地图快,因为我正在构建数千个矢量(或地图),每个矢量(地图)相对较小(~10个项目).我不知道如何a)通过neighborNodeId对对象进行排序,以及b)如何使用二进制搜索来搜索类的特定成员(neighborNodeId).抱歉,这个菜鸟问题.我指望你的帮助.

Answer 1

您需要一个自定义比较器函数,它接受两个EdgeExtended对象并比较您感兴趣的字段,并且可以分别传递给它们sort和binary_search第三个或第四个参数.

它可以通过lambda函数方便地完成:

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

如果您坚持使用C++ 11之前的版本,请编写一个带重载的类operator():

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