20

Consider the following code:

std::vector vec;
vec.reserve(500);
size_t cap = vec.capacity();

std::vector newVec = std::move(vec);
assert(cap == newVec.capacity());

In pretty much any implementation you run across, this will work. I don't care about what implementations do. I want to know what the standard requires. Will the moved-to vector have the same capacity as the original? Or will the assert trigger?

ildjarn
  • 62,044
  • 9
  • 127
  • 211
Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
  • 5
    If the capacity were to change, that would completely break the motivation for having move semantics in the first place, which is to avoid unnecessary copying and reallocation. I don't have the standard at hand, though, so I can't give you a proper answer. – amaurea Oct 29 '12 at 20:44

2 Answers2

12

Looking at the standard, it appears that nothing is required from the move constructor, however as @amaurea says, it would completely defeat the purpose of move semantics if the move constructor were to try and allocate or deallocate memory, so I would expect the capacity to remain the same in all implementations.

23.2.1 General container requirements

Expression

X u(a);
X u = a;

Assertion/note pre-/post-condition

Requires: T is CopyInsertable into X (see below).
post: u == a

The standard only requires that newVec == vec. As capacity is not taken into consideration for std::vector::operator==, newVec need not necessarily have the same capacity as vec.

Peter Alexander
  • 53,344
  • 14
  • 119
  • 168
  • 2
    The first paragraph of your answer contradicts your warning in the last paragraph, so it's hard to tell which assertion you're making more strongly. – seh Jan 11 '13 at 20:12
9

C++11 standard requirements on move constructor for std::vector are (Table 99 — Allocator-aware container requirements):

X(rv)
X u(rv)
  • move construction of allocator shall not exit via an exception
  • post: u shall have the same elements as rv had before this construction; the value of get_allocator() shall be the same as the value of rv.get_allocator() before this construction.
  • complexity: constant

Here is no requirements/guarantee on capacity. But we can make conclusion that constant complexity implicitly denies any reallocations. And I cannot see any other logical reason to change capacity except reallocation. So it shall be the same.

From the other point of view if the moved-from vector is empty, it is perfectly legal to just ignore it and default-construct itself. This would still be O(1), as it doesn't require any per-element constructs. (Thanks to Nicol Bolas for this issue).

Also implemenation possibly could shrink capacity to the size using hint parameter of std::allocator::allocate function:

pointer allocate(size_type, allocator<void>::const_pointer hint = 0);

The use of hint is unspecified, but intended as an aid to locality if an implementation so desires. So some sofisticated solution possibly could pass vector storage pointer as hint and use realloc on it to shrink capacity.

Conclusion: looks like standard doesn't guarantee capacity preserving on moving std::vector, storage potentially could be shrinked.

Community
  • 1
  • 1
Rost
  • 8,779
  • 28
  • 50
  • 5
    "*But we can make conclusion that constant complexity implicitly denies any reallocations.*" +1 – ildjarn Oct 29 '12 at 21:12
  • 3
    Seems like an implementation could just reduce the capacity to the size and still satisfy all the legal requirements, though it would be a pointless waste. – aschepler Oct 29 '12 at 21:14
  • I could see a reasonable implementation doing a `realloc` to shrink the `vector` down so that `size() == capacity()`. Constant complexity does not preclude this. – Peter Alexander Oct 29 '12 at 21:14
  • @PeterAlexander : How could `std::allocator<>` make use of `realloc` with its current interface? – ildjarn Oct 29 '12 at 21:15
  • @ildjarn: In theory, a template specialization which happens to know that its allocator used `malloc` internally could just call `realloc` on the pointer. – aschepler Oct 29 '12 at 21:17
  • @ildjarn: It doesn't have to. There's a high level rule in the standard that allows the implementation to do any optimisation it sees fit as long as the observable behaviour is the same. Also, what aschepler said :-P – Peter Alexander Oct 29 '12 at 21:17
  • 2
    @aschepler: But what part of the `std::allocator<>` interface could use `realloc` under the covers? – Mooing Duck Oct 29 '12 at 21:18
  • But initially, I was thinking of a weird implementation that didn't even do any `realloc` or similar: just change the vector capacity for no good reason. The memory is still allocated, but it won't ever be used. – aschepler Oct 29 '12 at 21:19
  • A very clever implementation could even do optimisations on the whole vector and allocate everything on the stack (if the situation allows). I don't think there's anything that disallows that in certain situations. – Peter Alexander Oct 29 '12 at 21:21
  • @PeterAlexander: That's known as Small Buffer Optimization, and Dinkumware/Microsoft's `std::string` does it. – Mooing Duck Oct 29 '12 at 21:27
  • @PeterAlexander : You're saying that `std::allocator` can do that? The standard requires that the default allocator for `std::vector` is `std::allocator`, no specializations, no customization... – ildjarn Oct 29 '12 at 21:28
  • 3
    @Rost: The concern here is that, since `vec` is empty, it is perfectly legal for `newVec` to just ignore the empty moved-from object and default-construct itself. This would still be O(1), as it doesn't require any per-element constructs. – Nicol Bolas Oct 29 '12 at 21:31
  • @MooingDuck Don't think such trick is applicable here, how can you move automatic storage object in constant time? You have to move it by elements which is linear or at least amortized const complexity. – Rost Oct 29 '12 at 21:32
  • @ildjarn: I'm repeating myself here, but the implementation can do *whatever it wants* as long as the observable behaviour is the same. – Peter Alexander Oct 29 '12 at 21:34
  • @Nicol Bolas Good point, looks like it's not denied by standard. – Rost Oct 29 '12 at 21:36
  • @PeterAlexander : Allocating on the stack would _not_ have the same observable behavior. – ildjarn Oct 29 '12 at 21:42
  • @Rost: Moving automatic storage is _always_ constant time, since it has a small fixed upper limit. Ildjarn is correct that this doesn't apply to `vector`s that contain non-POD types. `string` does this because it requires the contained type to be POD. – Mooing Duck Oct 29 '12 at 21:57
  • @PeterAlexander Stack and other dirty tricks aren't applicable here, default allocator is required to use `::operator new(std::size_t)` – Rost Oct 29 '12 at 21:59
  • @Mooing Duck Really? What about moving/swapping `std::array`? It's not constant but linear time. – Rost Oct 29 '12 at 22:04
  • @Rost: You're right, I hadn't considered types whos stack size depends on `N`. Tuples have the same issue. – Mooing Duck Oct 29 '12 at 22:07
  • @Rost: I'll repeat for the third time: implementation can do **whatever it wants** as long as the observable behaviour is the same. – Peter Alexander Oct 29 '12 at 22:10
  • 2
    @Peter Alexander Ooh, finally I see it. But, wait! Allocating on stack and via `::operator new(size_t)` is not the same observable behavior! – Rost Oct 29 '12 at 22:21
  • @Rost: The observable behaviour of `new` is just that it creates an object. As far as the standard is concerned, there is no stack or heap or `malloc`. – Peter Alexander Oct 29 '12 at 22:52