Хранить именованные элементы в таблице поиска

Question

Рассмотрим следующий класс

class Person
{
     public:
          explicit Person(RegistrationNumber id, std::string const& name);

          RegistrationId id() const;

          std::string const& name() const;
          Person& name(std::string const&);

          // ...
     private:
          RegistrationNumber m_id;
          std::string m_name;
          // ...
};

1. Теперь я хочу найти человека по его идентификатору и обновить его имя. Для этого я мог бы использовать std::set<Person, PersonIdCompare>, но тогда я не могу изменить запись без const_cast.

2. Лучше ли хранить людей в std::map<RegistrationId, Person>, поэтому запись может быть изменена, хотя для этого требуется, чтобы идентификатор хранился дважды.

3. Или, возможно, мне следует использовать карту и удалить идентификатор из класса Person. Но тогда я не могу получить идентификатор, если у меня есть доступ только к Person, а не к std::pair<RegistrationNumber const, Person>, поэтому может потребоваться передать эти пары.

Какой вариант наиболее эффективный или менее подверженный ошибкам. Подумайте о сценарии, в котором кто-то добавляет установщик для идентификатора человека, который нарушает опцию 1 и 2, или сохраняет идентификатор дважды, как для варианта № 2.

Answer 1

В большинстве случаев лучше просто выбросить все в (потенциально) отсортированную std::vector<Person>. Затем вы можете выполнить бинарный поиск по вектору, чтобы найти элемент. Небольшой вспомогательный класс, который инкапсулирует векторный объект, был бы полезен.

У вас есть преимущество локальности кэша (особенно во время итерации по всем записям). И по крайней мере та же производительность поиска, что и set или map (O (log n)). Однако без оптимизации вставка будет несколько хуже (O (n) по сравнению с O (log n)). Если вы выполняете массовую вставку, вы можете просто вставить все элементы, а затем отсортировать вектор, который дает вам заданную / отображаемую производительность.

Приложение : если идентификаторы уникальны и возрастают (без или очень маленькие пробелы) вектор также является очевидным выбором, так как вы можете просто использовать идентификатор в качестве индекса. Если идентификаторы не гарантированы быть последовательными, рассмотрите что-то вроде vector<optional<Person>>.