Does std :: vector * * have for moving objects while increasing capacity? Or, can distributors "redistribute"?

Question

A different question inspired the following thought:

Does std::vector<T> need to move all elements while increasing its capacity?

As I understand it, the standard behavior is that the base allocator will request the entire fragment of a new size, then move all the old elements, then destroy the old elements and then free up the old memory.

This behavior is the only possible correct solution, given the standard distributor interface. But I was wondering if it would be advisable to make corrections to the allocator to offer the reallocate(std::size_t) function, which would return pair<pointer, bool> and could map to the base realloc() ? The advantage of this would be that if the OS could actually just expand the allocated memory, then no movement should occur at all. A boolean value indicates whether memory has been moved.

( std::realloc() may not be the best choice, because we don’t need to copy the data if we can’t extend it. So we really would like to get something like extend_or_malloc_new() . Edit: Maybe is_pod - Specialized specialization would allow us to use the actual realloc , including a battered copy of it. Just not in general.)

Seems like a missed opportunity. In the worst case, you can always implement reallocate(size_t n) as return make_pair(allocate(n), true); therefore there would be no penalty.

Is there any problem that makes this function unacceptable or undesirable for C ++?

Perhaps the only container that can take advantage of this is std::vector , but again, that is a pretty useful container.

---

Update: A small 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 */ } 

Answer 1

When std::vector<T> is out of capacity, it should allocate a new block. You correctly explained the reasons.

IMO, it would be advisable to expand the dispenser interface. Two of us tried to use C ++ 11, and we could not get support for it: [1] [2]

I made sure that an additional level C API is required to complete this work. I also could not get support: [3]

Answer 2

In most cases, realloc will not expand memory, but rather allocates a separate block and moves the contents. This was taken into account when defining C ++ in the first place, and it was decided that the current interface is simpler and no less efficient in the general case.

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

Please note that while realloc can sometimes increase the amount of memory without moving, but by the time realloc complete, it could move (bit by bit) the memory, and this binary move will result in undefined-POD behavior. I don’t know of any dispenser implementation (POSIX, * NIX, Windows) where you can ask the system if it can grow, but it will not work if it requires moving.

Answer 3

Yes, you are right that the standard distributor interface does not provide optimization for memcpy'able types.

One could determine whether the memcpy'd type could use a library of properties of a formatted type (not sure if they would provide it out of the box, or whether it would be necessary to create a discriminator of a composite type based on boost).

In any case, to use realloc() , you could create a new container type that can explicitly use this optimization. With the current standard distributor interface, this is not possible.