For what argument is std::vector<void*>::reserve an O(1) time operation?
<p>I am interested in at least an approximate answer to:</p>

<pre><code>int n;
...
std::vector&lt;void*&gt; vectorOfPointers;
vectorOfPointers.reserve(n);
</code></pre>

<p>For up to which number <strong>n</strong> does the above mentioned program run in <strong>O(1)</strong> ? </p>

<p>Let us suppose that for a laptop running 32 bit Ubuntu with 3 gigabytes of memory, not running any other programs. Is it tens, thousands, millions? What information does one need to know to be able to asses such a question? Is there a way to find out without running any experiments?</p>

<p>I have never studied anything about operating systems but in my imagination, the operating system allocates memory in just 2 steps. It determines the pointer to start the chunk and the pointer of the end of the chunk. The situation can be more complicated because the system may have to tidy up in order to get a big enough chunk of memory. But if we suppose that the system runs just this one program, how can we estimate the time needed? Are there some other aspects to be considered, besides the fragmentation of memory?</p>

<p>EDIT:</p>

<p>sorry, I didn't make my question clear. It is important to consider, that the vector is empty before calling reserve, so no copying of data is required.</p>
