C++ std::vector 搜索值

Question

我正在尝试优化 std::vector“搜索”- 基于索引的 vector 迭代并返回与“搜索”条件匹配的元素

struct myObj {
   int id;
   char* value;
};

std::vector<myObj> myObjList;

创建几千个具有唯一 id 和值的条目，并将它们推送到 vector myObjList。

检索与 id 匹配的 myObj 的最有效方法是什么。目前我正在像这样迭代索引:

for(int i = 0; i < myObjList.size(); i++){
   if(myObjList.at(i).id == searchCriteria){
    return myObjList.at(i);
   }
}

注意:searchCriteria = int。所有元素都有唯一的 id。以上方法可以完成工作，但可能不是最有效的方法。

Answer 1

C++ 标准库有一些抽象算法，它们赋予 C++ 一种函数式风格，正如我所说的那样，它让您可以更多地关注搜索标准，而不是如何实现自己搜索。这适用于许多其他算法。

您要查找的算法是std::find_if ，通过迭代器范围的简单线性搜索。

在 C++11 中，您可以使用 lambda 来表达您的条件:

std::find_if(myObjList.begin(), myObjList.end(), [&](const myObj & o) {
    return o.id == searchCriteria;
});

当没有可用的 C++11 时，您必须提供一个谓词(函数对象 (=functor) 或函数指针)，如果提供的实例是您要查找的实例，该谓词将返回 true。仿函数的优点是它们可以参数化，在您的情况下，您希望使用您正在寻找的 ID 来参数化仿函数。

template<class TargetClass>
class HasId {
    int _id;
public:
    HasId(int id) : _id(id) {}
    bool operator()(const TargetClass & o) const {
        return o.id == _id;
    }
}

std::find_if(myObjList.begin(), myObjList.end(), HasId<myObj>(searchCriteria));

此方法返回一个迭代器，指向找到的第一个符合条件的元素。如果没有这样的元素，则返回结束迭代器(它指向 vector 的末尾，而不是最后一个元素)。所以你的函数看起来像这样:

vector<myObj>::iterator it = std::find_if(...);

if(it == myObjList.end())
    // handle error in any way
else
    return *it;