2

我需要在 32 位中存储大量元素std::vector（超过 unsigned int 允许的 2^32-1）。据我所知，这个数量受std::size_tunsigned int 类型的限制。我std::size_t可以通过强制转换来改变它unsigned long吗？它会解决问题吗？

如果那不可能，假设我以 64 位编译。不做任何修改就可以解决问题吗？

4

3 回答 3

6

size_t是一种可以容纳任何可分配内存块大小的类型。因此，您不能分配比适合您的内存更多的内存size_t，因此无法以任何方式存储更多元素。

以 64 位编译将允许它，但要意识到该数组仍然需要适合内存。2 32是 40 亿，所以你要超过 4 * sizeof(element) GiB 的内存。超过 8 GiB 的 RAM 仍然很少见，因此这看起来不合理。

我建议用STXXL中的向量替换向量。它使用外部存储，因此您的矢量不受 RAM 数量的限制。该库声称可以轻松处理 TB 级数据。

（编辑）迂腐注意：size_t需要保持最大单个对象的大小，不一定是所有可用内存的大小。在分段内存模型中，它只需要在每个对象必须存在于单个段中时适应偏移量，但是对于不同的段，可以访问更多的内存。甚至可以在带有 PAE（“长”内存模型）的 x86 上使用它。但是我还没有看到有人真正使用它。

于 2012-06-22T07:21:59.223 回答
3

有很多话要说。

首先，分别关于 32 位系统和 64 位系统上的大小。std::size_t这就是标准所说的std::size_t（§18.2/6,7）：

6 该类型size_t是实现定义的无符号整数类型，它大到足以包含任何对象的字节大小。

7 [注意：建议实现选择其整数转换等级（4.13）不大于的类型，ptrdiff_t除非需要更大的大小来包含所有可能的值。——尾注]size_tsigned long int

由此可知，在 32 位系统上至少为 32 位，std::size_t在64位系统上至少为 64 位。它可能更大，但这显然没有任何意义。

其次，关于类型转换的想法：要使其工作，即使在理论上，您也必须在其自身的实现中转换（或者更确切地说：重新定义）类型std::vector，无论它发生在哪里。

第三，当你说你需要这个“32 位”的超大向量时，是不是意味着你想在 32 位系统上使用它？在那种情况下，正如其他人已经指出的那样，您想要的是不可能的，因为 32 位系统根本没有那么多内存。

但是，第四，如果您想要在 64 位机器上运行程序，并且仅使用 32 位数据类型来指代元素的数量，但可能使用 64 位类型来指代总大小以字节为单位，std::size_t则不相关，因为它用于指代元素的总数和单个元素的索引，而不是以字节为单位的大小。

最后，如果您在 64 位系统上并且想要使用类似 a 的极端比例的东西std::vector，那当然是可能的。具有 32 GB、64 GB 甚至 1 TB 主内存的系统可能并不常见，但绝对可用。

但是，要实现这样的数据类型，通常在一个连续的块中分配千兆字节的内存通常不是一个好主意（这就是 a所做的），原因如下：std::vector

  • 除非向量的总大小在初始化时一劳永逸地确定，否则向量将被调整大小，并且很可能会重新分配，可能会在您添加元素时多次重新分配。重新分配一个非常大的向量可能是一项耗时的操作。[我已将此项目添加为对原始答案的编辑。]
  • 操作系统将难以提供如此大的未碎片化内存，因为并行运行的其他进程也需要内存。[编辑：正如评论中正确指出的那样，这对于当今使用的任何标准操作系统都不是真正的问题。]
  • 在非常大的服务器上，您还拥有数十个 CPU 和典型的 NUMA 类型的内存架构，显然最好使用相对较小的内存块，并且有多个线程（可能每个线程在不同的核心上运行）访问不同的块并行向量。

结论

A）如果您在 32 位系统上并且想要使用那么大的向量，则使用基于磁盘的方法（例如 @JanHudec 建议的方法）是唯一可行的方法。

B）如果您可以访问具有数十或数百 GB 的大型 64 位系统，您应该研究将整个内存区域划分为块的实现。本质上类似于 a std::vector<std::vector<T>>，其中每个嵌套向量代表一个块。如果所有块都已满，则追加一个新块等。为此实现迭代器类型也很简单。当然，如果你想进一步优化它以利用多线程和 NUMA 特性，它会变得越来越复杂，但这是不可避免的。

于 2012-06-22T08:12:05.160 回答
0

Avector可能是您错误的数据结构。它需要存储在单个内存块中，这受size_t. 这可以通过为 64 位系统编译来增加，但是您不能在 32 位系统上运行，这可能是必需的。

如果您不需要vector' 的特定特征（特别是 O(1) 查找和连续内存布局），则另一种结构（例如 astd::list可能适合您，它没有大小限制，除了计算机可以物理处理的内容，因为它是一个链表代替一个方便包装的数组。

于 2012-06-22T07:26:07.620 回答