Home > database >  What's going on when we expand std::vector<>?
What's going on when we expand std::vector<>?

Time:11-16

What happens when we do push_back with size() == capacity()?

I've heard a lot of opinions regarding this question. Most popular is: when the vector's size reaches its capacity, it allocates a new region of memory, copies the vector to the newly allocated memory, and inserts new value to the vector's end.

But, why do we have to do it? We have a virtual memory mechanism, we can just call realloc(vec.data(), (sizeof(vec::value_type) * vec.size()) * 2). The Allocator will give us a new memory page, and virtual addresses make the memory "consistent", so we don`t have to copy values from the vector.

Do I understand the virtual memory mechanism wrong?

CodePudding user response:

You understand virtual memory mechanism correctly, basically you can create any amount of continuous page-aligned arrays in the proces' virtual memory space and they would be backed by non-contiguous physical memory.

But that is irrelevant to std::vector because std::allocator does not provide any API to take advantage of that, I think some see this as an oversight.

Just be mindful that C is not restricted to only architectures supporting virtual memory, although I think it would be an implementation detail of the standard library if it were implemented anyway.

No, you cannot use C realloc because C has objects with real lifetimes, everything is not just a blob of bytes that can be freely copied at whim, some special blobs might not like being moved and they will not appreciate it if you force them to.

Yes, if you are dealing with PODs, this would work with a custom::vector, not std::vector based on std::allocator.

There is a paper in works which addresses your concerns and goes beyond realloc, arguing "its day has passed" - P0901 which few days ago received rather positive feedback from the committee.

  • Related