Can pop_back() ever reduce the capacity of a vecto

问题:

According to the C++ standard, is std::vector<T>::pop_back() ever allowed to reduce the capacity of the vector?

I am asking because I would like to have a guarantee, that the following code will not throw an out of memory exception:

my_vec.pop_back();
if (...)
    my_vec.push_back(...);

Assume that my_vec is an std::vector<int>.

I guess there are three possibilities:

1. Yes, this can happen according to both C++03 and C++11.

2. No, C++11 prohibits this (but C++03 does not).

3. No, both C++03 and C++11 prohibits this.

Yes, my question is related to Does std::vector.pop_back() change vector's capacity?, but my question is specifically about what the standard guarantees.

Note also that the accepted answer in Does std::vector.pop_back() change vector's capacity? is mostly about how to reduce the capacity of a vector, not about when it is guaranteed not to happen, and offers no evidence for its claim about pop_back().

回答1:

According to http://en.cppreference.com/w/cpp/container/vector/pop_back

No iterators or references except for back() and end() are invalidated.

Therefore it may not reallocate. There is no C++11 tag on that page, which implies this is also true in 03. I will dig up the section references and edit them in for completeness.

Edit: Even better: From C++03: [lib.container.requirements] (23.1), paragraph 10:

no erase(), pop_back() or pop_front() function throws an exception.

Same wording at 23.2.1/10 in N3337 (~C++11).

回答2:

No. The only way to shrink a vector's capacity is the swap trick, as shown here. And also the C++11 way I mention bellow.

Also, as the ref says:

Removes the last element in the vector,
effectively reducing the container size by one.

In other words, it changes the size of the vector and not its capacity.

Take a look at the iterator validity:

The end iterator and any iterator, pointer and reference
referring to the removed element are invalidated.
Iterators, pointers and references referring to other
elements that have not been removed are guaranteed to keep
referring to the same elements they were referring to before the call.

In C++11 you could use std::vector<>::shrink_to_fit() in order to change the capacity (for more see the 1st link). (tnx Psyduck). Interesting comments below the answer, but this question is not about the above method, so if interested, read the comments.

Notice that even this method is not guaranteed to reduce the capacity, as the ref says:

Requests the container to reduce its capacity to fit its size.

The request is non-binding, and the container implementation is free to optimize otherwise >and leave the vector with a capacity greater than its size.

This may cause a reallocation, but has no effect on the vector size and cannot alter its >elements.

It would be too strange that this function is not guaranteed to reduce capacity and pop_back does, while the ref of the second does not mentions anything relevant.

The way I see it, since the ref does not mention capacity, this means that it's not needed to, which means, that capacity remains the same.

An interesting example is this:

#include <iostream>
#include <vector>

int main() {
  const int N = 1000000;

  std::vector<int> v1;
  v1.reserve(N);
  for (int i = 0; i < N; ++i) {
    v1.push_back(i);
  }

  std::cout << v1.capacity() << " and size = " << v1.size() << std::endl;

  for (int i = 0; i < N - 2; ++i) {
    v1.pop_back();
  }

  std::cout << v1.capacity() << " and size = " << v1.size() << std::endl;

  return 0;
}

Output:

1000000 and size = 1000000
1000000 and size = 2

where capacity is clearly not reduced.

[EDIT]

Another relevant question, which could also be flagged as a duplicate has some good answers. Here are some interesting ones:

1)

Go look at Scott Meyers Effective STL item 17. (some ref that the OP looks) Basically you can't directly reduce the storage size of a std::vector. The "trick" is to > create a new container of the right size, copy the data and swap that with the current container.

2)

No, you cannot reduce the capacity of a vector without copying.

3)

I'm not saying that GCC couldn't have some method for doing what you want without a copy, > but it would be tricky to implement (I think) because vectors need to use an Allocator object to allocate and deallocate memory, and the interface for an Allocator doesn't include a reallocate() method. I don't think it would be impossible to do, but it might be tricky.

I suggest reading the link for more.

[EDIT.2]

This question also supports that:

Q: Can pop_back() ever reduce the capacity?

A: NO.

When you can't rely on the appropriate methods for reducing capacity (in terms of what you read in the standard), you can't expect pop_back() to do something like that.

回答3:

The comments are not really addressing it. Clearly, if std::vector is prohibited to use anything except std::allocator, and if std::allocator is prohibited to be extended with additional methods, then resizing with same base address is impossible, which makes it impossible to decrease capacity because iterators would be invalidated.

Closest info I could find about reallocation was a stackoverflow comment on Why is there no reallocation functionality in C++ allocators? saying

"There is nothing stopping std::vector from doing that in some cases (e.g., it knows its using the standard allocator). The standard library is allowed to use knowledge of the underlying system. – KeithB Jun 23 '10 at 21:39" (no references mentioned, though)

There have been submitted ideas for adding realloc to std::allocator, but they have both been rejected:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html

The papers don't explicitly state that std::allocator is prohibited to extend std::allocator, though - they only state that it doesn't need to. They also don't explicitly state that std::vector is prohibited to use API calls to the underlying system... So no real info there either.