我有一个数据,我需要对其进行搜索和排序。数据只是一堆结构对象,看起来像这样:

struct ContactInfo {
    std::string name;
    std::string description;
    std::string phoneNumber;
    std::string email;

    ContactInfo(std::string name, std::string phone, std::string email, std::string desc);
    ContactInfo();
};

如果我将其保存在以“名称”为关键字的 map 中,则通过“描述”,“phoneNumber”或“电子邮件”进行搜索时,我将必须执行线性搜索。

我的问题是:我是否有更好的方法来保持数据的搜索速度更快?

最佳答案

关联STL容器(mapunordered_map)是围绕单个索引的最典型情况构建的。

如果您希望在多个字段上建立索引,则有几种解决方案:

  • 最简单:使用多个容器,每个容器都在自己的字段上建立索引,并保留记录的副本(更新记录变得很痛苦)
  • 有点困难:使用多个容器,每个容器都在自己的字段上建立索引并共享记录(std::shared_ptr<ContactInfo>)
  • 较难:与上一个相同,但使用拥有记录的“主”容器以提高效率(并减少间接访问)

  • 对于您的情况,如果您必须更新记录,那么我将从(1)开始,然后移至(2)。

    但是请记住,该更新是一项复杂的任务,因为每次更新记录时,都必须在已更新的字段上重新为其编制索引。为了简化查找​​,您可以在每个容器中保留一个引用该项目的迭代器,并使用这些迭代器进行擦除而无需进行查找:当您将项目放入insert(或map)时,对unordered_map的调用会返回此迭代器。

    09-10 03:26
    查看更多