使用整数键和向量的映射之间的差异

Question

向量是带有整数键的unordered_map的特殊形式吗？看起来是这样,因为矢量也有整数键.

如果没有,有什么区别？

Answer 1

Vector是一个数组周围的容器.

无序映射是二叉树周围的容器.

这意味着它们具有不同的性能特征.一些例子:

• 通过索引访问元素是向量/数组中的常量时间操作,但是是二叉树中的对数时间操作.两者都很便宜,但在矢量上它甚至更快.
• 增加向量的容量是昂贵的(线性时间),但对于二叉树来说是便宜的(对数时间).

Answer 2

主要区别在于数据的存储方式.

A vector将数据存储在调整大小的内部数组中,并添加更多元素.一个unordered_map内部使用哈希表.

实际上,a vector给你在后面进行摊销的恒定时间插入(它需要一次调整大小和复制/移动所有内容),通过索引进行恒定时间访问,以及最多线性时间插入和删除(所有后续元素必须是移动).此外,由于a vector是连续的,您可以将其传递给期望c样式数组的函数.

unordered_map 为您提供按密钥分摊的常量时间(因为散列不完美,并且冲突迫使查找遍历内部链接列表),分摊的常量时间插入和删除.

请参阅:http://en.cppreference.com/w/cpp/container/unordered_map 和:http://en.cppreference.com/w/cpp/container/vector