c++ - 最快的预打包键值对搜索

Question

我想用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 是否提供任何替代方案？

Answer 1

使用unordered_map ( HashMap )或 map (二叉树)- 可能 unordered_map会更快。此外，如果您的键值限制为 10000，则 vector<int>将保证恒定时间查找 - 对应该“不存在”的 vector 元素使用“魔法”值。

unordered_map是 TR1 和 c++0x 的一部分——它不是 c++03 中的标准。许多实现都支持它。 Boost 也有一个 unordered_map .

map和 vector都是标准的。

• map对应java TreeMap
• unordered_map对应java HashMap
• vector对应java ArrayList