c++ - 具有随机访问权限的列表的 STL 容器？

Question

有没有类似列表元素不连续存储的STL容器？此容器的大小最多可达 1000x1000 个元素，每个元素都是一个包含 36 个 double 值的 vector 。这将是一个很大的 block 来存储在一起(大约 200 兆字节)。是否有一种变体将指向其内容的指针存储为单独的 vector ，以便允许随机访问。是否有一个已经存在的 STL 容器类，或者我应该手动存储指针？

我需要的容器实际上是一个恒定大小，所以我认为自己实现它不会太困难，但我想知道是否已经存在用于此的 STL 容器。我想避免使用 vector ，因为列表很大而且内容将是中等大小。如果容器中的 vector 不需要彼此相邻，那么将它们分开放在列表中以防止内存因碎片耗尽不是更好吗？

Answer 1

两者都是 deque<array<double, 36>>和 vector<vector<double>>将避免需要任何真正巨大的连续分配。

vector<vector<double>>在这些方面更糟。对于您指定的数字，它需要连续分配 1000*1000*sizeof(vector<double>) ，这是 MB 的低 10 秒(很可能 vector 是 3 个指针的大小)。这在“合适的计算机”(台式机或服务器)上很少是个问题。由于碎片原因(小虚拟地址空间或根本没有虚拟寻址)而需要关注的地方，您可能还有一个更基本的问题，即您无论如何都没有 300MB 左右的 RAM。但是您可以通过避免它来玩得更安全，因为显然存在您可以分配总共 300MB 但不能连续分配 12MB 的环境。

没有std::array在 C++03 中，但是有 boost::array或者您可以轻松编写一个类来表示 36 个 double 。

vector<array<double, 36>>碎片问题最严重，它需要连续的 250 MB 分配。就我个人而言，我发现在测试“我们将面临的最糟糕的内存碎片”时模拟并不容易，但我不是最好的测试员。这个 block 的大小大约是我在 32 位进程中开始感到有点不安的地方，但它在良好的条件下可以正常工作。