我正在处理一组对象，其合理大小可能在 1 到 50K 之间（但没有设定上限）。每个对象都包含一些字符串。
我想实现一个搜索函数，该函数可以部分、完全或正则表达式匹配这些字符串中的任何一个，然后返回一个对象列表。
如果每个对象只包含一个字符串，那么我可以简单地按字典顺序对它们进行排序，并相当容易地拉出范围 - 但map由于速度/内存问题，我不愿意为每个包含的字符串实现类似的结构。
是否有适合这种操作以提高速度和内存效率的数据结构？我感觉到数据库可能即将出现，但我对它们知之甚少，所以我想推迟研究，直到有更多知识渊博的人能够将我推向正确的方向！
类似地图的集合可能是您最好的选择，键是字符串，值是对包含对象的引用。如果您的字符串作为 stl 字符串保存在对象中，那么您可以将数据的引用存储在映射的关键部分中（或者使用 shared_ptr 作为字符串并在对象和映射中引用它们）
搜索、排序只是实现使用取消引用数据的自定义搜索函子的问题。地图的大小将是 2 个引用加上地图开销，如果您考虑替代方案将同样大，即使不是更大，这也不会那么糟糕。
部分、完全或 RegEx 匹配这些字符串中的任何一个，并随后返回对象列表
好吧，对于完全匹配，你可以有一个std::map<std::string, std::vector<object*> >. 键将是确切的字符串，并且vector保存指向匹配对象的指针，其中许多指针可能指向单个对象实例。
你可以有一个从部分字符串到完整字符串的前端映射：假设字符串是“dogged”，你不得不为“dogged”、“ogged”、“gged”、“ged”、“ ed" 和 "d" （如果您想要最小匹配大小，请在任何地方停止）...然后使用 lower_bound 进行搜索。这样，假设您搜索“dog”，您仍然可以看到匹配“dogged”（它是否匹配说“dogfood”并不重要。这将是一个简单的std::map<string, string>。当您从 lower_bound 向前递增时位置并且字符串仍然匹配（即从 dogfood 到 dogged to ... 直到它不以 dog 开头），您可以在“精确匹配”映射中搜索并汇总结果。
对于正则表达式，我没有什么好的建议……我将从暴力搜索所有完整字符串开始。如果它真的不够好，那么你会做一些粗略的优化，比如在进行蛮力匹配之前检查要过滤的常量子字符串，但我无法想象如何非常彻底和快速地做到这一点。
object*（如果有用，用你最喜欢的智能指针替换s）