resize() and reserve() of std::vector

[t im]

In most cases, resize() changes the size of a vector while reserve() changes capacity of a vector.
My question is about reserve() function.
First look at the code below:

std::vector<int> v{1,2}; // size = 2, capacity = 2;
v.reserve(8); // size = 2, capacity = 8;
v.resize(8); // size = 8, capacity = 8; 

After the reserve() is executed, can the space after the second element of vector be allocated? If not, is the space used after reserve() is executed the same with that after resize() is executed?

[jonnin]

1) yes, after reserve, you can use push-back (as an example) to turn reserved space into actual used locations.

2) not sure because of your wording. But resize will use the reserved space, and if resize needed more space than capacity, it will also reallocate enough to get the job done.

because of the above, you should just use resize without reserve in most scenarios where you would resize it; there isnt any point in reserving first since either way is going to trigger a reallocation. I suppose an exception would be if you need to resize multiple times and reserved one time a lot of space up front, but grew the actual size slowly by hand (instead of using push back).

[George P]

After the reserve() is executed, can the space after the second element of vector be allocated?

Dynamic/heap memory is pre-allocated with reserve(), the memory is "tagged" as unused when getting the size() (number of currently used elements) of the vector.

Memory is pre-allocated either on creation or via reserve(), the capacity of a vector, so if more data elements are added to the vector there is no immediate need to allocate an entire new contiguous block of heap memory, copy the elements from the old block to the new block, and then deallocate the old memory. That is a large performance hit if it has to be done every time data is added to the vector. A serious drawback to manual memory management, especially with regular arrays done with pointers.

resize() OTOH is used to change the number of elements the vector is holding, its size(). size() changes the actual content of the container by adding or erasing elements from it.

The vector's capacity is unchanged unless the new size is greater than the vector's current capacity. That forces the vector to redo the memory allocation to add the new elements. Performance hit.

Adding elements to a container repeatedly makes a a vector not a great choice as a container since dynamic memory reallocation is an expensive operation. For that a std::list might be better. A list's elements might not be in a contiguous memory block.

[Peter87]

George P wrote:

Adding elements to a container repeatedly makes a a vector not a great choice as a container since dynamic memory reallocation is an expensive operation. For that a std::list might be better.

Adding elements to the end of a std::vector is relatively efficient.

Adding 10 ints (std::vector 1.8 times faster)
https://quick-bench.com/q/kTvBEoz__I9oytClwshDo1hks_Q

Adding 100 ints (std::vector 9.8 times faster)
https://quick-bench.com/q/1_n31-X2JUin3g0SGgbrCu6MPX8

Adding 1000 ints (std::vector 27 times faster)
https://quick-bench.com/q/LvOsRF2Jv5IukcEjrOI0D53r40Q

Adding 1000 std::string "short" (std::vector 1.8 times faster)
https://quick-bench.com/q/1k_v2Pb1_IoSHpGiBXrR63RR0Ik

Adding 1000 std::string "a much longer string this time" (std::vector 1.1 times faster)
https://quick-bench.com/q/StCGlxWlUy38VFyQD5WxKrlyqEo

Adding 1000 std::array<int, 100> (std::list 3.8 times faster)
https://quick-bench.com/q/v9pvbQTThjauw7ex9VAzoT2TaIY

I don't claim this to be very scientific (perhaps I should have used DoNotOptimize inside the inner loop?) but it shows that adding elements to the end of a std::vector is not "slow" and often faster than doing the same with std::list. The exception seems to be when the elements are costly to move but in that case you might want to consider a vector of (smart) pointers.

std::vector<std::unique_ptr<std::array<int, 100>>> vs. std::list<std::array<int, 100>> (std::vector 1.1 times faster)
https://quick-bench.com/q/TLs8uW1zAAEuSar_eipid-_dGKY

If you know how many elements you're going to add you can use reserve which will make std::vector win all the time.

If you are using a std::vector for a long time, constantly adding and removing elements, you will typically get a few reallocations in the beginning but almost none later on when the capacity is big enough for your needs.

Adding elements is usually not the only operation that matters. std::vector is more efficient to loop though, etc. so it's often a good choice for a lot of situations. I can't remember the last time I used std::list to be honest.

C++ Core Guidelines - Prefer using STL vector by default unless you have a reason to use a different container
https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#slcon2-prefer-using-stl-vector-by-default-unless-you-have-a-reason-to-use-a-different-container

[t im]

Maybe I do not describe my problem correctly.
After reserve(), can the space after the second element of vector be reallocated to others?
It seems not from my point of view.

[jonnin]

the third space is ready to use.
if you resize to 3 or push back an item, it will use it.
it can't be used by anything other than the vector; the vector owns that block of memory for now.

[JLBorges]

> After reserve(), can the space after the second element of vector be reallocated to others?

With shrink_to_fit we can request the vector to release the extra memory (unused capacity). If the request is honoured, the extra memory would be released for general use.
https://en.cppreference.com/w/cpp/container/vector/shrink_to_fit

#include <iostream>
#include <vector>

template < typename T > struct noisy_allocator : std::allocator<T>
{
    using std_allocator = std::allocator<T> ;
    using value_type = T ;

    [[nodiscard]] T* allocate( std::size_t n )
    {
        auto p = std_allocator::allocate(n) ;
        std::cout << "allocated " << n * sizeof(T) << " bytes at address " << static_cast<const void*>(p) << '\n' ;
        return p ;
    }

     void deallocate( T* p, std::size_t n ) noexcept
     {
        std::cout << "deallocating " << n * sizeof(T) << " bytes at address " << static_cast<const void*>(p) << '\n' ;
        std_allocator::deallocate(p,n) ;
     }
};

template < typename T > using noisy_vector = std::vector< T, noisy_allocator<T> > ;

struct A
{
    A() { std::cout << "construct A at address " << this << '\n' ; }
    A( const A& ) { std::cout << "copy construct A at address " << this << '\n' ; }
    ~A() { std::cout << "destroy A at address " << this << '\n' ; }

    char filler[32] {} ;
};

int main()
{
    std::cout << "1. construct with size of 2\n" ;
    noisy_vector<A> vec(2) ;

    const auto dump = [&vec]
    {
        std::cout << "storage at " << static_cast<const void*>( vec.data() )
                  << "  size: " << vec.size() << "  capacity: " << vec.capacity() << "\n\n\n" ;
    };

    dump() ;

    std::cout << "2. reserve(8)\n" ;
    vec.reserve(8) ;
    dump() ;

    std::cout << "3. resize(8)\n" ;
    vec.resize(8) ;
    dump() ;

    std::cout << "4. pop_back()\n" ;
    vec.pop_back() ;
    dump() ;

    std::cout << "5. emplace_back()\n" ;
    vec.emplace_back() ;
    dump() ;

    std::cout << "6.emplace_back()\n" ;
    vec.emplace_back() ;
    dump() ;

    std::cout << "7. resize(2)\n" ;
    vec.resize(2) ;
    dump() ;

    std::cout << "8. shrink_to_fit()\n" ;
    vec.shrink_to_fit() ;
    dump() ;

    std::cout << "9. destroy vector\n" ;
}

http://coliru.stacked-crooked.com/a/4c5a4fd7a2facba6

[t im]

Thanks for all your helpful reply.
I get it.