11

我正在尝试优化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的。以上完成了这项工作，但可能不是最有效的方式。

4

4 回答 4

19

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<myObj>::iterator it = std::find_if(...);

if(it == myObjList.end())
    // handle error in any way
else
    return *it;
于 2013-01-02T15:20:55.150 回答
11

使用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;
}
于 2013-01-02T15:17:04.057 回答
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++ 容器的标准方法是使用迭代器。向量可以按整数索引，这很好。但是，如果您不必要地依赖这种行为，那么以后如果您应该更改数据结构，您就会变得更加困难。

于 2013-01-02T15:34:14.453 回答
2

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

于 2013-01-02T15:17:37.623 回答