In C++, arrays are fundamental data structures used to store collections of elements of the same type. They provide efficient random access to elements. Two common types of arrays in C++ are static arrays and dynamic arrays.

1 Static Arrays

Static arrays, also known as fixed-size arrays, are arrays whose size is fixed at compile-time and cannot be changed during program execution.

Declaration and Initialization:

int staticArray[5]; // Declaration of a static array of size 5
int staticArray[5] = {1, 2, 3, 4, 5}; // Initialization of a static array with values

Characteristics:

1. Fixed Size: The size of a static array is determined at compile-time and cannot be altered during runtime.
2. Memory Allocation: Memory for a static array is allocated on the stack.
3. Access Time: Direct access to elements with constant time complexity (O(1)).
4. Scope: Limited to the block or function where it is declared.
5. Lifetime: Exists throughout the program's execution.

Example:

#include <iostream>

int main() {
    int staticArray[5] = {1, 2, 3, 4, 5};

    // Accessing elements
    for (int i = 0; i < 5; ++i) {
        std::cout << staticArray[i] << " ";
    }

    return 0;
}

Advantages:

• Simple and efficient.
• No overhead for memory allocation/deallocation.

Limitations:

• Size must be known at compile-time.
• Cannot be resized dynamically.

2 Dynamic Arrays:

Dynamic arrays are arrays whose size can be determined and modified at runtime. Dynamic arrays are implemented using pointers and memory allocation functions.

Declaration and Initialization:

int* dynamicArray = new int[5]; // Declaration of a dynamic array of size 5

Characteristics:

1. Resizable: The size of a dynamic array can be changed during runtime.
2. Memory Allocation: Memory for a dynamic array is allocated on the heap.
3. Access Time: Direct access to elements with constant time complexity (O(1)).
4. Scope: Can have a broader scope, extending beyond the block or function it is declared.
5. Lifetime: Can be explicitly deallocated to free up memory.

Example:

#include <iostream>

int main() {
    int staticArray[5] = {1, 2, 3, 4, 5};

    // Accessing elements
    for (int i = 0; i < 5; ++i) {
        std::cout << staticArray[i] << " ";
    }

    return 0;
}

Advantages:

• Flexibility in size.
• Can be resized dynamically using memory reallocation functions like realloc().

Limitations:

• Requires manual memory management (allocation and deallocation).
• Potential for memory leaks and fragmentation if not managed properly.
• Overhead for memory allocation/deallocation.

Example:

#include <iostream>

int main() {
    // Static array
    int staticArray[5] = {1, 2, 3, 4, 5};

    // Dynamic array
    int* dynamicArray = new int[5];
    for (int i = 0; i < 5; ++i) {
        dynamicArray[i] = i + 1;
    }

    // Print static array
    std::cout << "Static Array: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << staticArray[i] << " ";
    }
    std::cout << std::endl;

    // Print dynamic array
    std::cout << "Dynamic Array: ";
    for (int i = 0; i < 5; ++i) {
        std::cout << dynamicArray[i] << " ";
    }
    std::cout << std::endl;

    // Clean up dynamic array
    delete[] dynamicArray;

    return 0;
}

Resizing dynamic array:

#include <iostream>

int* resizeArray(int* oldArray, int oldSize, int newSize) {
    // Allocate memory for the new array
    int* newArray = new int[newSize];

    // Copy elements from the old array to the new array
    for (int i = 0; i < std::min(oldSize, newSize); ++i) {
        newArray[i] = oldArray[i];
    }

    // Deallocate memory for the old array
    delete[] oldArray;

    // Return pointer to the new array
    return newArray;
}

int main() {
    // Original dynamic array
    int size = 5;
    int* dynamicArray = new int[size]{1, 2, 3, 4, 5};

    // Display original array
    std::cout << "Original Array: ";
    for (int i = 0; i < size; ++i) {
        std::cout << dynamicArray[i] << " ";
    }
    std::cout << std::endl;

    // Resize the array to double its size
    int newSize = size * 2;
    dynamicArray = resizeArray(dynamicArray, size, newSize);

    // Display resized array
    std::cout << "Resized Array: ";
    for (int i = 0; i < newSize; ++i) {
        std::cout << dynamicArray[i] << " ";
    }
    std::cout << std::endl;

    // Deallocate memory for the resized array
    delete[] dynamicArray;

    return 0;
}

1. Allocate a new array with the desired size.
2. Copy elements from the old array to the new array.
3. Deallocate memory for the old array.
4. Update the pointer to point to the new array.

The Need for Vectors

In the early days of C++, dynamic arrays with pointers were commonly used to manage collections of data. These arrays were flexible in size and allowed for efficient memory allocation. However, they posed several challenges and limitations:

1. Manual Memory Management: Dynamic arrays always required explicit memory allocation and deallocation using new and delete[] operators, making them error-prone and susceptible to memory leaks and dangling pointers.
2. Lack of Safety: Incorrect memory management could lead to memory corruption, segmentation faults, and other runtime errors, especially in complex programs or when dealing with multiple pointers.
3. Fixed Size: Once allocated, the size of a dynamic arrays could not be changed easily. Resizing required allocating a new array, copying elements, and deallocating the old array, which was cumbersome and inefficient.
4. No Built-in Operations: Dynamic arrays lacked built-in operations for common tasks like appending elements, inserting elements at arbitrary positions, or resizing dynamically.

Introducing std::vector

To address these limitations and provide a safer and more convenient alternative to dynamic arrays, the C++ Standard Library introduced the std::vector container in the Standard Template Library (STL). std::vector combines the flexibility of dynamic arrays with additional functionality and safety features:

1.  Automatic Memory Management: std::vector handles memory allocation and deallocation automatically, relieving developers from the burden of manual memory management. Memory is allocated on the heap and automatically released when the vector is destroyed.
2. Safety and Reliability: By encapsulating memory management within the vector class, std::vector reduces the risk of memory leaks, dangling pointers, and other memory-related errors. It provides a robust and reliable interface for working with dynamic arrays.
3. Dynamic Resizing: std::vector supports dynamic resizing, allowing elements to be added or removed efficiently. Resizing is performed automatically when the vector's capacity is exceeded, ensuring optimal memory usage and performance.
4. Rich Interface: std::vectorprovides a rich set of member functions and iterators for common operations such as element access, insertion, deletion, resizing, and more. These operations are safe, efficient, and easy to use, simplifying the development process.

Definition

std::vector is a dynamically resizable array-like container in C++ STL. It provides a contiguous memory block to store elements of a specified type, allowing for efficient element access, insertion, and deletion.

It is defined in the <vector> header.

Key Characteristics:

1. Dynamic Resizing:std::vector automatically manages memory allocation and resizing. It grows or shrinks as needed to accommodate elements, providing dynamic memory management.
2. Random Access: Elements in a std::vector can be accessed directly using index-based subscripting ([]). This allows for constant-time access to elements.
3. Sequential Storage: Elements in a std::vector are stored sequentially memory, providing cache-friendly access patterns and efficient traversal.
4. Safe and Reliable:std::vector encapsulated memory management and provides a robust interface for working with dynamic arrays, reducing the risk of memory leaks and pointer errors.

Declaration

#include <vector>

std::vector<T> name; // Declaration of a vector named 'name' containing elements of type 'T'

Where:

• T: Represents the type of elements stored in the vector, Replace T with the desired data type, such as int, double, std::string, etc.

1 Declaring an empty vector (using default constructor):

#include <vector>

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

2 Declaring a vector with initial values:

#include <vector>

std::vector<double> prices = {10.5, 20.3, 15.8}; // Declaration of a vector of doubles with initial values

3 Using std::initializer_list Constructor (C++11 and later):

#include <vector>

std::vector<int> vec{1, 2, 3, 4, 5}; // Initializes a vector with elements from the initializer list

4 Using Constructor with Initial Size and Value:

#include <vector>

std::vector<int> vec(5, 0); // Initializes a vector of size 5 with all elements set to 0

5 Using Copy Constructor:

#include <vector>

std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2(vec1); // Initializes vec2 as a copy of vec1

6 Using Range Constructor (C++11 and later):

#include <vector>
#include <iterator>
#include <array>

std::array<int, 5> arr = {1, 2, 3, 4, 5};
std::vector<int> vec(arr.begin(), arr.end()); // Initializes vec with elements from arr

7 Using Assignment Operator:

#include <vector>

std::vector<int> vec;
vec = {1, 2, 3, 4, 5}; // Assigns initial values to the vector

8 Using resize() Function:

#include <vector>

std::vector<int> vec;
vec.resize(5); // Resizes the vector to size 5, initializes elements to default value (0 for int)

9 Initialization of vector from array:

#include <iostream>
#include <vector>

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    // Initializing vector from array using iterators
    std::vector<int> vec(arr, arr + size); // pass start and last address

    // Displaying vector elements
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Example:

#include <iostream>
#include <vector>

int main() {
    // Declaration and initialization of a vector
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Append an element to the end of the vector
    vec.push_back(6);

    // Access elements using the subscript operator or iterators
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Functions of vector

1 push_back()

The push_back() function appends an element to the end of the vector.

#include <iostream>
#include <vector>

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

    // Adding elements to the vector
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // Displaying vector elements
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

// Output
10 2o 30

Time Complexity: O(1) amortized time

• Adding an element at the end of the vector typically requires constant time. However, if the vector needs to resize its internal storage, the operation may take O(n)time, where n is the current size of the vector.

2 pop_back()

The pop_back() function removes the last element from the vector. It takes constant time.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Removing the last element
    vec.pop_back();

    // Displaying vector elements
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}


// Output

10 20

Time Complexity: O(1)

• Removing the last element from the vector takes constant time since there is no need for shifting other elements.

3 front()

The front() function returns a reference to the first element in the vector.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Accessing the first element
    std::cout << "First element: " << vec.front() << std::endl;

    return 0;
}

// Output
First element: 10

Time Complexity: O(1)

• Accessing the first element of the vector function has constant-time complexity.

4 back()

The back() function returns a reference to the last element in the vector.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Accessing the last element
    std::cout << "Last element: " << vec.back() << std::endl;

    return 0;
}

// Output
Last element: 30

Time Complexity: O(1)

• Accessing the last element of the vector function has constant-time complexity.

5 at()

The at() function returns a reference to the element at a specified position in the vector, with bounds checking. This is safer than the subscript access. this will generate the exception if trying to access out of bound element.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Accessing elements using at()
    std::cout << "Element at index 1: " << vec.at(1) << std::endl;
    
    // Accessing elements out of bounds
    
    std::cout << "Element at index 9: " << vec.at(9) << std::endl;

    return 0;
}

// Output
Element at index 1: 20

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 9) >= this->size() (which is 3)
Program terminated with signal: SIGSEGV

Time Complexity: O(1)

• Accessing an element by index using the at() function has constant-time complexity. However, it performs bounds checking, so if the index is out of range, it throws an exception.

6 Subscript Operator ([])

The subscript operator ([]) allows you to access elements at a specific index in the vector. Indexing starts from 0. This will not generate the exception if trying to access out of bound element.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Accessing elements using the subscript operator
    std::cout << "Element at index 1: " << vec[1] << std::endl;
    
    // Accessing element out of index using the subscript operator
    std::cout << "Element at index 9: " << vec[9] << std::endl;

    return 0;
}

// Output
Element at index 1: 20

Element at index 9: 544501349 // print garbage value

Time Complexity: O(1)

• Accessing an element by index using the subscript operator has constant-time complexity.

7 insert()

The `insert() function inserts elements into the vector at a specified position.

It would take O(n), because of shifting if inserted at initial position.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Inserting elements at position 1
    vec.insert(vec.begin() + 1, 15);

    // Displaying vector elements
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

// Output
10 15 20 30

Time Complexity: O(n)

• Inserting an element or a range of element into the vector at a specified position requires shifting elements to make room, resulting in linear time complexity.

8 size()

The size() function returns the number of elements in the vector.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Getting the size of the vector
    std::cout << "Size of the vector: " << vec.size() << std::endl;

    return 0;
}


// Output

Size of the vector: 3

Time Complexity: O(1)

• Retrieving the size of the vector is a constant-time operation since the size is stored internally.

9 resize()

The resize() function changes the size of the vector so that it contains n elements.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Resizing the vector
    vec.resize(5, 0); // Resize to size 5 and fill with zeros

    // Displaying vector elements
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

// Output
10 20 30 0 0

Time Complexity: O(n)

• Resizing the vector to a specific size requires copying elements to a new memory location, which takes linear time proportional to the number of elements being copied.

10 empty()

The empty() function checks if the vector is empty (i.e., contains no elements). O(1)

#include <iostream>
#include <vector>

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

    // Checking if the vector is empty
    if (vec.empty()) {
        std::cout << "Vector is empty" << std::endl;
    } else {
        std::cout << "Vector is not empty" << std::endl;
    }

    return 0;
}

// Output
Vector is empty

Time Complexity: O(1)

• Checking if the vector is empty is a constant-time operation.

11 erase()

The erase() function removes elements from the vector. It takes either one or two arguments.

• If given single argument, it removes the element at the specified position.
• If given two arguments, it removes the elements in the range [first, last].

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // Removing element at index 2 (value: 30)
    vec.erase(vec.begin() + 2);

    // Displaying vector elements
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

// Output
10 20 40 50

Time Complexity: O(n)

• Erasing a single element or a range of elements from the vector requires shifting elements to fill the gap, resulting in linear time complexity.

12 clear()

The clear() function removes all elements from the vector, leaving it with a size of 0.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};

    // Clearing the vector
    vec.clear();

    // Checking if the vector is empty
    if (vec.empty()) {
        std::cout << "Vector is empty" << std::endl;
    } else {
        std::cout << "Vector is not empty" << std::endl;
    }

    return 0;
}

// Output
Vector is empty

Time Complexity: O(n)

• Clearing the vector by removing all elements requires linear time since it involves deallocating memory for all elements.

Iterator Functions for Vector

1 begin()

Function: Returns an iterator pointing to the first element of the vector.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin(); // Iterator pointing to the first element

2 end()

Returns an iterator pointing to the position one past the last element of the vector.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.end(); // Iterator pointing past the last element

3 rbegin()

Returns a reverse iterator pointing to the last element of the vector.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto rit = vec.rbegin(); // Reverse iterator pointing to the last element

4 rend()

Returns a reverse iterator pointing to the position before the first element of the vector.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto rit = vec.rend(); // Reverse iterator pointing before the first element

5 cbegin()

Returns a constant iterator pointing to the first element of the vector

std::vector<int> vec = {1, 2, 3, 4, 5};
auto cit = vec.cbegin(); // Constant iterator pointing to the first element

6 cend()

Returns a constant iterator pointing to the position one past the last element of the vector.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto cit = vec.cend(); // Constant iterator pointing past the last element

7 crbegin()

Returns a constant reverse iterator pointing to the last element of the vector.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto crit = vec.crbegin(); // Constant reverse iterator pointing to the last element

8 crend()

Returns a constant reverse iterator pointing to the position before the first element of the vector.

std::vector<int> vec = {1, 2, 3, 4, 5};
auto crit = vec.crend(); // Constant reverse iterator pointing before the first element

How vector Works internally during addition of new element

When a std::vector in C++ is full and you attempt to push a new element into it, the vector needs to reallocate memory to accommodate the new element.

1 Capacity Check:

• Before adding a new element the vector checks if there is enough capacity to accommodate the new element.
• If the vector's size is less than its capacity, there is available space for the new element, and no reallocation is needed.

2 Reallocation:

• If the vector is already at its capacity, it needs to reallocate memory to increase its capacity.
• The new capacity is usually increased by a factor (e.g., doubling the current capacity).
• A new memory block is allocated on the heap with the increased capacity.
• All existing elements are copied from the old memory to the new memory block.
• The old memory block is deallocated.

3 Insertion of New Element:

• After reallocation, the new element is added at the end of the vector.
• The size of the vector is incremented to reflect the addition of the new element.

4 Amortized Time Complexity:

• Although reallocation involves copying elements, the cost is amortized over multiple insertions.
• In other words, the average time complexity of a single insertion operation is O(1), even though occasional reallocations may take O(n) time.
• Average case and best case  = O(1)
• Worst case = O(n)

#include <iostream>
#include <vector>

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

    // Add elements until capacity is reached
    for (int i = 0; i < 5; ++i) {
        vec.push_back(i);
        std::cout << "Capacity: " << vec.capacity() << std::endl; // Print capacity
    }

    return 0;
}

// Output
Capacity: 1
Capacity: 2
Capacity: 4
Capacity: 4
Capacity: 8

In this example, you can see that the capacity of the vector increases as elements are added. The capacity is dynamically adjusted by the vector implementation to optimize memory usage and insertion performance. When the number of elements exceeds the current capacity, the vector reallocates memory to increase its capacity. This typically involves doubling the current capacity to minimize the number of reallocation needed.