std::vector<void*>::reserve是一个O(1)时间操作是什么参数？
我对以下问题至少有一个大致答案感兴趣：
int n;
...
std::vector<void*> vectorOfPointers;
vectorOfPointers.reserve(n);上面提到的程序在O(1)中运行到哪个数字？
让我们假设，对于运行3G内存的32位Ubuntu的膝上型计算机，不运行任何其他程序。是几万，数千，数百万吗？你需要知道哪些信息才能回答这样的问题？有没有办法不用做任何实验就找出答案呢？
我从来没有研究过有关操作系统的任何东西，但在我的想象中，操作系统只在两个步骤中分配内存。它确定要启动块的指针和块尾的指针。情况可能会更复杂，因为为了获得足够大的内存块，系统可能需要清理。但是如果我们假设系统只运行这一个程序，我们如何估计所需的时间？除了内存碎片之外，还有其他方面需要考虑吗？
编辑：
抱歉我没说清楚我的问题。必须考虑的是，在调用备用之前，向量是空的，因此不需要复制数据。
回答 3
Stack Overflow用户
发布于 2013-01-19 08:17:01
从C++的角度来看，代码需要O(1)时间(在容器的当前大小中它是线性的，在您的情况下总是为零)。
现在看来，您的问题实际上是关于分配m字节内存的复杂性。恐怕这一点还没有具体说明。
有关进一步讨论，请参见内存分配的时间复杂性
除了在另一个问题中已经说过的话之外，还有几个层次的复杂性：
- 首先，
malloc()需要维护其内部数据结构。这样做的复杂性没有具体说明，但人们希望malloc(m)不会占用Θ(m)时间。然而，复杂程度很可能取决于其他因素，如内存碎片。 - 其次，
malloc()可能需要从操作系统请求额外的内存。在这里，期望操作系统对它分配的每一个内存页做一些事情并不是不合理的(例如，擦除它，这样你就不会看到其他人的机密数据)。如果发生这种情况，操作将确实是Θ(m)。
Stack Overflow用户
发布于 2013-01-19 08:16:44
在使用reserve()时，不能依赖O(1)的复杂性。
复杂性 容器的大小成线性
(cf 优先选择)
基本上，新内存的分配是固定时间的，但是您还需要将旧的元素从以前的内存复制到新的内存中(因此产生了线性复杂性)。
因此，对于空向量，保留可能有一个恒定的时间，但我不确定标准是否明确地说明了这一点。因此，这可能取决于底层实现(即使我没有看到任何不这样做的理由)。
Stack Overflow用户
发布于 2013-01-19 08:21:02
我唯一能想到的O(1)是std::vector::reserve()，那就是n <= capacity()，这意味着reserve()什么都不做。
https://stackoverflow.com/questions/14412402
复制相似问题
腾讯云开发者
