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では、ラムダを使用して基準を表すことができます。

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;
于 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 を利用できる場合は、ラムダを使用してこれをさらに簡潔にすることができます。

#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、まだ慣用的ではありません。2回書き直します。1 つは C++11 の書き直し、もう 1 つは 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 がソートされている場合は、バイナリ検索を実行できます ( binary_searchstl にも関数があります)。それらが何もない場合はパフォーマンスが向上しますが、それでも stl(use find_if) を使用してより短い方法でコードを記述することができます。

于 2013-01-02T15:17:37.623 に答える