1

std::vector<MyClass*>(MyClass ポインターのベクトル) があり、ベクトル内の特定の項目を見つける必要があります。クラスには、getID()クラスの一意の識別子を返す関数があります。

特定の ID を持つクラスを見つけたい場合は、次のようにベクターを反復して ID を持つクラスを探します。

for(std::vector<Chunk*>::iterator it = chunksRenderList.begin(); it != chunksRenderList.end(); ++it)
{
    if((*it)->getID() == id)
        return *it;
}

このコードを 1 秒間に何度も呼び出しているため、これはかなり遅いです。std::unordered_map私はずっと遅いa を使ってみましたが、 astd::mapもまた遅かったです。なぜ遅くなったのかはわかりませんが、私の使い方のせいかもしれません。

反復せずに特定のアイテムにアクセスするために使用できるコンテナ/アルゴリズムはありますか (反復よりも高速です)?

4

2 に答える 2

3

コンテナーが getID() の値に従ってソートされている場合は、バイナリ検索を使用してみてください。

class A
{
  size_t m_id;
public:
  A (size_t id) : m_id(id) {}
  size_t getID (void) const { return m_id; }
};

template<class T1, class T2>
struct less_id
{
  bool operator () (T1 const &lhs, T2 const & cmp)
  {
    return (lhs->getID() < cmp);
  }
};

int main (void)
{
  std::vector<A*> v;
  v.push_back(new A(2));
  v.push_back(new A(3));
  v.push_back(new A(4));
  v.push_back(new A(5));

  less_id<A*, size_t> cmp;

  size_t find_value = 4;
  std::vector<A*>::iterator found = std::lower_bound(v.begin(), v.end(), find_value, cmp);
  if(found == v.end() || !((*found)->getID() == find_value))
  {
    // not found
  }
  else
  {
    // found
    std::cout << "Found element: " << (found-v.begin()) << std::endl;
  }

  for (size_t i=0; i<v.size(); ++i) delete v[i];
  v.clear();
}

ショー

見つかった要素: 2

A==Chunkとv==の場所chunksRenderList。

于 2013-07-18T03:37:42.010 に答える