1

Excuse me for the badly-formatted question, to give context , i'm trying to re-implement vector container and following this quote from the reference:

... vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). Libraries can implement different strategies for growth to balance between memory usage and reallocations...

and this question i understand that most implementations use some sort of little formula N*K where N stands for it's size and K for the growth ratio, the golden ratio used by most implementations is 1.5 according to the answers, however concluding from the reference it seems it gives absolute freedom regarding the growth strategy but doesn't mention where or when this allocation of N*K should happen, in which constructors if there's any or in which member methods, maybe it gives freedom too regarding this aspect, well if that's the case is there a recommended map by which one should guide.

interesting
  • 149
  • 1
  • 10
  • when you perform push_back operation on a vector check if there is still available space to paste 1 element. If not perform reallocation – Alexander Sobetskiy Sep 29 '22 at 10:21
  • 1
    Methods like [`insert`](https://en.cppreference.com/w/cpp/container/vector/insert), [`emplace`](https://en.cppreference.com/w/cpp/container/vector/emplace) and quite a few others mention when the reallocation happens. There's no freedom for implementation here (implementation only chooses how much `capacity()` should grow with each reallocation). – Yksisarvinen Sep 29 '22 at 10:22
  • I want to stress that you musst implement any clever strategy, because otherwise it is not possible to have a asymtotic complexity of O(1) e.g. for insertion. – gerum Sep 29 '22 at 10:23
  • 4
    There is no specific section giving the exact rule, but the iterator invalidation rules only allow reallocation when the vector is full and more space is needed. As an aside, much of the standard has a "holistic" principle, as one little rule can have effects in many other places. And the text tries to avoid repetition in fear of causing contradictions. – BoP Sep 29 '22 at 10:24
  • @BoP +1 for the precise answer. – interesting Sep 29 '22 at 10:35
  • @BoP it would be great and appreciated if you can elaborate in your comment in an answer for future comers. – interesting Sep 29 '22 at 10:38
  • I don't have much to add, that's why I wrote a comment and not an answer. Having done this for a long time, I just "know things" that has been discussed before, but without proper footnotes or links to sources. – BoP Sep 29 '22 at 20:21
  • Also, some of the rules in the C++ standard says "Unless otherwise specifed, blah blah blah". And then you have to read the next 1000 pages to see what might be "otherwise specified", if anything. But you cannot easily quote that. – BoP Sep 29 '22 at 20:24

1 Answers1

1

"when and where" is fairly simple: for any operation that would require .capacity() to grow. Note that .capacity() >= .size(), so things like .resize() are also covered. This is a hard requirement: as BoP noted in the comments, implementations may do this if and only if capacity() must grow.

The rule for this is that std::vector<> uses the std::allocator interface to grow .capacity(). std::allocator does not have an ability to extend existing allocations. To grow a vector, all values are copied to a new allocation. This invalidates the iterators to existing elements (and end() too).

Obviously for all constructors there's no previous size, so there's no way to grow by a certain factor. It's up to the implementor to choose an initial size.

The N*K is a simplification. Rounding up to convenient sizes is certainly possible. (e.g. system page size). Even rounding down might be acceptable, as long as the rounding down is bound by a lower limit (i.e. growing to approximately 2*K is allowed if you never round below 1.5*K)

MSalters
  • 173,980
  • 10
  • 155
  • 350