带有lookuptime O(1)的C++数据结构,就像stl中java的hashmap一样？

Question

c ++标准库中有这样的结构吗？我无法访问其他任何东西,因此tr1中的unordered_map无法使用(和boost等).

我所拥有的是我需要存储的大量自定义类元素100000+,并且在everage上非常快速地访问它们O(1).我不能使用数组/向量,因为元素将随机存储,我不知道元素的位置.

我唯一的替代方法是实现一个只有c ++标准库可用的自己的hashmap实现吗？

Answer 1

如果您真的被限制std::并且不能使用其他任何东西,那么std::map最好的选择.这只给你对数查找时间,而不是常数查找时间,但与数组/向量相比,它将非常快.此外,我想只有100000个元素,对数查找将足够快,你不会通过使用哈希表赢得太多.

话虽这么说,你的实现可能已经包含了一些哈希表实现.所以如果std::map真的不够快,试试吧

#include <tr1/unordered_map>
std::tr1::unordered_map<int,int> test;

要么

#include <hash_map>
stdext::hash_map<int,int> test;

甚至

#include <boost/tr1/unordered_map.hpp>
std::tr1::unordered_map<int,int> test;

Answer 2

问题是O(1)查找不是标准的.我不确定boost有什么,但是一些STL实现(比如sgi)有hash_map.这就是你所需要的.

这是文档.

试试吧:

#include <hash_map>

请记住,如果这样做,它是不可移植的...但也许现在没关系,以后你可以找到解决方法.