Быстрое извлечение определенного объекта из коллекции указателей

Question

Я пытаюсь придумать способы доступа / извлечения объекта из контейнера (карты, вектора) в наиболее эффективном из возможных поместьев.

Итак, если у меня есть объект:

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?

Мои идеи:

Это итеративное решение, которое неэффективно:

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

Другой способ: иметь 2 карты

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

Есть еще идеи, как я могу хранить и извлекать свои объекты из коллекции в быстром и эффективном поместье?

Answer 1

std::map сохраняет его элемент в сбалансированной древовидной структуре и обеспечивает довольно хорошую скорость поиска.Но вставка в std::map происходит медленнее, чем в последовательных контейнерах по тем же причинам.Так что map - ваш выбор, если у вас есть много недоумений и довольно мало вставок.

Кроме того, я не понимаю точно, почему вы сделали map <string, Person*> personIDMap; вместо map <unsigned int, Person*> personIdMap.

Answer 2

std::map - это сбалансированное дерево, которое O(log n) шагов для поиска. Boost предлагает boost::unordered_map, что является хэш-картой.Он асимптотически хуже (O(n^2)), однако в среднем он работает лучше.В зависимости от наполненности контейнера, это 1-3 постоянных шага.Как только контейнер заполнится (что означает, что значения ключей исчерпаны) будет происходить все больше и больше коллизий, и производительность будет быстро снижаться.В большинстве реализаций это происходит при заполненности около 80%.В большинстве случаев это не проблема, но помните об этом ограничении.

Answer 3

Map - самый быстрый контейнер для поиска в C ++, если индекс не является целым числом. Надеюсь, это хорошо