When should we use reserve() of vector?

问题:

I always use resize() because I cannot use reserve as it gives error: vector subscript out of range. As I've read info about the differences of resize() and reserve(), I saw things like reserve() sets max. number of elements could be allocated but resize() is currently what we have. In my code I know max. number of elements but reserve() doesn't give me anything useful. So, how can I make use of reserve()?

回答1:

A vector has a capacity (as returned by capacity() and a size (as returned by size(). The first states how many elements a vector can hold, the second how many he does currently hold.

resize changes the size, reserve only changes the capacity.

See also the resize and reserve documentation.

As for the use cases: Let's say you know beforehand how many elements you want to put into your vector, but you don't want to initialize them - that's the use case for reserve. Let's say your vector was empty before; then, directly after reserve(), before doing any insert or push_back, you can, of course, not directly access as many elements as you reserved space for - that would trigger the mentioned error (subscript out of range) - since the elements you are trying to access are not yet initialized; the size is still 0. So the vector is still empty; but if you choose the reserved capacity in such a way that it's higher or equal to the maximum size your vector will get, you are avoiding expensive reallocations; and at the same time you will also avoid the (in some cases expensive) initialization of each vector element that resize would do.

With resize, on the other hand, you say: Make the vector hold as many elements as I gave as an argument; initialize those whose indices are exceeding the old size, or remove the ones exceeding the given new size.

Note that reserve will never affect the elements currently in the vector (except their storage location if reallocation is needed - but not their values or their number)! Meaning that if the size of a vector is currently greater than what you pass to a call to the reserve function on that same vector, reserve will just do nothing.

See also the answer to this question: Choice between vector::resize() and vector::reserve()

回答2:

reserve() is a performance optimization for using std::vector.

A typical std::vector implementation would reserve some memory on the first push_back(), for example 4 elements. When the 5th element gets pushed, the vector has to be resized: new memory has to be allocated (usually the size is doubled), the contents of the vector have to be copied to the new location, and the old memory has to be deleted.

This becomes an expensive operation when the vector holds a lot of elements. For example when you push_back() the 2^24+1th element, 16Million elements get copied just to add one element.

If you know the number of elements in advance you can reserve() the number of elements you are planning to push_back(). In this case expensive copy operations are not necessary because the memory is already reserved for the amount needed.

resize() in contrast changes the number of elements in the vector.

If no elements are added and you use resize(20), 20 elements will now be accessable. Also the amount of memory allocated will increase to an implementation-dependent value. If 50 elements are added and you use resize(20), the last 30 elements will be removed from the vector and not be accessable any more. This doesn't necessarily change the memory allocated but this may also be implementation-dependent.

回答3:

resize(n) allocates the memory for n objects and default-initializes them.

reserve() allocates the memory but does not initialize. Hence, reserve won't change the value returned by size(), but it will change the result of capacity().

回答4:

Edited after underscore_d's comment.

Description how functions implemented in VS2015

VS2015 CTP6

This error dialog exist only in the DEBUG mode, when #if _ITERATOR_DEBUG_LEVEL == 2 is defined. In the RELEASE mode we don't have any problems. We get a current value by return (*(this->_Myfirst() + _Pos), so size value isn't needed:

    reference operator[](size_type _Pos)
    {   // subscript mutable sequence
    #if _ITERATOR_DEBUG_LEVEL == 2
    if (size() <= _Pos)
        {   // report error
        _DEBUG_ERROR("vector subscript out of range");
        _SCL_SECURE_OUT_OF_RANGE;
        }

    #elif _ITERATOR_DEBUG_LEVEL == 1
    _SCL_SECURE_VALIDATE_RANGE(_Pos < size());
    #endif /* _ITERATOR_DEBUG_LEVEL */

    return (*(this->_Myfirst() + _Pos));
    }

If we see in the vector's source code, we can find, that a difference between resize and reserve is only in the changing of the value of this->_Mylast() in the func resize().

reserve() calls _Reallocate.

resize() calls _Reserve, that calls _Reallocate and then resize() also changes the value of this->_Mylast(): this->_Mylast() += _Newsize - size(); that is used in the size calculation(see last func)

    void resize(size_type _Newsize)
    {   // determine new length, padding as needed
    if (_Newsize < size())
        _Pop_back_n(size() - _Newsize);
    else if (size() < _Newsize)
        {   // pad as needed
        _Reserve(_Newsize - size());
        _TRY_BEGIN
        _Uninitialized_default_fill_n(this->_Mylast(), _Newsize - size(),
            this->_Getal());
        _CATCH_ALL
        _Tidy();
        _RERAISE;
        _CATCH_END
        this->_Mylast() += _Newsize - size();
        }
    }


    void reserve(size_type _Count)
    {   // determine new minimum length of allocated storage
    if (capacity() < _Count)
        {   // something to do, check and reallocate
        if (max_size() < _Count)
            _Xlen();
        _Reallocate(_Count);
        }
    }



    void _Reallocate(size_type _Count)
    {   // move to array of exactly _Count elements
    pointer _Ptr = this->_Getal().allocate(_Count);

    _TRY_BEGIN
    _Umove(this->_Myfirst(), this->_Mylast(), _Ptr);
    _CATCH_ALL
    this->_Getal().deallocate(_Ptr, _Count);
    _RERAISE;
    _CATCH_END

    size_type _Size = size();
    if (this->_Myfirst() != pointer())
        {   // destroy and deallocate old array
        _Destroy(this->_Myfirst(), this->_Mylast());
        this->_Getal().deallocate(this->_Myfirst(),
            this->_Myend() - this->_Myfirst());
        }

    this->_Orphan_all();
    this->_Myend() = _Ptr + _Count;
    this->_Mylast() = _Ptr + _Size;
    this->_Myfirst() = _Ptr;
    }

    void _Reserve(size_type _Count)
    {   // ensure room for _Count new elements, grow exponentially
    if (_Unused_capacity() < _Count)
        {   // need more room, try to get it
        if (max_size() - size() < _Count)
            _Xlen();
        _Reallocate(_Grow_to(size() + _Count));
        }
    }

    size_type size() const _NOEXCEPT
    {   // return length of sequence
    return (this->_Mylast() - this->_Myfirst());
    }

Problems

But some problems exist with reserve:

1. end() will be equal to begin()

23.2.1 General container requirements

5:

end() returns an iterator which is the past-the-end value for the container.

    iterator end() _NOEXCEPT
    {   // return iterator for end of mutable sequence
    return (iterator(this->_Mylast(), &this->_Get_data()));
    }

i.e. _Mylast() will be equal _Myfirst()

2. at() will generate an out_of_range exception.

23.2.3 Sequence containers

17:

The member function at() provides bounds-checked access to container elements. at() throws out_of_range if n >= a.size().

3. in the VisualStudio debugger we can see vector values, when size isn't 0

with resize:

with reserve and manually setted #define _ITERATOR_DEBUG_LEVEL 0: