CODEWITHSUNDEEP
c++vector
user3345850
user3345850

Reputation: 151

What happens when we use vector erase or insert

Does it move all elements from the right side of the vector(to 1 position left if erase and move to 1 position right if insert) or is it like a linked list(it creates a new address and makes a new address. Also when I initialise a vector with a string how does it take care of the memory. If it is storing it in a sequence what would happen when we keep doing push_back when it reaches its maximum memory allocation.

Upvotes: 1

Views: 1297

Answers (1)

vsoftco
vsoftco

Reputation: 56547

A std::vector is guaranteed (by the C++ standard) to store the elements in a contiguous memory area. Which means that no, it is not like a linked list, but more like a dynamically allocated array. When you push_back elements after the vector reaches the maximum capacity a reallocation takes place and elements are copied into the new buffer. Same happens when you use insert or erase elements, things are shifted around so those operations are in general O(N) and not O(1) as it is the case for linked lists.

So it looks like std::vector is worse than a std::list. This is not the case though as in many applications read operations are the dominant ones, for which a std::vector is way faster than a std::list due to cache locality and O(1) random access due to the fact that the elements are stored contiguously. Also push_back is O(1) except when the vector performs re-allocation (technically push_pack has amortized O(1) complexity).

Upvotes: 6

Related Questions