从指针集合中快速检索特定对象 [英] Fast Retrieval of a Specific Object from a Collection of Pointers

问题描述

我正在尝试提出一种以尽可能高效的方式从容器(地图，矢量，)访问/检索对象的技术.

I am trying to come up with techniques of accessing/retrieving an object from a container (map, vector, ) in the most efficient manor possible.

所以，如果我有对象:

class Person
{
   public:
       string name;
       unsigned int ID; // unique ID
       double deposit;
 };

// And then I have a vector of pointers to person objects
std::vector <Person*> people;

Person* getPerson( string nName );
Person* getPerson( unsigned int nID ); // what would be a good method to quickly identify/retrieve the correct Person object from my vector?

我的想法:

这是无效的迭代解决方案:

This is the iterative solution that is not efficient:

Person* getPerson( string nName )
{
   for (int i=0; i<people.size(); i++)
   {
      if (people[i]->name == nName ) { return people[i]; }
   }
}

另一种方式:拥有2张地图

Another way: have 2 maps

map <string, Person*> personNameMap;  

Person* getPerson( string nName )
{
   return personNameMap[nName]; 
}

map <string, Person*> personIDMap;
Person* getPerson( unsigned int nID )
{
   char id[2];
   atoi( nID, id, 10 );  // or is it itoa?
   return personNameMap[id]; 
}

关于如何存储&的其他任何想法从集合中快速检索我的对象高效的庄园?

Any other ideas how I could store & retrieve my objects from a collection in a fast & efficient manor?

推荐答案

std::map是一棵平衡树，是O(log n)个搜索步骤. 提高报价 boost::unordered_map这是一个哈希映射.它的渐近性更差(O(n^2))，但是平均而言，它的性能更好.取决于容器的充满度，它是1-3个恒定的步骤.容器装满后(这意味着键的值用尽了)，将发生越来越多的碰撞，并且性能将迅速下降.在大多数实现中，这种情况发生在大约80％的充满度下.在大多数情况下，这不是问题，但是请注意此限制.

std::map is a balanced tree that is O(log n) steps for searching. Boost offers boost::unordered_map which is a hash-map. It is asymptotically worse (O(n^2)), however, on average it performs better. Depending on the fullness of the container, it is 1-3 constant steps. Once the container gets filled (which means that the values of the keys get exhausted) there will be more and more collisions and the performance will degrade quickly. In most implementations this happens at around 80% fullness. This is not a problem in most cases, but be aware of this limitation.

这篇关于从指针集合中快速检索特定对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！