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

这相当慢，因为我每秒调用此代码很多次。我尝试过使用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 回答
2

如果您这样做足以证明它的合理性，那么显而易见的事情就是对向量进行排序，然后使用二进制搜索来查找您的项目。

如果您的 ID 合理地可预测地分布在它们所覆盖的范围内，您可以使用插值搜索将复杂性从 O(N) 降低到大致 O(log log N) - 尽管它有足够高的常数，通常只是一个胜利有相当大的收藏。

于 2013-07-18T03:05:26.643 回答