c ++ std :: vector搜索值

Question

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

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

std::vector<myObj> myObjList;

使用唯一id的值和值创建几千个条目并将它们推送到向量myObjList.

什么是最有效的检索方式myObj匹配id.目前我的索引迭代如下:

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可用,则必须提供谓词(函数对象(=函子)或函数指针),如果提供的实例是您要查找的实例,则返回true.Functors的优势在于它们可以参数化,在您的情况下,您希望使用您要查找的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;

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