Store named items in lookup table

Question

Consider the following class

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. Now I want to be able to find a person by its id, and update its name. For that, I could use std::set<Person, PersonIdCompare>, but then I cannot modify the record without a const_cast.

2. Is it better then to store Persons in a std::map<RegistrationId, Person>, so the record can be changed, though this requires the id to be stored twice.

3. Or maybe I should use a map, and remove the id from the Person class. But then I cannot get the id if I only have access to the Person, and not std::pair<RegistrationNumber const, Person>, so this may require to pass these pairs around.

What option is most efficient or less error prone. Think of the scenario where someone adds a setter for the person id, which would break option 1 and 2, or storing the id twice as for option number 2.

Answer 1

Most of the time it's best to just throw everything in a (potentially) sorted std::vector<Person>. Then you can do binary search on the vector to look up an element. A small convenience class that encapsulates the vector object would be useful.

You have the advantage of cache locality (esp. during iteration over all entries). And at least the same retrieval performance than a set or map (O(log n)). Without optimisation however, insertion will be slightly worse (O(n) versus O(log n)). If you do bulk insertion, you can just insert all items, then sort the vector, which gets you set/map performance.

Addendum: If the ids are unique and ascending (with no or very little gaps) a vector is also the obvious choice, as you can just use the id as index. If the ids are not guaranteed to be consecutive consider something like vector<optional<Person>>.