Unlocking the Power of Vectors
An Inside Look at Dynamic Arrays in C++

Introduction:
Hello and welcome back to another great LeetCode post! In this post, we will look at the internals of the widely used vector data structure in C++. We'll learn about its dynamic nature and how it manages to enable efficient element access and manipulation.

Understanding how a vector works inside is essential for optimising algorithms and data structures. Let's dive into vectors' core processes and discover the secret behind their dynamic behaviour.

A vector in C++ is implemented as a dynamic array at a high level. It allows you to store and modify elements in a contiguous memory block in a simple and flexible manner. Here's how it works on the inside:

Std::vector allocates space on the heap and stores each of its components in a single contiguous chunk of memory.
1. Dynamic Memory Allocation:
A vector has no memory allocated when it is first declared. The vector internally monitors its capacity and resizes as necessary as you add items using the 'push_back()' function. It starts by allocating a small initial block of memory, typically enough to hold a few elements.

2. The vector holds two important characteristics: capacity and size. Size is the number of elements currently stored in the vector, whereas capacity denotes the most elements the vector can hold before necessitating reallocation.

But what if the dynamic memory it initially allocated is entirely used up?

3. Dynamic Resizing:
When the number of elements exceeds the current capacity, the vector dynamically resizes its memory block to accommodate more elements. It typically doubles the current capacity by allocating a new, larger memory block on the heap. Then, it efficiently copies the existing elements to the new memory location.

Capacity: The C++ function std::vector::capacity() returns the size of allocated storage, expressed in terms of elements. This capacity is not necessarily equal to the size of the vector. It can be equal to or greater than the vector size.

Size: The C++ function std::vector::size() returns the number of elements present in the vector. It is less than or equal to the capacity of the vector.

Below pictorial representation tells how the capacity of a vector changes, dynamically according to the number of insertions made in the vector.

When std::vector’s internal memory completely finishes then it increases the size of its memory. To do that it performs the following steps,

1.) It will allocate a bigger chunk of memory on heap i.e. almost double the size of the previously allocated.
2.) Then it copies all the elements from the old memory location to the new one. Yes, it copies them, so in case our elements are user-defined objects then their copy constructor will be called. Which makes this step quite heavy in terms of speed.
3.) Then after successful copying it deletes the old memory.

4. Efficient Element Access:
One of the vector's key strengths is its efficient element access. Elements are stored contiguously in memory, allowing constant-time random access using the subscript operator [] or the at() function. This property makes vectors ideal for algorithms that require frequent or random element access.

5. Time Complexity:
Resize operation: O(n), but
The amortized time complexity of vector resizing is indeed O(1), not O(n). The resizing operation, which involves doubling the capacity and copying elements, occurs infrequently compared to the number of insertions performed on the vector.
6. Space Complexity:
Obviously it will be O(N) as it requires the memory for the insertion of N elements in the vector.

Conclusion:
Congratulations! You now have an in-depth understanding of how a vector works internally. It manages its capacity dynamically, allowing efficient element access and dynamic resizing. Armed with this knowledge, you can leverage vectors to their full potential and optimize your algorithms and data structures.

Some Takeaways:

vector::resize()  //  read about them from any good website 
vector::capacity()

Keep exploring and experimenting with vectors to uncover more of their hidden capabilities.
Happy coding on LeetCode!