Intereting Posts
Почему Visual C ++ 6 жалуется на частный деструктор Приложение tcp для нескольких клиентов / серверов с использованием qt как отменить операцию удаления shared_ptr? Функция имени шаблона classа шаблона Арабский: «источник» Unicode для окончательного отображения Unicode Преобразование простого приложения MFC CView / CDocument / CSingleDocTemplate в элемент управления ActiveX Зачем продолжать использовать геттеры с неизменяемыми объектами? Почему анонимные объединения не содержат членов с нетривиальными конструкторами / деструкторами? Как определить пользовательское расстояние в Boost Dijkstra? C ++ – Вложенные include в себя – Избегать “включить вложенную слишком глубокую ошибку” Зачем использовать QVector (Qt) вместо std :: vector Преобразование строки в код C ++ Мерцание windows при изменении размера с левой стороны Самый простой способ получить PTY в Linux C ++ C ++: Почему у моего конструктора DerivedClass нет доступа к защищенному полю BaseClass?

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

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