A dynamic array in C++ is a data structure that allows you to create an array whose size can be changed during runtime. They allow you to store a collection of elements of the same data type while providing the ability to resize the array dynamically during program execution. This is in contrast to a static array, where the size is fixed at compile time. Dynamic arrays are quite useful because they offer flexibility and efficient memory management. The flexibility is achieved by allocation memory on the heap and using pointers to manage the array's memory.

In C++, you can implement a dynamic arrays using pointers and memory allocation functions (such as new and delete[] ) or, preferably, by using the std::vector container from the C++ Standard Library.

Key features of dynamic arrays:

• Dynamic resizing: You can add or remove elements without worrying about the array' initial size.
• Random access: Like static arrays, dynamic arrays allow you to access elements using indices.
• Contiguous memory: Elements are stored in adjacent memory location, providing efficient cache utilization.

Dynamic Array Using Pointers (Manual Memory Management)

Allocate Memory

Use the new operator to allocate memory for the dynamic array. This memory allocation should be done on the heap.

int *numbers = new int[3]; // numbers points to first element of the dynamically allocated array.

Initialize Array Elements

you can initialize the elements of the dynamic array as needed.

for (int i = 0; i < size; i++){
 	numbers[i] = 0;
 }

Access or Modify Elements

You can access and modify elements of the dynamic array just like a regular array using square brackets [].

numbers[0] = 42; // Set the first element to 42
int value = numbers[1]; // Access the second element

Deallocate Memory

It's crucial to deallocate the memory when you are done with the dynamic array to prevent memory leaks. Use the delete[] operator to release the memory.

delete[] numbers;

This step is essential to free up the memory and should be done before the program exists or when you no longer need the dynamic array.

Resizing a Dynamic Array

One of the key features of dynamic arrays is the ability to resize them as needed. However, C++ doesn't have built-in mechanism of resizing an array once it has been allocated. You can however, overcome this challenge by allocating a new array dynamically, copying over the elements, the erasing the old array. When the array becomes too small to accommodate new element, you can create a larger array, copy the existing elements to it, and update the pointer. Here's a basic example of resizing a dynamic array:

int* dynamicArray = new int[5]; // Creating an array of 5 integers

int newSize = 10;
int* newDynamicArray = new int[newSize];

for (int i = 0; i < 5; i++) {
    newDynamicArray[i] = dynamicArray[i]; // Copying elements
}

delete[] dynamicArray; // Deallocating old memory
dynamicArray = newDynamicArray; // Updating the pointer

Complete Example:

 #include <iostream>
 using namespace std;
 
 int main(){
 	int size;
 	int* dynamicArray;
 	
 	cout<< "Enter the size of the dynamic array: ";
 	cin>>size;
 	
 	dynamicArray = new int[size];
 	
 	for(int i = 0; i < size; i++){
 		dynamicArray[i] = 0;
 	}
 	
 	dynamicArray[0] = 7;
 	
 	delete[] dynamicArray;
 	return 0;
 }

Advantages of Dynamic Arrays

1. Dynamic Sizing: You can change the size of the array at runtime accommodating varying amounts of data.
2. Efficiency: Dynamic arrays allow for efficient random access to elements, just like static arrays.
3. Memory Management: You have fine-grained control over memory allocation and deallocation.

Disadvantages of Dynamic Arrays

While dynamic arrays are powerful, they come with some drawbacks:

1. Memory Overhead: Dynamic arrays require extra memory to store their size and capacity, which can be inefficient for small collections.
2. Resizing Overhead: Resizing a dynamic array can be computationally expensive, especially if it needs to be done frequently.
3. Manual Memory Management: You can responsible for managing memory with new and delete, which can lead to memory leaks and segmentation faults if not done correctly.

Time Complexity

The time complexity of dynamic arrays is as follows:

Accessing Elements

Accessing Elements in a dynamic array by their index is an operation with constant time complexity.

Time Complexity: O(1)

This means that regardless of the size of the dynamic array, accessing any element by its index takes roughly the same amount of time.

int value = dynamicArray[2]; // Accessing the third element

Insertion and Deletion at the End

Inserting or deleting an element at the end of a dynamic arrays using pointers also has a constant time complexity on average.

However, in the worst case, when the array needs to be resized, it becomes a linear time operation.

Average Time Complexity: O(1)

Worst-Case Time Complexity:(resizing required) O(n)

// Inserting an element at the end
dynamicArray[size] = element;
size++;

// Deleting an element from the end
size--;

Insertion and Deletion in the Middle

Inserting or deleting an element in the middle of dynamic array implemented with pointers is typically a linear time operation.

Time Complexity: O(n)

This is because you need to shift elements to accommodate the insertion or removal

// Inserting an element at a specific index
for (int i = size; i > index; i--) {
    dynamicArray[i] = dynamicArray[i - 1];
}
dynamicArray[index] = element;
size++;

// Deleting an element from a specific index
for (int i = index; i < size - 1; i++) {
    dynamicArray[i] = dynamicArray[i + 1];
}
size--;

Search

Searching for an element in a dynamic array implemented with pointers requires traversing the array, making it a linear time operation.

Time Complexity: O(n)

You need to examine each element until you find the desired one.

for (int i = 0; i < size; i++) {
    if (dynamicArray[i] == target) {
        // Element found
        break;
    }
}

std::vector

std::vector is a widely-used C++ container that provides dynamic array functionality. It is part of the C++ Standard Library and offers numerous benefits:

1. Dynamic Sizing: std::vector can grow or shrink automatically as you add or remove elements. This makes it suitable for situations where the number of elements is unknown or may change.
2. Random Access: Like regular arrays, you can access elements in a std::vector using indices. This allows for efficient random access.
3. Contiguous Memory: Elements in a std::vector are stored in contiguous locations, making it cache-friendly and efficient for operations like iteration.
4. Automatic Memory Management: You don't need to worry about manual memory allocation or deallocation; std::vector takes care of it for you.
5. Standard Interface: std::vector follows a standard interface that includes functions for adding, removing, and accessing elements. This consistency makes it easy to use and understand.

Using std::vector

Syntax:

vector<T> vector_name;

The type parameter <T> specifies the type of the vector. It can be any primitive data type such as int, char, float, etc.

vector<int> intVector;

vector<string> stringVector;

vector<float> floatVector;

vector<double> doubleVector;

Creating a Vector

std::vector::vector()

• Constructor for creating an empty vector.
• Example: std::vector<int> myVector;
• This created an empty vector called myVector that can hold integers.

#include <vector>

std::vector<int> myVector; // Create an empty vector of integers

or 

#include <vector>
using namespace std;
//...

vector<int> myVector; // no need to prepend std:: any more

// Note For small projects, you can bring the entire namespcae std into the scope by inserting using directivve on to of your .cpp file.

Note:

• Never write a using directive into a header file. This would bloat the entire namespace std into each and every cpp file that includes that header.
• For larger projects, it is better to explicitly qualify every name accordingly.

std::vector::vector(size_type count, const T& value):

• Constructor to create a vector with count copies of value.
• Example: std::vector<int> myVectorWithValues(5, 40);
• This created a vector myVectorWithValues containing 5 copies of the integer 42.

Different ways to Initialize the vector

Method 1:

// Initializer list
vector<int> vector1 = {1, 2, 3, 4, 5};

// Uniform initialization
vector<int> vector2 {1, 2, 3, 4, 5};

Method 2:

Accessing Elements

std::vector::at(size_type pos):

• Accesses the element at the specified position with bounds checking.
• Example: int thirdElement = myVector.at(2).
• It retrieves the element at index 2 in myVectorand assigns it to thirdElement.

std::vector::operator[]:

• Accesses the element at the specified position without bounds checking.
• Example: int secondElement = myVector[1];
• It directly accesses the element at index 1 in myVector and assigns it to secondElement.

int value = myVector[0]; // Access the first element

More Functions:

std::vector::empty():

• Returns true if the vector is empty, false otherwise.
• Example: bool isEmpty = myVector.empty();
• It checks whether the vector myVector is empty and stores the result in the isEmpty variable.

std::vector::push_back(const T& value):

• Adds an element with value to the end of the vector.
• Example: myVector.push_back(10);
• This appends the integer 10 to the end of the myVector container.

std::vector::pop_back():

• Removes the last element from the vector.
• Example: myVector.pop_back();
• This function removes the last element from the myVector container. After calling pop_back(), the size of the vector decreases by 1, and the last element is removed. It doesn't return the removed element.

std::vector::size():

• Returns the number of elements in the vector.
• Example: int size = myVector.size();
• It retrieves the number of elements in the myVector container and assigns it to the size variable.

std::vector::front():

• Returns a reference to the first element in the vector.
• Example: int first = myVector.front();
• It retrieves a reference to the first element in myVector and assigns it to the first variable.

std::vector::back():

• Returns a reference to the last element in the vector.
• Example: int last = myVector.back();
• It retrieves a reference to the last element in myVector and assigns it to the last variable.

std::vector::insert(iterator pos, const T& value):

• Insert an element with value at the specified position.
• Example: myVector.insert(myVector.begin() + 1, 99);
• This inserts the value 99 at the position just after the first element in myVector.

std::vector::erase(iterator pos):

• Removes the element at the specified position.
• Example: myVector.erase(myVector.begin() + 2);
• This removes the element at the position 2 in myVector.

std::vector::clear()

• Removes all elements from the vector, leaving it empty.
• Example: myVector.clear();
• This clears all elements from the myVector container, making it empty.

std::vector::resize(size_type count):

• Changes the size of the vector. If it increases, new elements are initialized with their default value.
• Example: myVector.resize(5);
• This resized myVector to have 5 elements. If it had fewer than 5, the new elements are initialized to their default value (0 for integers).

std::vector::resize(size_type count, const T& value):

• Changes the size of the vector. If it increases, new elements are initialized with value.
• Example: myVector.resize(8, 40);
• This resized myVector to have 8 elements. If it had fewer than 8, the new elements are initialized to the value 40.

std::vector::capacity():

• Returns the current storage capacity of the vector.
• Example: int cap = myVector.capacity();
• This function returns the number of elements that the vector can hold without needing to allocate more memory. It provides insight into how much memory has been allocated for the vector, which can be useful for performance optimization. The capacity is often greater than or equal to the vector's size. If the vector's size exceeds its capacity and new elements are added, the vector may need to reallocate memory, which can be an expensive operation.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> myVector;

    // Display the initial capacity
    std::cout << "Initial Capacity: " << myVector.capacity() << std::endl;

    // Add elements to the vector
    for (int i = 0; i < 10; ++i) {
        myVector.push_back(i);
    }

    // Display the updated capacity
    std::cout << "Updated Capacity: " << myVector.capacity() << std::endl;

    return 0;
}

// Output
Initial Capacity: 0
Updated Capacity: 16

std::vector::swap(vector& other):

• Swaps the contents of the vector with another vector.
• Example: myVector.swap(anotherVector);
• This swaps the contents of myVectorand anotherVector, effectively exchanging their elements.

std::vector::begin() and std::vector::end()

• Returns iterators pointing to the beginning and one past the end of the vector, respectively. Useful for iterating through the vector.
• Example: for (auto it = myVector.begin(); it ≠ myVector.end(); ++it) {..}
• These functions provides iterators that allow you to traverse the elements of the vector from the beginning to the end.

Time Complexity:

Access(operator[], at):

• Time Complexity: O(1)
• Accessing elements in a vector using operator[]or at is a constant-time operation because vectors use an array-based data structure. Elements are store in contiguous memory locations, so accessing them by index takes constant time.

Insertion at the end (push_back):

• Time Complexity: O(1) amortized
• Appending an element to the end of a vector using push_back is typically a constant-time operation. However, occasionally, when the vector needs to be resized to accommodate more elements, the operation might become O(n), where n is the current size of the vector.

Deletion from the end (pop_back):

• Time Complexity: O(1)
• Removing the last element from the vector using pop_back is a constant-time operation because it only involves adjusting the vector's size and does not require shifting elements.

Insertion/Deletion in the middle(insert, erase):

• Time Complexity: O(n)
• Inserting or erasing an element at a position other than the end of the vector requires shifting elements, which takes linear time. The time complexity is O(n) because the worst-case scenario involves moving all elements after the insertion/deletion point.

Size (size):

• Time Complexity: O(1)
• Determining the size of a vector using the size member function is a constant-time operation because the size of the vector is stored internally and can be retrieved directly.

Search (find):

• Time Complexity: O(n)
• Searching for an element in an unsorted vector using linear search (e.g., with std::find) takes O(n) time since it may require scanning the entire vector to find the element.

Sort (sort):

• Time Complexity: O(nlog(n)) or better
• Sorting a vector using a efficient sorting algorithm (e.g., std::sort) takes O(n*log(n)) time on average.