c++ std::vector 搜索值

c++ std::vector search for value

提问by narkis

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

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

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

std::vector<myObj> myObjList;

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

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

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

检索myObj匹配id. 目前我正在索引迭代，如：

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

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

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

回答by leemes

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.

C++ 标准库有一些抽象算法，它们给了 C++ 一种我称之为函数式的味道，它让你更多地关注搜索的标准，而不是你如何实现搜索本身。这适用于许多其他算法。

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

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

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

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

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

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.

当没有 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));

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;

回答by Chad

Using std::find_if.

使用std::find_if.

There's an example on the referenced page.

参考页面上有一个示例。

Here's a working example that more precisely fits your question:

这是一个更适合您的问题的工作示例：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct myObj
{
   int id;
   char* value;

   myObj(int id_) : id(id_), value(0) {}
};

struct obj_finder
{
    obj_finder(int key) : key_(key)
    {}

    bool operator()(const myObj& o) const
    {
        return key_ == o.id;
    }

    const int key_;
};

int main () {
  vector<myObj> myvector;
  vector<myObj>::iterator it;

  myvector.push_back(myObj(30));
  myvector.push_back(myObj(50));
  myvector.push_back(myObj(100));
  myvector.push_back(myObj(32));

  it = find_if (myvector.begin(), myvector.end(), obj_finder(100));
  cout << "I found " << it->id << endl;

  return 0;
}

And, if you have C++11 available, you can make this even more concise using a lambda:

而且，如果您有 C++11 可用，您可以使用 lambda 使其更加简洁：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct myObj
{
   int id;
   char* value;

   myObj(int id_) : id(id_), value(0) {}
};

int main ()
{
  vector<myObj> myvector;
  vector<myObj>::iterator it;

  myvector.push_back(myObj(30));
  myvector.push_back(myObj(50));
  myvector.push_back(myObj(100));
  myvector.push_back(myObj(32));

  int key = 100;

  it = find_if (myvector.begin(), myvector.end(), [key] (const myObj& o) -> bool {return o.id == key;});
  cout << "I found " << it->id << endl;

  return 0;
}

回答by Omnifarious

This isn't really an answer to your question. The other people who answered gave pretty good answers, so I have nothing to add to them.

这不是你问题的真正答案。其他回答的人给出了很好的答案，所以我没有什么可以补充的。

I would like to say though that your code is not very idiomatic C++. Really idiomatic C++ would, of course, use ::std::find_if. But even if you didn't have ::std::find_ifyour code is still not idiomatic. I'll provide two re-writes. One a C++11 re-write, and the second a C++03 re-write.

我想说虽然你的代码不是很惯用的 C++。当然，真正惯用的 C++ 会使用::std::find_if. 但即使你没有::std::find_if你的代码仍然不是惯用的。我将提供两次重写。一个是 C++11 重写，第二个是 C++03 重写。

First, C++11:

首先，C++11：

for (auto &i: myObjList){
   if(i.id == searchCriteria){
      return i;
   }
}

Second, C++03:

二、C++03：

for (::std::vector<myObj>::iterator i = myObjList.begin(); i != myObjList.end(); ++i){
   if(i->id == searchCriteria){
      return *i;
   }
}

The standard way of going through any sort of C++ container is to use an iterator. It's nice that vectors can be indexed by integer. But if you rely on that behavior unnecessarily you make it harder on yourself if you should change data structures later.

通过任何类型的 C++ 容器的标准方法是使用迭代器。很高兴向量可以用整数索引。但是，如果您不必要地依赖该行为，那么如果您以后应该更改数据结构，就会使您自己变得更难。

回答by Ivaylo Strandjev

If the ids are sorted you may perform binary search(there is also a function binary_searchin stl). If they are not nothing will perform better, but still you may write your code in a shorter way using stl(use find_if).

如果对 id 进行排序，您可以执行二进制搜索（binary_searchstl 中也有一个函数）。如果它们不是什么都不会表现得更好，但您仍然可以使用 stl(use find_if)以更短的方式编写代码。