一般来说，c++ 中的地图或矢量哪个更好？

Question

据我所知，访问向量中的元素需要恒定时间，而访问映射中的元素需要对数时间。然而，存储地图比存储矢量占用更少的内存。

所以我想问一下一般来说哪一个比较好？我正在考虑在我的程序中使用这两个之一，该程序包含大约 1000 个元素。我计划使用 3 维向量，它需要 1000x1000x1000 个元素。

Answer 1

这个问题没有正确答案。正确的问题应该是“哪个更适合特定应用程序——在此处插入您的项目——”。要选择正确的容器，您需要解释它将如何使用。

Answer 2

地图是一个关联容器——它提供与向量完全不同的功能。如果要将键与值关联起来，请使用映射。如果您的键只是非负连续整数，那么向量在各个方面都更优越。

Answer 3

矢量和地图是用于不同目的的两个不同的容器。如果有一个更好，另一个就不会存在......

Answer 4

首先，存储映射几乎肯定会比向量占用更多的内存，因为向量只是一个连续的块，而映射包含树结构。

关于哪个更好的问题的答案是，这取决于您要解决的问题。这实际上取决于您希望如何为数据建立索引。如果您的数据可以通过整数线性索引，那么向量将表现最好。

但是，在很多情况下您会希望以其他方式访问数据。例如，如果您想使用字符串对数据进行索引（如字典查找），那么地图的性能会更好。要使用向量对字符串数据进行索引，如果不保持向量排序，则必须执行线性搜索 (O(n)) 来查找元素。映射只需执行二分搜索 (O(log n))，随着 n 的增长，速度会快很多。

Answer 5

一般来说，没有更好的事情。这完全取决于您要执行的操作以及这些操作的频率。

对于相同数量的元素，向量不会比映射使用更多的空间。然而，这样的事情，例如稀疏矩阵，有时可以使用映射更有效地实现。

Answer 6

如果您有稀疏的 3 维数组，则可以使用带有键作为索引组合的映射来节省大量内存。对于您的情况，索引 < 1000，key可以是32位无符号整数：

#include <stdint.h>
...
int index1 = 12, index2 = 34, index3 = 56;

// construct key:
uint32_t key = 
  ((index1&0x3FF) << 20) | 
  ((index2&0x3FF) << 10) | 
  (index3&0x3FF)
  );

// restore indexes:
index1 = (key >> 20) & 0x3FF;
index2 = (key >> 10) & 0x3FF;
index3 = (key) & 0x3FF;

Answer 7

坦率地说，建议您创建 1,000,000,000 个空对象来存储 1000 个有用的对象，这是荒谬的。如果您认为向量会更快，那么当您考虑所有交换文件抖动、动态内存分配以及随之而来的不必要的对象构造时，您可能就大错特错了！

您的应用程序的描述可能太模糊；但如果一个值可以通过 x,y,z 索引；然后使用包含 x,y,z 的对象作为映射键。定位 1000 个物体并不需要很长时间 - 这是一张非常小的地图。

Answer 8

如果你想要一个键值组件，请使用map。如果您想要按数字随机访问解决方案或迭代排序解决方案，请使用向量。

检查您的数据结构/算法分析文本以获取更多信息。

Answer 9

我认为 vector<> 是容器的最佳默认选择（vector 除外）。如果我有理由更喜欢另一个容器，我会使用另一个；如果没有，我使用vector（或deque）。这已经是我能达到的“总体上更好”的最接近结果了。

所有 STL 容器都是有原因的，它们比任何其他容器都做得更好。如果不知道您将使用数据结构做什么，我无法提供更多帮助。

然而，使用错误结构的惩罚随着规模的增加而增加。如果您有几十个元素，任何类都可以。如果您谈论的是 10 亿个元素，您确实希望正确处理（并确保您的计算机能够处理它 - 您可能需要一个具有大量 RAM 的 64 位应用程序）。

Answer 10

Deque 是比映射更合适的向量替代品。但这取决于您的需求。向量需要线性内存来存储其所有数据，但双端队列则不需要。在大多数情况下，双端队列可以用作向量的替代品。

Answer 11

如果您的 3D 矩阵填充稀疏（即大部分为零），那么您会对 boost::ublas::sparse_matrix。如果我没记错的话，默认情况下，它使用 std::map 作为底层容器。它提供了用于轻松行/列索引的运算符（以及行/列/元素迭代器）。

编辑：没关系，我以为 boost::ublas 有 3D 矩阵。看来并非如此。似乎 sparse_matrix 已被具有稀疏存储的新矩阵类型所取代。我已经很久没有使用那个库了。

您仍然可以查看 Boost.uBlas 来获取滚动您自己的稀疏 3D 矩阵的灵感。