0

我至少对以下问题的大致答案感兴趣：

int n;
...
std::vector<void*> vectorOfPointers;
vectorOfPointers.reserve(n);

上面提到的程序在O(1)中运行到哪个数字n？

让我们假设一台运行 32 位 Ubuntu 和 3 GB 内存的笔记本电脑，没有运行任何其他程序。是几万，几万，几百万？需要知道哪些信息才能评估这样一个问题？有没有办法在不进行任何实验的情况下找出答案？

我从未研究过任何有关操作系统的东西，但在我的想象中，操作系统只需 2 个步骤即可分配内存。它确定开始块的指针和块结束的指针。情况可能会更复杂，因为系统可能必须整理才能获得足够大的内存块。但是如果我们假设系统只运行这一个程序，我们如何估计需要的时间呢？除了内存碎片，还有其他方面需要考虑吗？

编辑：

对不起，我没有把我的问题说清楚。重要的是要考虑，在调用 reserve 之前向量是空的，因此不需要复制数据。

4

3 回答 3

2

使用时不能依赖 O(1) 复杂度reserve()。

复杂

与容器大小成线性关系

（参见cppreference）

基本上，新内存的分配是在恒定时间内进行的，但是您还需要将旧内存中的旧元素复制到新内存中（因此具有线性复杂性）。

所以在一个空向量上，reserve 可能会有一个恒定的时间，但我不确定标准是否明确说明了它。所以它可能取决于底层实现（即使我没有看到任何不这样做的理由）。

于 2013-01-19T08:16:44.147 回答
2

从 C++ 的角度来看，代码需要时间（它与容器的当前O(1)大小成线性关系，在您的情况下始终为零）。

现在，您的问题似乎实际上是关于分配m内存字节的复杂性。恐怕，这是未指定的。

有关进一步讨论，请参阅内存分配的时间复杂度

为了补充另一个问题中已经说过的内容，有几层复杂性：

  • 首先，malloc()需要维护其内部数据结构。没有具体说明这样做的复杂性，但人们希望这malloc(m)不会花费Θ(m)时间。但是，复杂性很可能取决于其他因素，例如内存碎片。
  • 其次，malloc()可能需要向操作系统请求额外的内存。在这里，期望操作系统对它分配的每个内存页做一些事情并不是没有道理的（例如，擦除它，这样你就不会看到其他人的机密数据）。如果发生这种情况，手术确实会是Θ(m)。
于 2013-01-19T08:17:01.077 回答
1

我唯一O(1)能想到的std::vector::reserve()是什么时候n <= capacity()什么reserve()都不做。

于 2013-01-19T08:21:02.593 回答