c++ - 为二进制搜索排序对象 vector

Question

我有以下类(class):

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

};

我想要一个这样的对象的 vector ，按 neighborNodeId 排序。然后我想搜索一个特定的 neighborNodeId 并通过二进制搜索返回对 vector 内找到的对象的引用。以前我为此使用了一张 map ，所以它是这样的:

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

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

代替

map<int, EdgeExtended> neighbours;

我想拥有

vector<EdgeExtended> neighbours;

并保留尽可能多的旧代码相同。

如果 vector 比 map 快，我想进行基准测试，因为我正在构建数千个 vector (或 map )并且每个 vector ( map )相对较小(约 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;
    }
};