将命名项存储在查阅表中

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. 现在我希望能够通过id找到一个人，并更新他的名字。为此，我可以使用std::set<Person, PersonIdCompare>，但如果没有const_cast，我就无法修改记录。

2. 将Persons存储在std::map<RegistrationId, Person>中，这样就可以更改记录，尽管这需要存储两次id。

3. 或者，我应该使用映射，并从Person类中删除id。但是，如果我只能访问Person，而不能访问std::pair<RegistrationNumber const, Person>，那么我就无法获得id，所以这可能需要传递这些对。

什么选项最有效或不易出错。想象一下这样的场景，有人为个人id添加了一个setter，这将破坏选项1和2，或者将id存储为选项2的两倍。

Answer 1

大多数时候，最好将所有内容都放入(可能(排序的std::vector<Person>中。然后你可以对向量进行二进制搜索来查找元素。一个封装矢量对象的小型便利类会很有用。

您具有缓存局部性的优势(尤其是在迭代过程中超过所有条目(。并且至少具有与set或map(O(logn((相同的检索性能。然而，如果不进行优化，插入将稍差(O(n(与O(logn((。如果进行批量插入，则可以插入所有项目，然后对向量进行排序，从而设置/映射性能。

附录：如果id是唯一的并且是升序的(没有间隙或间隙很小(，那么向量也是显而易见的选择，因为您可以将id用作索引。如果不能保证id是连续的，可以考虑vector<optional<Person>>之类的东西。