c++ - 需要选择一个容器来存储我的数据

Question

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

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();
};

如果我将它保存在以“name”为键的映射中，如果我通过“description”、“phoneNumber”或“email”进行搜索，我将不得不执行线性搜索。

我的问题是:我是否有更好的方法来保留数据以进行更快的搜索？

Answer 1

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

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

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

对于您的情况，我会从 (1) 开始，如果您必须更新记录，我会转到 (2)。

但请记住，更新是一项复杂的任务，因为每次更新记录时都必须在更新的字段上重新编制索引。为了简化查找​​，您可以在每个引用该项目的容器中保留一个迭代器，并使用它们来删除而不进行查找:此迭代器通过调用 insert 返回。当您将商品放入 map 时(或 unordered_map )。