有效搜索字符串的對象的鏈接列表

Question

由於某些原因，我有一個鏈接的對象列表，Object包含一個字符串。

我可能需要搜索特定的字符串，並根據該字符串檢索對象。

列表的起始標題是列表中的唯一輸入。

儘管我擁有的對象的數量被限制在3000，但這還不算太多，我仍然想知道是否有一種有效的方法可以做到這一點，而不是逐個搜索匹配的字符串。

列表中的對象沒有以任何方式排序，我不能指望它們被排序，並且鏈接列表的入口點是我唯一的輸入。

那麼，有誰能告訴我，如果有一種有效的方法（也許搜索算法）來實現這一目標？

另外，對於這種搜索，如果需要，假設此搜索是對象的數據密集度最高的功能，那麼推薦的數據結構是什麼？

謝謝..

Answer 1

使用std::map<std::string, YourObjectType>。您仍然可以迭代所有對象。但是他們現在按字符串排序。

如果您可能有多個具有相同字符串的對象，請改爲使用multimap。

Answer 2

擁有3000個你想使用unordered map而不是一個鏈表，這會給你平均的O（1）查找，插入和刪除時間。

Answer 3

如果你不能切換到任何不同的結構/容器，那麼沒有辦法比列表的大小線性更好地做到這一點。