Why don't compilers try to allocate contiguous memory (if possible) when vector is full?

Question

When std::vector gets full, new memory is allocated. From what I read, the new capacity grows in a geometric progression (but this is irrelevant to the question), then the old information is copied in the new memory region, and the old one is freed.

Based on this assumption, my questions are:

1. Why don't compilers try to see if there's enough contiguous free-to-use memory at the end of our std::vector, allocate just a portion at the end of our std::vector, and don't waste time copying?

2. Did people try to implement this, but it was decided it's not worth to do it? (on the average/always)

3. Are there are any other, more subtle, reasons why this is not happening?

Answer 1

It is a combination of your points 2) and 3).

First it was reasoned (I cannot say how much measuring has been done at the time) that the benefits were rare and not so great. You can only (significantly) grow memory iff no allocation happened after the origninal allocation, and the cost of growing a vector is amortized.

However many have pointed out that even this scenario is not so rare, and can significantly improve performance and prevent memory fragmentation. So there was a proposal in 2006.

This is were the more subtle reasons kicked in. The first problem is that Containers do not allocate memory by themselfs, but use an Allocator to do so. So as a first step the allocator interface would need to be changed. This is difficult because, as others have noted, realloc can only be used if the contained type is trivial. To be generally useful we would need a different low level function to grow memory (one that reallocates only if it can be done inplace, see the proposal for details). The problem there is that not all platforms provide such a function, and so we would need Posix or the C standard to provide one first.