c++ - 按值在 map 中查找 - 方法在速度方面的偏好

Question

我想到了四种在 map 中按值查找的方法。就速度而言，这些方法的优先顺序是什么？

假设键和值在它们之间是唯一的。

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在第二张 map 上。
4. 遍历整个 map 并检查if (iter->second == value_to_find) ,如果找到break;

我将一直按键查找，按值查找一次或两次。

Answer 1

选项 2 和 4 做的是完全相同的事情:逐个条目地迭代整个 map ，直到找到匹配的条目。两种情况下的运行时间都是 O(n)。

选项1和3也是等价的。 map 的运行时间为 O(log n)，无序 map 的运行时间为 O(1)。当您选择选项 3 时，您实际上是在重新发明 boost:bimap。

所以我建议您选择选项 1 并在可用时使用 boost:bimap。当 boost 由于任何原因不可用时，您应该重建功能并使用两个 map 并实现代码以自行保持它们同步。

当然，这一切都是在您要在此数据结构中存储如此多实际重要的值的前提下进行的。当条目数量较少时，仅使用 std::vector 并手动迭代它实际上是速度方面的最佳解决方案。