按價值查找地圖 - 在速度方面偏好方法

Question

四種方法讓我想起按照價值在地圖中查找。這些方法在速度方面的偏好順序是什麼？

假設鍵和值都是唯一的。

std::map<int, std::string>或std::unordered_map<int, std::string>

1. 使用boost::bimap如果Boost庫可
2. 使用std::find_if與謂詞/仿一些相等的比較邏輯
3. 在填充std::map<int, string>的時間，創造&填充 另一std::map<std::string, int>並在第二張地圖上執行map::find。
4. 迭代通過整個地圖，並檢查if (iter->second == value_to_find)， 如果發現break;

我會重點在任何時候通過值進行查找和一次或兩次。

Answer 1

選項2和4的功能完全相同：迭代整個地圖，直到找到匹配的條目。兩種情況下的運行時間爲O(n)。

選項1和3也是等效的。對於地圖，運行時將爲O(log n)，對於無序地圖，運行時將爲O(1)。當你選擇選項3時，你基本上是在重新創造boost：bimap。

所以我建議你去選擇1，並在可用時使用boost:bimap。當boost由於某種原因不可用時，您應該重新編譯這些功能並使用兩個映射並實現代碼以保持它們自己同步。

這當然都是在你要在這個數據結構中存儲這麼多值的前提下實現的。當條目數量很小時，只需使用std::vector並手動迭代它實際上可以成爲速度方面的優秀解決方案。