c++ - 在包含多个字符串的许多对象中查找子字符串

Question

我正在处理一组对象，其合理大小可能在 1 到 50K 之间(但没有设置上限)。每个对象都包含一些字符串。

我想实现一个搜索功能，该功能可以部分、完全或正则表达式匹配这些字符串中的任何一个，然后返回一个对象列表。

如果每个对象只包含一个字符串，那么我可以简单地按字典顺序对它们进行排序，并相当容易地拉出范围 - 但我不愿意为每个包含的字符串实现类似 map 的结构由于速度/内存问题。

是否有一种数据结构非常适合这种速度和内存效率的操作？我感觉到一个数据库可能即将出现，但我对它们知之甚少，所以我想推迟研究，直到更有知识的人可以将我推向正确的方向!

Answer 1

类似 map 的集合可能是您最好的选择，键是字符串，值是对包含对象的引用。如果您的字符串作为 STL 字符串保存在对象内部，那么您可以将对数据的引用存储在 map 的关键部分(或者对字符串使用 shared_ptr 并在对象和 map 中引用它们)

搜索、排序只是实现一个 custom search functor 的问题使用取消引用的数据。 map 的大小将是 2 个引用加上 map 开销，如果您认为备选方案也一样大，如果不是更大的话，这不会那么糟糕。