19

Possible Duplicate:
std::vector resize downward

If I resize() an std::vector to some size smaller than its current size, is it possible that the vector will ever allocate new memory?

This is important to me for performance reasons.

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
Alex Flint
  • 6,040
  • 8
  • 41
  • 80

5 Answers5

16

No, resizeing to a smaller size will never reallocate.

In case the container shrinks, all iterators, pointers and references to elements that have not been removed remain valid after the resize and refer to the same elements they were referring to before the call.

(From here)

Given that, we can be sure that a reallocation cannot have happened.

Chowlett
  • 45,935
  • 20
  • 116
  • 150
  • 6
    To be clear, this is not a formal guarantee that it will not reallocate. But it's hard to imagine how it could, since it would have to find some way to keep the iterators valid, and every imaginable way to do that is terrible. (And presumably, an implementation would only do that if it made things better, in which case you should be happy that it can make things even better than not reallocating.) – David Schwartz Jan 14 '13 at 14:12
  • I believe that in the case of `vector`, the Standard is quite specific about reallocations. – Puppy Jan 14 '13 at 14:13
  • @DeadMG: You might be right about `vector`, since its iterators are already very constrained. – David Schwartz Jan 14 '13 at 14:14
  • @DavidSchwartz - fair point. The precise laws of C++ always catch me out. I rather suspect DeadMG is correct, though, which is encouraging. – Chowlett Jan 14 '13 at 14:21
  • 1
    @DavidSchwartz: for the iterators, it's rather easy, however for the pointers and references, the items just cannot move in memory. – Matthieu M. Jan 14 '13 at 14:30
  • @MatthieuM.: That's sufficient to convince me that a vector cannot reallocate on a shrink. However, that argument wouldn't apply to other containers, since they can reallocate without invalidating pointers and references. – David Schwartz Jan 14 '13 at 14:31
  • Other containers are irrelevant. The question clearly specifies `vector`- that's the start and the end of it. "Reallocate" doesn't even make sense in the context of any other container. – Puppy Jan 14 '13 at 16:20
  • `resize` can reduce the number of elements in use, it generally does not effect container size unless growing beyond the current allocated memory. Starting with C++11 `std::vector::shrink_to_fit` will reduce excessive unused memory allocation above what is needed for the current number of elements. I do not know the specific allocation behavior used to achieve this allocation shrink. Because the standard does *not* require the allocation to shrink exactly to size `shrink_to_fit` may do nothing. I would assume it uses the implementation's common vector allocations.(ie steps of powers of 2) – Max Power Feb 27 '22 at 17:32
  • On my implementation of g++ 10.2 for amd_64 and Linux(5.10) (stdlibc++10) `std::vector::shrink_to_fit` reduces to an exact fit, and myvec.reserve() shows an exact fit (10 if you `.reserve(10)` rather than rounding up to 16). `push_back` 6 elements then `myvec.shrink_to_fit()` results in `myvec.size()` being 6 and `myvec.capacity()` being 6 then `push_back()` a 7th element and `myvec.capacity()` becomes 12. – Max Power Feb 27 '22 at 19:11
7

resize() when reducing only changes the logical size. Others have already answered this, so I am adding nothing here. The purpose of this is to optimise for speed, as it does not need to reallocate or move any data.

However when you want to optimise for memory usage, C++11 has introduced a further function shrink_to_fit() that you may call after your resize() (or even at any other time) which will actually ensure you don't pay for any memory you don't want.

CashCow
  • 30,981
  • 5
  • 61
  • 92
  • +1 for mentioning `shrink_to_fit`. But strictly seen, this is only a recommendation. The implementation is not required to shrink the vector even for this function (though it would indeed be strange if it didn't). – Christian Rau Jan 14 '13 at 15:14
2

No. The vector will never, ever shrink it's memory, except in a few quite specific conditions. Remember that when the vector resizes, iterators are invalidated, so it cannot go around doing this behind your back- it's an observable change, and the Standard specifies exactly when this may or may not happen.

Puppy
  • 144,682
  • 38
  • 256
  • 465
1

No.

Vector uses two values: size and capacity. The size is the actual number of elements stored in the vector, while the capacity reffers to the allocated reserved space in memory. The performance increase comes from allocating more space than is needed.

Only when the request for resize which will result in a capacity greater than the current one is performed, will the re-allocation take place. Also, if you try to insert a lot of elements in the middle of the vector, it will impact on the algorithm performance since all elements after the inserted ones need to be moved (sometimes, this can trigger reallocation, if you exceed capacity of the vector).

You can use the reserve member function to further increase speed: the reserve member function will make sure that the capacity is set to a specific value.

You can read more about std::vector on page 148 - in the book The C++ Standard Library: A Tutorial and Reference.

tmaric
  • 5,347
  • 4
  • 42
  • 75
0

First you have to measure what you want to optimize, performance alone is not sufficient, what do you mean ? UI reactivity ? that need a typical user action for which you measure time. Heavy algorithm ? and so on ... Then you have to find where is the bottleneck, may be memory, disk access, etc, and at the end may be vector::resize, but only at the end ! And the way you ask your question, I bet my $ that vector::resize will not be the bottleneck.

Be confident the way STL is designed, check your code before modifying STL behavior ;-)

Jean Davy
  • 2,062
  • 1
  • 19
  • 24
  • Lower memory use, presumably. That is also one measure of "performance". – CashCow Jan 14 '13 at 16:30
  • @CashCow I don't agree, you may easily imagine scenarios where memory foot print is as low as possible and user responsiveness is bad, very often, not say always, "performance" is multifactor, as you increase something you drecrease another one, so as you don't define precisely, with a measure, what is "performance" you can't work on it. You may waste many days while optimizing for a scenario then discover later, preferabily through a customer critical project, that your vector::resize optimization has very poor side effect on another scenario ... – Jean Davy Jan 16 '13 at 10:16