为二进制搜索排序对象矢量 [英] Sort vector of objects for binary search

问题描述

我有以下类：

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

};

我想有一个这样的对象的向量，通过neighborNodeId排序。然后我想搜索一个特定的neighborNodeId，并通过二叉搜索返回向量内的找到的对象的引用。以前我使用了一个地图，所以它是这样的：

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

而不是

map<int, EdgeExtended> neighbours;

我想要

vector<EdgeExtended> neighbours;

并保留与旧代码相同的代码。

and retain as much as the old code the same.

我想要基准如果向量比地图快，因为我建立成千上万的向量（或地图）和每个向量（地图）是相对较小（约10项）。我不知道如何a）使对象可以通过neighborNodeId和b）如何使用二进制搜索搜索类的一个特定成员（neighborNodeId）。对不起，noob问题。

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.

推荐答案

您需要一个自定义比较函数，它需要两个 EdgeExtended 对象，并比较您感兴趣的字段，并且可以传递给 sort 和 binary_search 作为第三个或第四个参数。

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.

可以方便地使用lambda函数：

It can be conveniently done with a lambda function:

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

如果你卡住前C ++ 11，写一个重载的类代替：

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

这篇关于为二进制搜索排序对象矢量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！