最快的预打包键值对搜索

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进行相反的搜索.

该地图的大小可能大约为10 000个元素.

我假设二叉树搜索会产生最快的查找时间？是std:映射使用的最佳工具吗？boost会提出任何替代方案吗？

Answer 1

使用unordered_map(hashmap)或map(二叉树) - 可能unordered_map会更快.此外,如果您的键值限制为10000,则a vector<int>将保证恒定时间查找 - 对应"不存在"的矢量元素使用"魔术"值.

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

map并且vector都是标准的.