StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PODoes std::vector *have* to move objects when growing capacity? Or, can allocators "reallocate"?
text
Body
copied!<p>A <a href="https://stackoverflow.com/questions/8002615/is-it-possible-to-find-the-sizeoft-when-creating-a-template-in-c/8002636#8002636">different question</a> inspired the following thought:</p> <p>Does <code>std::vector<T></code> <em>have</em> to move all the elements when it increases its capacity?</p> <p>As far as I understand, the standard behaviour is for the underlying allocator to request an entire chunk of the new size, then move all the old elements over, then destroy the old elements and then deallocate the old memory.</p> <p>This behaviour appears to be the only possible correct solution given the standard allocator interface. But I was wondering, would it make sense to amend the allocator to offer a <code>reallocate(std::size_t)</code> function which would return a <code>pair<pointer, bool></code> and could map to the underlying <code>realloc()</code>? The advantage of this would be that in the event that the OS can actually just <em>extend</em> the allocated memory, then no moving would have to happen at all. The boolean would indicate whether the memory has moved.</p> <p>(<code>std::realloc()</code> is maybe not the best choice, because we don't need do copy data if we cannot extend. So in fact we'd rather want something like <code>extend_or_malloc_new()</code>. <em>Edit:</em> Perhaps a <code>is_pod</code>-trait-based specialization would allow us to use the actual <code>realloc</code>, including its bitwise copy. Just not in general.)</p> <p>It seems like a missed opportunity. Worst case, you could always implement <code>reallocate(size_t n)</code> as <code>return make_pair(allocate(n), true);</code>, so there wouldn't be any penalty.</p> <p>Is there any problem that makes this feature inappropriate or undesirable for C++?</p> <p>Perhaps the only container that could take advantage of this is <code>std::vector</code>, but then again that's a fairly useful container.</p> <hr> <p>Update: A little example to clarify. Current <code>resize()</code>:</p> <pre><code>pointer p = alloc.allocate(new_size); for (size_t i = 0; i != old_size; ++i) { alloc.construct(p + i, T(std::move(buf[i]))) alloc.destroy(buf[i]); } for (size_t i = old_size; i < new_size; ++i) { alloc.construct(p + i, T()); } alloc.deallocate(buf); buf = p; </code></pre> <p>New implementation:</p> <pre><code>pair<pointer, bool> pp = alloc.reallocate(buf, new_size); if (pp.second) { /* as before */ } else { /* only construct new elements */ } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload