2

I am reading c++ primer move section and confused about the move implementation.

Let us say we have one vector that has 4 elements that occupy 4 consecutive memory locations. MEM[0~3]. The capacity of the vector is 4.

Assuming MEM[4] is now not available as it is occupied by another thread or program or due to whatever reason. Is this possible?

Now we need to add another element. Because we must maintain consecutive memory, we can only find another piece of consecutive memory that can host 8 vector entries, for example MEM[5~12]. In this way, we do copy the contents from MEM[0~3] to MEM[5~8] and then add the new element at MEM[9], right?

There is no way we could reuse the old MEM[0~3] and increase capacity while maintaining consecutive addresses.

If it is linked list, i can understand the move. But for array like, I am a bit confused. Please help explain a bit. Thanks.

WriteBackCMO
  • 629
  • 2
  • 9
  • 18
  • You've pretty much described how a typical vector implementation works along with a dynamic memory allocator. What exactly are you confused about? – Quentin Apr 13 '21 at 00:16
  • 1
    Similar: [How do you 'realloc' in C++?](https://stackoverflow.com/q/3482941) – 001 Apr 13 '21 at 00:18
  • This question is very broad, and the answer depends on the implementation of the allocator. Essentially, this is the problem of memory segmentation for which there are many ways to deal with. MEM[0~3] can be reused after the copy in this case. The problem for the implementation is keeping track of those things efficiently. – Emanuel P Apr 13 '21 at 00:19
  • @JohnnyMopp I don't think it is duplicate, that one just basically describes how to use vector's member function to implement realloc. – WriteBackCMO Apr 13 '21 at 00:24
  • @Quentin, i am confused that for my scenario, how can we do "move" instead of "copy". It seems it is unavoidable to copy the contents from MEM[0~3] to MEM[5~8] instead of somehow re-use the MEM[0~3]. – WriteBackCMO Apr 13 '21 at 00:25
  • @EmanuelP, right, maybe i am not familiar with allocator. Can you suggest one way (not necessarily efficient) to re-use the MEM[0~3]. Because vector supports accessing a particular element using VEC[N], the memory must be consecutive, that is where i don't know how to re-use MEM[0~3]. – WriteBackCMO Apr 13 '21 at 00:28
  • 2
    *how can we do "move" instead of "copy"* - for simple types there is no distinction, and for most types there will be some amount of copying, likely the bytes 0-3 to 5-8. The difference of *move* vs *copy* matters more with more complex objects with dynamic resources. See: https://stackoverflow.com/questions/36827900/what-makes-moving-objects-faster-than-copying – kmdreko Apr 13 '21 at 00:39
  • @WriteBackCMO I don't think you understood move correctly. When vector allocates new memory it moves elements instead of copying them. But their content is copied. This about this - imagine you have a vector os unique pointers. But you can't copy a unique pointer, only move. Another example is a vector of vectors. In this case, move will be more efficient, 'cos copying element (vector) would require memory allocation and copying it's content, but with move only pointer to element content is copied. – Michael Nastenko Apr 13 '21 at 00:41
  • @kmdreko thanks so much for the link. (Need to improve my searching skills) " So for light value classes, actually offering two specific implementations, one for l-value, and one for r-values, makes no sense. Offering only the l-value implementation will be more than enough. " This is very helpful to me. Michael also explained vector of vector, i guess only for complicated data structure this makes difference. – WriteBackCMO Apr 13 '21 at 04:33

1 Answers1

4

This is completely outside the scope of the C++ standard.

There's nothing in the standard that prohibits this optimization. It's certainly possible that a particular C++ implementation determines that the std::vector that already used up its reserve()d capacity can be expanded without allocating larger storage and moving the existing contents of the vector into the larger allocated storage.

If so, then this is a very plausible, and sensible optimization. But nothing in the C++ standard requires this specific optimization either. Given that std::vector's storage expansion algorithm already mandates that the resulting vector insertion must have constant amortized time complexity, it is reasonable to conclude that the additional complexity in tracking memory allocation to such a level of detail may produce only marginal gains, in exchange for larger overhead overall, and might actually prove to incur more overhead, overall.

Sam Varshavchik
  • 114,536
  • 5
  • 94
  • 148
  • maybe the standard vector mislead ppl. Can you suggest one way (not necessarily efficient) to re-use the MEM[0~3]. Because vector supports accessing a particular element using vec[N], the memory must be consecutive, that is where i don't know how to re-use MEM[0~3]. To be more general, i am not sure how "move" works when we need to maintain conseucitve memory while the adjacent memory location is used and not available. – WriteBackCMO Apr 13 '21 at 00:31
  • A new, larger, memory block is allocated, the existing contents of the vector get moved there, and the old, smaller, memory block gets deleted. – Sam Varshavchik Apr 13 '21 at 00:47