how c++ vector works

Question

Lets say if I have a vector V, which has 10 elements. If I erase the first element (at index 0) using v.erase(v.begin()) then how STL vector handle this?

Does it create another new vector and copy elements from the old vector to the new vector and deallocate the old one? Or Does it copy each element starting from index 1 and copy the element to index-1 ?

If I need to have a vector of size 100,000 at once and later I don't use that much space, lets say I only need a vector of size 10 then does it automatically reduce the size? ( I don't think so)

I looked online and there are only APIs and tutorials how to use STL library. Is there any good references that I can have an idea of the implementation or complexity of STL library?

Answer 1

Actually, the implementation of vector is visible, since it's a template, so you can look into that for details:

iterator erase(const_iterator _Where)
    {   // erase element at where
    if (_Where._Mycont != this
        || _Where._Myptr < _Myfirst || _Mylast <= _Where._Myptr)
        _DEBUG_ERROR("vector erase iterator outside range");
    _STDEXT unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr);
    _Destroy(_Mylast - 1, _Mylast);
    _Orphan_range(_Where._Myptr, _Mylast);
    --_Mylast;
    return (iterator(_Where._Myptr, this));
    }

Basically, the line

unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr);

does exactly what you thought - copies the following elements over (or moves them in C++11 as bames53 pointed out).

To answer your second question, no, the capacity cannot decrease on its own.

The complexities of the algorithms in std can be found at http://www.cplusplus.com/reference/stl/ and the implementation, as previously stated, is visible.

Answer 2

Does it copy each element starting from index 1 and copy the element to index-1 ?

Yes (though it actually moves them since C++11).

does it automatically reduce the size?

No, reducing the size would typically invalidate iterators to existing elements, and that's only allowed on certain function calls.

I looked online and there are only APIs and tutorials how to use STL library. Is there any good references that I can have an idea of the implementation or complexity of STL library?

You can read the C++ specification which will tell you exactly what's allowed and what isn't in terms of implementation. You can also go look at your actual implementation.

Answer 3

Vector will copy (move in C++11) the elements to the beginning, that's why you should use deque if you would like to insert and erase from the beginning of a collection. If you want to truly resize the vector's internal buffer you can do this:

vector<Type>(v).swap(v);

This will hopefully make a temporary vector with the correct size, then swaps it's internal buffer with the old one, then the temporary one goes out of scope and the large buffer gets deallocated with it.

As others noted, you may use vector::shrink_to_fit() in C++11.

Answer 4

That's one of my (many) objection to C++. Everybody says "use the standard libraries" ... but even when you have the STL source (which is freely available from many different places. Including, in this case, the header file itself!) ... it's basically an incomprehensible nightmare to dig in to and try to understand.

The (C-only) Linux kernel is a paragon of simplicity and clarity in contrast.

But we digress :)

Here's the 10,000-foot answer to your question:

http://www.cplusplus.com/reference/stl/vector/

Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.

But unlike regular arrays, storage in vectors is handled automatically, allowing it to be expanded and contracted as needed.

Vectors are good at:

• Accessing individual elements by their position index (constant time).
• Iterating over the elements in any order (linear time).
• Add and remove elements from its end (constant amortized time).

Compared to arrays, they provide almost the same performance for these tasks, plus they have the ability to be easily resized. Although, they usually consume more memory than arrays when their capacity is handled automatically (this is in order to accommodate extra storage space for future growth).

Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.

...

Reallocations may be a costly operation in terms of performance, since they generally involve the entire storage space used by the vector to be copied to a new location. You can use member function vector::reserve to indicate beforehand a capacity for the vector. This can help optimize storage space and reduce the number of reallocations when many enlargements are planned.

...

Answer 5

I only need a vector of size 10 then does it automatically reduce the size?

No it doesn't automatically shrink.
Traditionally you swap the vector with a new empty one: reduce the capacity of an stl vector

But C++x11 includes a std::vector::shrink_to_fit() which it does it directly