How to Downsize Std::Vector

How to downsize std::vector?

Effective STL, by Scott Meyers, Item 17: Use the swap trick to trim excess capacity.

vector<Person>(persons).swap(persons);

After that, persons is "shrunk to fit".

This relies on the fact that vector's copy constructor allocates only as much as memory as needed for the elements being copied.

How to resize an std::vector without loosing the existing data?

You can't do that.

The only way to reduce the value reported by size() is to resize. When resizing reduces the size, the elements outside the new size no longer exist as far as the program is concerned. Any means of accessing them (or reaccessing them, in your case) yields undefined behaviour.

If you want to track the number of elements of an array in use (say, that you are using two elements of a vector with five elements) then create an extra variable to keep track of that. To state the (hopefully) obvious, that variable will need to be kept consistent with the size of the vector (e.g. to avoid tracking that ten elements are being used in a vector with five elements).

If you want to keep the variable with the vector, make both members of a struct/class type. That class can provide member functions or operations that manage both the vector and the number of elements "in use", to ensure consistency.

does std::vector::resize() downward take O(1) time if the element type is a primitive?

There seems to be no guarantee in the standard for this complexity. However, as you point out, there seems to be no reason for greater-than-constant complexity either in that case. Complexity is only guaranteed to be O(n).

I'd be surprised to find a compiler that implemented it as linear for primitive types, but the best way to be sure with your compiler setup would be to make a simple test.

Does std::vector have to resize if the elements it contains grow in size?

The size of a data type in C++ is set at compile time and cannot change. The data type may contain references to other objects, and these other objects can vary in size, but the size of the reference, and thus the data type, is unchanging.

Consider a vector of vectors. The inner vector may contain 0 elements or billions and billions and it will always be the same size. The outer vector only knows that it contains 0 or more vectors and knows nothing about what is contained inside the inner vectors.

You do not have to worry about this.

Reducing the size of a std::vector without a default constructor

In my implementation, it looks like we have (with a few simplifications):

void std::vector<T,A>::resize(size_type __new_size)
{
    if (__new_size > size())
        _M_default_append(__new_size - size());
    else if (__new_size < size())
        _M_erase_at_end(begin() + __new_size);
}

auto std::vector<T,A>::erase(iterator __first, iterator __last) -> iterator
{
    if (__first != __last)
    {
        if (__last != end())
            _GLIBCXX_MOVE3(__last, end(), __first);
        _M_erase_at_end(__first + (end() - __last));
    }
    return __first;
}

where _M_... are private member functions. You really want the effects of _M_erase_at_end. I would guess it would be hard or impossible for a compiler to optimize the _M_default_append call out of v.resize(sz), but relatively easy to notice in v.erase(iter, v.end()) that __last == end() and optimize away the _GLIBCXX_MOVE3 and the + (end() - __last). So erase() could very well be more efficient than resize() here.

I would expect most implementations to be a similar story: a few simple if tests, and then calling some identical method to call destructors for elements at the end.

std::vector resize(0) or clear() - but keep it's capacity

Actually the clear member function keeps the vector capacity unchanged. It only destroys (calls the destructor) each of the vector elements and sets the vector size to 0.

In this situation, at each iteration, I would call clear() to destroy all the vector elements, then call the member function reserve(size) which, in the case where the vector capacity is too small, will increase it to at least size.

Does resize on a std::vector int set the new elements to zero?

Are the elements of foo all zero?

Yes, this can be seen from std::vector::resize documentation which says:

If the current size is less than count,

1. additional default-inserted elements are appended

And from defaultInsertable:

By default, this will call placement-new, as by ::new((void*)p) T() (until C++20)std::construct_at(p) (since C++20) (that is, value-initialize the object pointed to by p). If value-initialization is undesirable, for example, if the object is of non-class type and zeroing out is not needed, it can be avoided by providing a custom Allocator::construct.

(emphasis mine)

Note the T() in the above quoted statement. This means that after the resize foo.resize(10);, elements of foo will contain value 0 as they were value initialized.

Amortizing in std::vector::resize and std::vector::push_back

Is it guaranteed that the capacity of the vector is "doubled" if the reallocation takes place?

No. The complexity of memory reallocation is amortized constant. Whether the capacity of the object is doubled when needed or increased by another factor is implementation dependent.

would the "+1 resize" allocate the memory the same way as it is done for push_back

Yes.

std::vector::resize(size_type sz) appends sz - size() value-initialized elements to the sequence when sz is greater than size(). That is equivalent to:

 insert(end(), sz-size(), <value initialized object>);

std::vector::insert, std::vector::emplace, and std::vector::push_back have the same complexity for memory allocation - amortized constant.

---

Related Topics