请问C++的容器中用index访问元素，array、vector、hash_map哪个最快？

Question

请问C++的容器中，如果用index访问容器里的元素，数组、vector、哈希表（假设没有碰撞）哪个最快？

我的猜测是：从快到慢为数组、vector、哈希表。因为vector要检查边界，hash_map要用hash function重新算出hash index，即使没有碰撞也多了一个运算步骤。不知道这个答案是否正确呢？

Answer 1

肯定是array快啊，vector和hashtable都是对array的封装啊。
区别array在编译期要确定大小，而vector不用，它是new出来的array。而hashtable会有碰撞啊！

Answer 2

不能说你错，至少不准确，哈希表有很多的，int hash[N]，这个hash就和数组速度一样，oj做题常用。

array和vector一样快，都是数组，都是容器，都要检查边界。

hash_map现在c++已经没了，c++11之前的东西，其内部是hashtable，确实hashtable也用的hash，但是它的hash是建立在“指针数组”结构上，查找虽然也是常数复杂度，但是应该是比那两个多，详情参见侯捷的《STL源码剖析》。

（“数组”和“array”是两个概念，“哈希表”和“hash_map”也是两个概念，我都不知道该看你的标题，还是你的正文了。。。。。汗。。。。。。）