C++ std::vector 查找值

Question

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

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

std::vector<myObj> myObjList;

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

检索与id匹配的myObj最有效的方法是什么。 目前我正在进行索引迭代，例如：

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

注意：searchCriteria = int。所有的元素都有独特的id。 以上内容可以完成任务，但可能不是最有效的方式。

- narkis

---

你的元素是否以任何方式排序？ - leemes

列表是在读取数据时创建的，没有进行任何排序。 - narkis

在尝试真正优化涉及到std::vector的任何代码时，首要考虑的是使用operator[]而不是at，因为后者每次都会进行完全不必要的范围检查。 - Christian Rau

谢谢Christian - 我今天稍后会测试"operator[]"，以便可能采取最低的果实 :) - narkis

可能是重复的问题：如何在std :: vector中查找项？ - petert

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，您必须提供一个谓词（函数对象（=函数器）或函数指针），如果所提供的实例是您正在查找的实例，则返回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<myObj>::iterator it = std::find_if(...);

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

- leemes

---

OP可能还没有lambda。 - Omnifarious

谢谢你们两个，我添加了一个非C++11的解决方案。 - leemes

注意：lambda示例中的返回语句缺失。 - fgiraldeau

Answer 2

使用std::find_if函数。

参考页面上有一个示例。

这里是一个更精确符合您问题的工作示例：

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

如果您有可用的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;
}

- Chad

---

为了清晰起见，您可能希望在示例中使用OP的定义。但没关系，我早就得到了我的赞成票。也许可以通过值来捕获int，但是好吧。 - Christian Rau

Answer 3

这并不是你问题的答案。其他回答者已经给出了相当好的答案，所以我没有什么可以补充的。

但是我想说的是，你的代码不是非常符合C++的习惯用法。真正符合C++的习惯用法当然会使用`::std::find_if`。但即使你没有`::std::find_if`，你的代码仍然不符合习惯用法。我会提供两个重写版本。一个是C++11重写，另一个是C++03重写。

首先是C++11：

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

第二点，C++03：

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

遍历C++容器的标准方法是使用迭代器。虽然向量可以通过整数索引，但如果您不必要地依赖该行为，将来更改数据结构会使您的工作更加困难。

- Omnifarious

---

传入的数据结构是由ISO标准所规定的，因此我们可以相信它暂时不会改变。感谢大家的所有意见！ - narkis

@narkis：这也比你之前做的更快，而且符合惯用语的意思是其他了解C++的人会更快地理解循环。 :-) - Omnifarious

@Omnifarious：你写的基于范围的for循环好像把i当作了迭代器，但实际上它不是。我认为你的意思应该是要么写成for (auto i : myObjList) { if(i.id == searchCriteria) return i; }，要么写成for (auto &i : myObjList) { same thing; }。 - Steve Jessop

Answer 4

如果ID已经排序，你可以使用二分查找（STL中也有一个名为binary_search的函数）。如果ID没有排序，则没有更好的方法，但你仍然可以使用STL来更简洁地编写代码（使用find_if函数）。

- Ivaylo Strandjev

---

谢谢 - 我会看看是否有合理的方法在向量最初填充“myObj”时按ID排序 - 虽然毫无疑问这也会产生开销。感谢您的建议！ - narkis