我有一个数据,我需要对其进行搜索和排序。数据只是一堆结构对象,看起来像这样:
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”进行搜索,我将不得不执行线性搜索。
我的问题是:我是否有更好的方法来保留数据以进行更快的搜索?
最佳答案
关联的 STL 容器(map
和 unordered_map
)是围绕单个索引的最典型情况构建的。
如果你希望在多个字段上建立索引,你有几种解决方案:
- 最简单:使用多个容器,每个容器都在自己的字段上建立索引并保留一份记录拷贝(记录更新变得很痛苦)
- 更难一点:使用多个容器,每个容器在自己的字段上建立索引并共享记录(
std::shared_ptr<ContactInfo>
) - 更难:与之前相同,但使用拥有记录的“主”容器以提高效率(并减少间接访问)
对于您的情况,我会从 (1) 开始,如果您必须更新记录,我会转到 (2)。
但请记住,更新是一项复杂的任务,因为每次更新记录时都必须在更新的字段上重新编制索引。为了简化查找,您可以在每个引用该项目的容器中保留一个迭代器,并使用它们来删除而不进行查找:此迭代器通过调用 insert
返回。当您将商品放入 map
时(或 unordered_map
)。
关于c++ - 需要选择一个容器来存储我的数据,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23044143/