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

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

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

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  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; iname == nName ) { return people[i]; } } } 

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

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

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

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

Кроме того, я не понимаю, почему вы сделали map personIDMap; вместо map personIdMap .

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

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