我想用c++(伪代码)实现以下数据结构:
Map<Integer, Integer> // Key->Value pairs
Map.put(1,6);
Map.put(2,5);
Map.put(6,89);
Map.put(7,23);
... etc ...
Map.get(2) .... returns 5
换句话说，给定一对整数，其中一个是查找键，让我从其中一个键检索值的最快库实现是什么？ Value->Key 的反向搜索不需要。
此 map 的大小可能约为 10 000 个元素。
我假设二叉树搜索会产生最快的查找时间？ std:map 是最好用的工具吗？ boost 是否提供任何替代方案？
最佳答案
使用unordered_map ( HashMap )或 map (二叉树)- 可能 unordered_map会更快。此外，如果您的键值限制为 10000，则 vector<int>将保证恒定时间查找 - 对应该“不存在”的 vector 元素使用“魔法”值。
unordered_map是 TR1 和 c++0x 的一部分——它不是 c++03 中的标准。许多实现都支持它。 Boost 也有一个 unordered_map .
map和 vector都是标准的。
-
map对应javaTreeMap -
unordered_map对应javaHashMap -
vector对应javaArrayList
关于c++ - 最快的预打包键值对搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5254560/