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

本文介绍了为二进制搜索排序对象矢量的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有以下类：

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