Here is a simple code:

#include <iostream> #include <vector> using namespace std; int main(){ vector<int> v(5); // в запасе есть 5 элементов cout << v.capacity() << endl; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); cout << v.capacity() << endl; // почему capacity самостоятельно увеличилась до 20? return 0; }

result:

enter image description here

Why the capacity (capacity) independently increased to 20, I expected it to be 6

    3 answers 3

    You placed in the container 6 items. The capacity building strategy of a vector is rather complicated.

    One of the strategies - 2 ^ n - to increase the capacity of the container in powers of two.

    The specific strategy depends on the implementation .

    The purpose of this behavior is to reduce the number of operations for the redistribution of memory, as they are very expensive in time.

    • what for. I can reserve memory myself. but thanks for the reply - perfect
    • four
      @perfect, you can, but many don't. Moreover, requiring the user to constantly monitor memory is not the path of abstractions to which C ++ aspires. Therefore, you should never hope that capacity will return the result known to you. - ixSci

    Here you are already well explained how . Let me say a few words about why .

    The fact is that the increase in capacity is an expensive operation. At the core of std::vector is an ordinary array, which in principle cannot be expanded. * So, capacity just shows the size of this array.

    How does the capacity increase? Very simple: a new array is allocated, all elements of the current one are copied there, the old array is destroyed. Yes, this is a rather expensive operation, it can cause copying / moving constructors of array elements **. Therefore, it is advisable to do it as rarely as possible, its cost is O(n) , where n is the current length of the array.

    Suppose we do not know the size of the necessary data in advance, and put it into std::vector dynamically, using push_back . If at each step we make a copy, when we reach the size N we have to do 1 copy at the 2nd step, 2 at the 3rd, 3 at the 4th, ..., N-1 at the N . The total number of copies is N*(N-1)/2 = O(N^2) . For an array size of 1000 items, this is about a million copies!

    Therefore, strategies were invented to reduce the number of copies. A popular strategy is to increase the capacity in powers of two. Let's look at the asymptotics for this. Let the final size of the array N , k be a power of two such that 2^k <= N < 2^(k+1) . We are copying now not every time, but less and less: after the 1st step (1 element), after the second (2 elements), after the 4th (4 elements), after the 8th (8 elements) and etc. Total 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 < 2*N copies. Thus, the number of copies remains O(N) (due to less optimal memory consumption).

    * No, realloc also not an option, the memory is copied into a new piece in the same way, it is just hidden from us. Plus constructors / destructors are not executed.

    ** If the class has a relocating constructor declared as noexcept , then it will be called, otherwise copying. Thanks @gbg for the hint.

    • 2
      To clarify, the displacement constructor will only be called if it is described as noexcept stackoverflow.com/questions/28166001/… - gbg
    • 2
      And yet realloc does not always copy, especially for really large arrays (at least in Linux, remap is done for them). I would also add that the popular strategy of powers of two always requires the allocation of a new section, i.e. never the amount of previously selected areas is equal to the required new size (imho in apple choose a new size 1.6 from the old one (I sometimes use 3/2 + 1)) - avp
    • @gbg: Wow, even so? Did not know. I will add to the answer. - VladD
    • @avp: Hm, what is remap ? (I explained on powers of two because there are the simplest calculations. You essentially have the same degree, but not two, but 1.5.) - VladD
    • 3
      @VladD mremap(2) - D-side

    Capacity (capacity) is the number of elements for which a fragment of memory is reserved. The vector itself is engaged in increasing memory.
    There is a misconception that the redistribution of memory occurs ONLY when adding a new element that exceeds the current capacity. This is not the case, as @gbg noted, each compiler has its own distribution strategy and the vector acts according to this strategy.

    For example, if you run your code on the Visual Studio C ++ compiler, then despite the fact that you reserved memory for 5 elements, then after adding the first element to the vector, the capacity increases to 7.

     int main() { vector<int> v(5); // в запасе есть 5 элементов cout << v.capacity() << endl; v.push_back(1); cout << v.capacity() << endl; // здесь емкость увеличивается уже до 7 v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); cout << v.capacity() << endl; // почему capacity самостоятельно увеличилась до 20? return 0; }

    I have the following application output

     5 7 15