60

This website implies that clearing a vector MAY change the capacity:

http://en.cppreference.com/w/cpp/container/vector/clear

Many implementations will not release allocated memory after a call to clear(), effectively leaving the capacity() of the vector unchanged.

But according to @JamesKanze this is wrong and the standard mandates that clear will not change capacity.

What does the standard say?

Dirk Holsopple
  • 8,731
  • 1
  • 24
  • 37
Neil Kirk
  • 21,327
  • 9
  • 53
  • 91
  • 1
    +1 others may run into this and be confused so good question. – Shafik Yaghmour Aug 27 '13 at 14:16
  • 8
    http://en.cppreference.com/w/cpp/container/vector/clear has been updated to reflect @JamesKanze's answer below. – Nate Kohl Aug 28 '13 at 01:09
  • 2
    I came across the same question and was completely confused because [cplusplus](http://www.cplusplus.com/reference/vector/vector/clear/) makes a strange statement about `clear` : "...and the vector capacity is not guaranteed to change" which I interpreted as: It might change but there is no guarantee that it does change. – 463035818_is_not_an_ai May 04 '16 at 17:47

1 Answers1

66

Depending on the version of the standard you are looking at, clear is defined as the equivalent of erase(begin(), end()), or (in C++11):
"Destroys all elements in a. Invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator."

In neither case is it allowed to modify the capacity; the following code is guaranteed safe by the standard:

std::vector<int> v;
for (int i = 0; i != 5; ++ i) {
    v.push_back(i);
}
assert(v.capacity() >= 5);
v.clear();
assert(v.capacity() >= 5);
v.push_back(10);
v.push_back(11);
std::vector<int>::iterator i = v.begin() + 1;
v.push_back(12);
v.push_back(13);
*i = 42;        //  i must still be valid, because none of 
                //  the push_back would have required an
                //  increase of capacity

(The reason for the change in wording in C++11: the committee didn't want to require MoveAssignable for clear, which would have been the case if it were defined in terms of erase.)

LogicStuff
  • 19,397
  • 6
  • 54
  • 74
James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • 1
    What in C++11 quote states that the capacity will not be changed? – Neil Kirk Aug 27 '13 at 14:18
  • @NeilKirk What says it can be changed? It's part of the observable state, and can only be changes when the standard explicitly says it can change. – James Kanze Aug 27 '13 at 14:22
  • 11
    @NeilKirk: If the capacity were to change, then it would break the guarantee offered by `reserve`: "It is guaranteed that no reallocation takes place during insertions that happen after a call to `reserve()` until the time when an insertion would make the size of the vector greater than the value of `capacity()`" – Mike Seymour Aug 27 '13 at 14:24
  • @MikeSeymour JamesKanze Thanks. Does this mean the website is wrong? – Neil Kirk Aug 27 '13 at 14:25
  • @juanchopanza By the same logic: the absence of any mention of elements being removed means that `insert` can remove elements? The absence of any mention of all of your global variables being `memset` to 0 means that `clear()` can `memset` all of your global variables to 0? There are an infinity of changes in the observable state which could feasibly take place; the standard doesn't explicitly exclude them, but goes on the principle that any observable behavior that is not specified is forbidden. – James Kanze Aug 27 '13 at 14:25
  • 1
    http://en.wikipedia.org/wiki/Everything_which_is_not_forbidden_is_allowed I guess the standard does not follow this! – Neil Kirk Aug 27 '13 at 14:28
  • 1
    Additionaly, the standard also say that `clear` shall not throw an exception. I think it'd be hard to achive that (at least with default allocator) if it were allowed to change the capacity. – jrok Aug 27 '13 at 14:28
  • 1
    @juanchopanza §23.3.6.3,5 states that "It is guaranteed that no reallocation takes place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity()." That includes calls to `clear` and as a corollary implies that clear/erase may not reduce the capacity. – Arne Mertz Aug 27 '13 at 14:29
  • 1
    @JamesKanze I would have assumed that `insert` would make *some* guarantees incompatible with removing elements. But I take your well made point. – juanchopanza Aug 27 '13 at 14:29
  • 2
    @jrok deallocation shall not thrwo either, so changing the capacity to 0 would not harm that requirement. – Arne Mertz Aug 27 '13 at 14:30
  • 2
    @juanchopanza: Of course `clear()` isn't an insertion; but insertions *after* `clear()` are still subject to the guarantee, so `clear()` can't reduce the capacity. – Mike Seymour Aug 27 '13 at 14:43
  • @MikeSeymour of course, I had totally misread that. Thanks for spelling it out. – juanchopanza Aug 27 '13 at 14:46
  • 1
    @JamesKanze: "*the absence of any mention of elements being removed means that insert can remove elements?*" Um, no. The standard says what all of the user-visible effects will be. Clearing globals would be a user-visible effect, so if it is not stated that this can or will happen, then it *cannot*. Removing elements would be a user-visible effect. And so forth. The capacity doesn't change precisely because it doesn't say that it *can be changed*. Therefore *it does not change*. – Nicol Bolas Aug 27 '13 at 14:50
  • @NeilKirk: "*en.wikipedia.org/wiki/… I guess the standard does not follow this!*" No, you have that backwards. If the standard doesn't say that something can or will change, then it does not. – Nicol Bolas Aug 27 '13 at 14:52
  • @NicolBolas yes that is opposite to "Everything which is not forbidden is allowed", ie "everything which is not allowed is forbidden" in the standard – Neil Kirk Aug 27 '13 at 14:53
  • 3
    @NicolBolas That is precisely my point. The standard defines the observable behavior of a function, and that function cannot have any additional observable behavior. We take this for granted in a lot of cases: `open` will not reformat your disk, although I doubt you'll find a statement to that effect in the description (Posix or other) of `open`. – James Kanze Aug 27 '13 at 15:08
  • @NeilKirk The question is: for whom? The user or the implementation. If the implementation can do anything it wants, provided it is not explicitly forbidden, then the user can't count on anything, and can't do much. – James Kanze Aug 27 '13 at 15:13
  • 3
    @MikeSeymour: By saying "`Of course clear() isn't an insertion; but insertions after clear() are still subject to the guarantee, so clear() can't reduce the capacity.`", does this mean that even copy/move assignment cannot reduce capacity (which I will be very surprised at)? – goodbyeera Mar 08 '14 at 10:18
  • 2
    @MikeSeymour: The standard says reallocation won't happen `"until the time when an insertion would make the size of the vector greater than the value of capacity()."`. Yes, the `insertion` could very well be after a `clear()`, but at that time, the `capacity()` could have already been changed, so a reallocation doesn't break the guarantee. (C++11 differs from C++03 in that the guarantee for non-reallocation upon `insertion` is against `capacity()`, rather than the argument passed in the most recent call to `reserve()`.) – goodbyeera Mar 08 '14 at 11:28
  • 4
    @MikeSeymour: I think the `capacity()` mentioned in the guarantee should be the value of `capacity()` upon the time of the insertion operation, not the the value of `capacity()` right after the `reserve()` call. So if `clear()` is allowed to shrink the capacity, the guarantee won't break. Whether `clear()` is allowed to shrink capacity or not is another question, I'm just saying that the justification you used here is not appropriate. – goodbyeera Mar 08 '14 at 11:42
  • @MikeSeymour: Just found in BS's C++PL 4th, p196, he regards `v.clear();` and `v={};` as something equivalent to `swap(v,vector{});`, though he also regards `s.shrink_to_fit();` equivalent to `swap(s,string(s));` in the same example. However, though not mandatory, `shrink_to_fit()` is allowed to reduce capacity, so it's fair to say that BS implies `clear()` and `move-assign` is allowed to reduce capacity too, otherwise that example will lose its whole point. – goodbyeera Mar 08 '14 at 13:44
  • @goodbyeera: Sorry, I must have missed the "language-lawyer" tag when I originally posted here. I don't have the required level of pedantry to join in, so please ignore my comments. – Mike Seymour Mar 08 '14 at 14:03
  • 5
    @JamesKanze: If we apply the `no additional observable behavior other than specified` rule (which I totally agree) to vector's copy/move assignment, can we come to the conclusion that copy/move assignment isn't allowed to reduce a vector's capacity either? This seems quite unreasonable. What went wrong here? – goodbyeera Mar 08 '14 at 14:45
  • @goodbyeera I'm not sure where you see a problem with `copy` and `move`. With regards to the constructors, there is no object beforehand, so no capacity to change. With regards to assignment, copy assignment cannot reduce capacity. Move assignment is a bit trickier; as the standard is currently written, move assignment _cannot_ reduce the capacity of the vector. (In fact, I don't think it can change the capacity if the size of the right hand vector is less than or equal to the capacity of the left-hand vector, because it cannot reallocate or invalidate iterators. A bug in the standard?) – James Kanze Mar 10 '14 at 12:27
  • 2
    @JamesKanze: Thanks for the reply. I'm confused too. I have asked a separate question regarding vector's copy/move assignment 2 days ago: http://stackoverflow.com/questions/22253355/what-happens-to-the-underlying-storage-upon-vectors-copy-move-assignment No convincing answer so far. It will be great if you could provide your thoughts there. Thanks again. – goodbyeera Mar 10 '14 at 13:12