Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does std::vector *have* to move objects when growing capacity? Or, can allocators "reallocate"?

A different question inspired the following thought:

Does std::vector<T> have to move all the elements when it increases its capacity?

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.

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 reallocate(std::size_t) function which would return a pair<pointer, bool> and could map to the underlying realloc()? The advantage of this would be that in the event that the OS can actually just extend the allocated memory, then no moving would have to happen at all. The boolean would indicate whether the memory has moved.

(std::realloc() 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 extend_or_malloc_new(). Edit: Perhaps a is_pod-trait-based specialization would allow us to use the actual realloc, including its bitwise copy. Just not in general.)

It seems like a missed opportunity. Worst case, you could always implement reallocate(size_t n) as return make_pair(allocate(n), true);, so there wouldn't be any penalty.

Is there any problem that makes this feature inappropriate or undesirable for C++?

Perhaps the only container that could take advantage of this is std::vector, but then again that's a fairly useful container.


Update: A little example to clarify. Current resize():

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; 

New implementation:

pair<pointer, bool> pp = alloc.reallocate(buf, new_size);  if (pp.second) { /* as before */ } else           { /* only construct new elements */ } 
like image 327
Kerrek SB Avatar asked Nov 03 '11 23:11

Kerrek SB


People also ask

Does std::vector resize change capacity?

The C++ function std::vector::resize() changes the size of vector. If n is smaller than current size then extra elements are destroyed. If n is greater than current container size then new elements are inserted at the end of vector.

What happens when you std :: move a vector?

std::move. std::move is used to indicate that an object t may be "moved from", i.e. allowing the efficient transfer of resources from t to another object. In particular, std::move produces an xvalue expression that identifies its argument t . It is exactly equivalent to a static_cast to an rvalue reference type.

What does std::vector do?

1) std::vector is a sequence container that encapsulates dynamic size arrays. 2) std::pmr::vector is an alias template that uses a polymorphic allocator. The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets to regular pointers to elements.

Does std::vector always allocate?

std::vector typically allocates memory on the heap (unless you override this behavior with your own allocator). The std::vector class abstracts memory management, as it grows and shrinks automatically if elements are added or removed.


2 Answers

When std::vector<T> runs out of capacity it has to allocate a new block. You have correctly covered the reasons.

IMO it would make sense to augment the allocator interface. Two of us tried to for C++11 and we were unable to gain support for it: [1] [2]

I became convinced that in order to make this work, an additional C-level API would be needed. I failed in gaining support for that as well: [3]

like image 196
Howard Hinnant Avatar answered Sep 23 '22 15:09

Howard Hinnant


In most cases, realloc will not extend the memory, but rather allocate a separate block and move the contents. That was considered when defining C++ in the first place, and it was decided that the current interface is simpler and not less efficient in the common case.

In real life, there are actually few cases where reallocis able to grow. In any implementation where malloc has different pool sizes, chances are that the new size (remember that vector sizes must grow geometrically) will fall in a different pool. Even in the case of large chunks that are not allocated from any memory pool, it will only be able to grow if the virtual addresses of the larger size are free.

Note that while realloc can sometimes grow the memory without moving, but by the time realloc completes it might have already moved (bitwise move) the memory, and that binary move will cause undefined behavior for all non-POD types. I don't know of any allocator implementation (POSIX, *NIX, Windows) where you can ask the system whether it will be able to grow, but that would fail if it requires moving.

like image 32
David Rodríguez - dribeas Avatar answered Sep 24 '22 15:09

David Rodríguez - dribeas