c ++ std :: vector搜索值 [英] c++ std::vector search for value

问题描述

我试图优化 std :: vector search - 基于索引的迭代通过向量和返回和元素匹配搜索条件

I am attempting to optimize a std::vector "search " - index based iterating through a vector and returning and element that matches a "search" criteria

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

std::vector<myObj> myObjList;

创建几千个具有唯一 id 并将它们推送到向量 myObjList 。

create a few thousand entries with unique id's and values and push them to the vector myObjList.

什么是最有效的方法来检索 myObj 匹配 id 。
目前我的索引迭代如下：

What is the most efficient way to retrieve myObj that matches the id. Currently I am index iterating like:

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

注意： searchCriteria = int 。所有元素都有唯一的 id 的。
上面的工作，但可能不是最有效的方式。

Note: searchCriteria = int. All the elements have unique id's. The above does the job, but probably not the most efficient way.

推荐答案

C ++标准库有一些抽象算法，它给予C ++一种我们称之为的功能性风格，这使得您更注重搜索的标准，而不是如何实现搜索本身。这适用于许多其他算法。

The C++ standard library has some abstract algorithms, which give C++ a kind of functional flavour, as I call it, which lets you concentrate more on the criteria of your search than on how you implement the search itself. This applies to a lot of other algorithms.

您正在寻找的算法是 std :: find_if ，通过迭代器范围进行简单的线性搜索。

The algorithm you are looking for is std::find_if, a simple linear search through an iterator range.

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

In C++11, you can use a lambda to express your criteria:

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

当没有C ++ 11可用时，必须提供一个谓词（function object ）或函数指针），如果提供的实例是你正在寻找的那个返回true。函子的优点是可以参数化 ，在你的情况下，你想用你正在寻找的ID参数化函数。

When not having C++11 available, you have to provide a predicate (function object (=functor) or function pointer) which returns true if the provided instance is the one you are looking for. Functors have the advantage that they can be parameterized, in your case you want to parameterize the functor with the ID you are looking for.

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

此方法返回一个迭代器，指向找到的符合您条件的第一个元素。如果没有这样的元素，则返回结束迭代器（其指向超过向量的末尾，而不是指向最后一个元素）。所以你的函数可能看起来像这样：

This method returns an iterator pointing to the first element found which matches your criteria. If there is no such element, the end iterator is returned (which points past the end of the vector, not to the last element). So your function could look like this:

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

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

这篇关于c ++ std :: vector搜索值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！