Std::Vector Capacity After Copying

std::vector capacity after copying

All you're guaranteed is that:

The vector has enough capacity to store its elements. (Obviously.)
The vector won't get a new capacity until it's current capacity is full.*

So how much extra or little an implementation wants to put is up to the implementation. I think most will make capacity match size, when copying, but it cannot lower capacity. (Because of number 2 above; reallocating while there's enough room is not allowed.)

_{* Mostly. See Charles' comments below.}

why swap (this trick) shrink the capacity of vector?

I love questions that make me re-evaluate what I thought to be true. Thank you!

Firstly, I had thought "capacity" was something that all containers have. Turns out that was my first mistake. It's just for std::vector and std::string (and std::string_view).

Now, looking at the expression you specified:

std::vector<T>(v).swap(v);

On one hand, we've got std::vector<T>(v), which is making a copy of v, and on the other hand we have a swap of v (presumably, an std::vector<T>) with that copy.

Let's look at each step.

Copy Constructor

Because std::vector is a container, it has to fulfill the requirements of a "container". This is where its copy constructor comes from. The copy constructor for std::vector is defined in the container.requirements section in table 64, in the row with the Expression X(a). That row also specifies that the complexity must be linear. It also says that the post-condition of the copy "Ensures: a == X(a)".

To determine what "a == X(a)" means, we look further down in that same table, and see that:

== is an equivalence relation. equal(a.begin(), a.end(), b.begin(), b.end())

If we take all the above together, it gives us a pretty good approximation of what the job of the copy constructor is: Populate an std::vector with equivalent values from another std::vector, in the same order.

But to be pedantic, there's no requirement about how much memory is allocated, or rather, how many times the allocated is called upon, other than enough to satisfy std::vector<T>(v) == v.

That being said, I'd be surprised if any implementer would allocate more than the minimum required. In C++ we like performance, and not paying for what we don't use. So unless there's a really good reason for the capacity to be greater, the capacity of the copied vector will be exactly the number of elements copied to it. Thus, it's implementation specific.

Swap

In the same table, the row with the Expression a.swap(b) refers to "Note A". That note says:

Those entries marked “(Note A)” [...] have constant complexity for [...] standard containers.

Also in container.requirements 21.2.1.9 there's the requirement that swap not invalidate any iterators:

The expression a.swap(b), for containers a and b of a standard container type [...] shall exchange the values of a and b without invoking any move, copy, or swap operations on the individual container elements. [...] Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap. It is unspecified whether an iterator with value a.end() before the swap will have value b.end() after the swap.

This is very interesting and Good Stuff! Nobody likes having iterators invalidated, after all. (Compare with shrink_to_fit, which may invalidate the iterators if it has to reallocate.)

It also shapes our understanding of swap for containers. Since there is no allowed move/copy/swap on elements, and the iterators remain valid, this heavily implies to the implementer that the destination of the swap will take over the memory from the source vector. (Yes, I know it seems obvious, but the standard takes great and wonderful pains to make sure that the obvious is obvious to everyone by spelling everything out.)

As you mentioned, std::vector has a specialization for swap, which also requires that the capacity be swapped. In particular, see "vector" section 21.3.11.3.12, where it says:

Effects: Exchanges the contents and capacity() of *this with that of x.

Which means that the standard guarantees that the capacity of std::vector<T>(v) will be swapped into v, when you do:

std::vector<T>(v).swap(v);

TL;DR The capacity of the swap-destination is mandated to be the same as the source of the swap. However, since the capacity of a copy-constructed std::vector is not explicitly mandated by the standard to be any specific value, it is implementation specific.

does std::vector copy/move elements when re-sizing?

If it needs to relocate, something similar to std::move(xold.begin(), xold.end(), xnew.begin()); will be used. It depends on the value type and the vector usually does its own internal placement new . but it'll move if it can move.

Your move constructor

person(const person &&other) noexcept;

has a flaw though: other should not be const since it must be allowed to change other to steal its resources. In this move constructor

person(person&& other) noexcept : m_name(std::move(other.m_name)) {}

the std::strings own move constructor will do something similar to this:

string(string&& other) noexcept : 
    the_size(other.the_size),
    data_ptr(std::exchange(other.data_ptr, nullptr))
{}

You also need to add a move assignment operator:

person& operator=(person &&other) noexcept;

STL vector reserve() and copy()

As noted in other answers and comments, you should just use vector's built-in functionality for this. But:

When you reserve() elements, the vector will allocate enough space for (at least?) that many elements. The elements do not exist in the vector, but the memory is ready to be used. This will then possibly speed up push_back() because the memory is already allocated.

When you resize() the vector, it will allocate enough space for those elements, but also add them to the vector.

So if you resize a vector to 100, you can access elements 0 - 99, but if you reserve 100 elements, they are not inserted yet, just ready to be used.

What you want is something like this:

vec2.reserve( vec1.size() );
copy(vec1.begin(), vec1.end(), std::back_inserter(vec2));

std::back_inserter is defined in <iterator>

Allocation free std::vector copy when using assignment operator

Standard doesn't guarantee that there would be no allocations. According to the C++11 Standard the effect of b = a; is as if b.assign(a.begin(), a.end()) (with surplus b's elements destroyed, if any) which result is "Replaces elements in b with a copy of [a.begin(), a.end())". Nothing about allocations but with the C++20 Standard (maybe earlier) we have an additional statement: "Invalidates all references, pointers and iterators referring to the elements of b". Which means allocation is possible and the capacity() isn't mentioned anywhere in these guarantees to prevent it in your particular case.

On the other hand, in practice, why would it reallocate the memory if there is enough already?

capacity of vector is 0 when i am inserting it into an un-ordered map

The make_pair will copy construct (6) a new vector, which does not retain the capacity.

You could also instead force the move constructor (7) which does retain capacity by using std::move but that would be overly complex.

_map.insert(std::make_pair(1, std::move(a)));

Instead of reserving capacity I'd suggest you simply reserve the size at the point of constructing the vector.

std::vector<int> a(40);

Does a vector assignment invalidate the `reserve`?

Unfortunately, the standard underspecifies behavior on allocator-aware sequence container assignment, and indeed is strictly speaking inconsistent.

We know (from Table 28 and from 23.2.1p7) that if allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value is true then the allocator is replaced on copy assignment. Further, from Tables 96 and 99 we find that the complexity of copy assignment is linear, and the post-condition on operation a = t is that a == t, i.e. (Table 96) that distance(a.begin(), a.end()) == distance(t.begin(), t.end()) && equal(a.begin(), a.end(), t.begin()). From 23.2.1p7, after copy assignment, if the allocator propagates, then a.get_allocator() == t.get_allocator().

With regard to vector capacity, 23.3.6.3 [vector.capacity] has:

5 - Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. 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().

If we take library DR341 as a guide to reading the Standard:

However, the wording of 23.3.6.3 [vector.capacity]paragraph 5 prevents the capacity of a vector being reduced, following a call to reserve(). This invalidates the idiom, as swap() is thus prevented from reducing the capacity. [...]

DR341 was resolved by adding paragraphs into 23.3.6.3:

void swap(vector<T,Allocator>& x);

7 - Effects: Exchanges the contents and capacity() of *this with that of x.

8 - Complexity: Constant time.

The conclusion is that from the point of view of the Library committee, operations only modify capacity() if mentioned under 23.3.6.3. Copy assignment is not mentioned under 23.3.6.3, and thus does not modify capacity(). (Move assignment has the same issue, especially considering the proposed resolution to Library DR2321.)

Clearly, this is a defect in the Standard, as copy assignment propagating unequal allocators must result in reallocation, contradicting 23.3.6.3p5.

We can expect and hope this defect to be resolved in favour of:

non-reduced capacity() on non-allocator-modifying copy assignment;
unspecified capacity() on allocator-modifying copy assignment;
non-reduced capacity() on non-allocator-propagating move assignment;
source-container capacity() on allocator-propagating move assignment.

However, in the current situation and until this is clarified you would do well not to depend on any particular behavior. Fortunately, there is a simple workaround that is guaranteed not to reduce capacity():

bigVector.assign(littleVector.begin(), littleVector.end());

Std::Vector Capacity After Copying