Intereting Posts
Файл записи вызывает сбои, с нарушением доступа Является ли шаблон функции друга определенным в classе доступным для поиска? clang ++ и g ++ не согласны Как использовать ETW из клиента Windows C ++ Почему неявно и явно удаленные конструкторы перемещения обрабатываются по-разному? При установке на OSX Sierra через gcc-6 сохраните «FATAL: / opt / local / bin /../ libexec / as / x86_64 / as: я не понимаю ошибку« m »!» Что делает голосовой атрибут VC / C ++? Неявное преобразование C ++ (Signed + Unsigned) SWIG typemap uint8_t * от C / C ++ до java.nio.ByteBuffer Как вы указываете, что следует ожидать исключения с помощью Boost.Test? Использование полиморфного интеллектуального указателя Что означает «только экспозиция»? Зачем использовать его? Преобразование временной строки в эпоху в windows Как рассчитать взаимосвязи с использованием boostlib для списка смежности? Экспоненциальный оператор в C ++ Как получить ширину и высоту изображения в OpenCV?

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

Я пытаюсь придумать методы доступа / получения объекта из контейнера (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 ++, если индекс не является целым. Надеюсь, что это хорошо