c++ - 有效地在对象的链接列表中搜索字符串

Question

由于某些原因，我有一个对象链接列表，其中包含一个字符串的对象。

我可能需要搜索特定字符串，并在此过程中根据该字符串检索对象。

列表的起始标题是我对列表的唯一输入。

尽管我拥有的对象数量上限为 3000，而且数量不多，但我仍然想知道是否有一种有效的方法可以做到这一点，而不是逐个搜索对象以查找匹配的字符串。

列表中的对象没有以任何方式排序，我不能指望它们被排序，链表的入口点是我唯一的输入。

那么，谁能告诉我是否有一种有效的方法（也许是搜索算法）来实现这一目标？

单独针对这种搜索，如果需要，假设这种搜索是对象的数据最密集的功能，推荐的数据结构是什么？

谢谢..

Answer 1

使用std::map<std::string, YourObjectType>. 您仍然可以迭代所有对象。但它们现在按字符串排序。

如果您可能有多个具有相同字符串的对象，请改用 a multimap。

Answer 2

有 3000 个，您想使用 aunordered map而不是链表，这将为您提供平均 O(1) 查找、插入和删除时间。

Answer 3

如果你不能切换到任何不同的结构/容器，那么没有比线性到列表大小更好的方法了。