时间戳

首页 > 解决方案 > 在查找表中存储命名项目

c++ - 在查找表中存储命名项目

问题描述

考虑下面的类

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 存储在 a 中是否更好std::map<RegistrationId, Person>，这样可以更改记录，尽管这需要将 id 存储两次。

  3. 或者也许我应该使用地图，并从Person班级中删除 id。Person但是，如果我只能访问, 而不是，则我无法获得 id std::pair<RegistrationNumber const, Person>，因此这可能需要传递这些对。

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

标签： c++dictionaryconstantsdata-consistency

解决方案

大多数情况下，最好将所有内容都放入（可能）排序的std::vector<Person>. 然后您可以对向量进行二进制搜索以查找元素。封装矢量对象的小型便利类会很有用。

您具有缓存局部性的优势（尤其是在迭代所有条目期间）。并且至少set与 a或map(O(log n))相同的检索性能。然而，如果没有优化，插入会稍微差一些（O(n) 与 O(log n)）。如果您进行批量插入，您可以只插入所有项目，然后对向量进行排序，从而获得设置/映射性能。

附录：如果 id 是唯一的并且是递增的（没有或很少有间隙），那么向量也是显而易见的选择，因为您可以只使用 id 作为索引。如果不能保证 id 是连续的，请考虑类似vector<optional<Person>>.

推荐阅读