Vectors in C++ | Looping & Problem Solving | Arrays - 2 | Lecture 13 | C++ and DSA Foundation Course

Key Concepts

• Vectors: Dynamic arrays that can be resized during runtime.
• Dynamic Array: An array that can change its size after it has been created.
• Contiguous Memory Allocation: Elements are stored in adjacent memory locations.
• Size: The number of elements currently stored in the vector.
• Capacity: The amount of memory allocated to the vector.
• push_back(): Adds an element to the end of the vector.
• insert(): Inserts an element at a specific position in the vector.
• pop_back(): Removes the last element from the vector.
• erase(): Removes an element at a specific position in the vector.
• clear(): Removes all elements from the vector.
• size(): Returns the number of elements in the vector.
• capacity(): Returns the current capacity of the vector.
• resize(): Changes the number of elements stored in the vector.
• begin(): Returns an iterator pointing to the first element of the vector.
• end(): Returns an iterator pointing to the element after the last element of the vector.

Vectors: Dynamic Arrays

Vectors are dynamic arrays, meaning their size can be changed during runtime. This contrasts with static arrays, where the size is fixed at compile time. Vectors store elements in contiguous memory locations, similar to arrays.

• Dynamic Resizing: Vectors can grow or shrink as needed, allowing for insertion and deletion of elements without manual memory management.
• Contiguous Memory: Elements are stored in adjacent memory locations, enabling efficient access and iteration.

Vector Declaration and Initialization

To use vectors, include the <vector> header file. Vectors can be declared without specifying an initial size:

#include <vector>
std::vector<int> v; // Declares an empty vector of integers

Alternatively, you can specify an initial size:

std::vector<int> v(5); // Declares a vector of integers with size 5

Vector Operations

Size and Capacity

• v.size(): Returns the number of elements currently stored in the vector.
• v.capacity(): Returns the amount of memory allocated to the vector. The capacity is always greater than or equal to the size.
• v.resize(new_size): Changes the number of elements stored in the vector. If new_size is greater than the current size, new elements are added (initialized with a default value). If new_size is less than the current size, elements are removed from the end.

Adding Elements

• v.push_back(element): Adds element to the end of the vector. This may trigger a reallocation of memory if the current capacity is not sufficient.

• v.insert(position, element): Inserts element at the specified position. The position is an iterator relative to the beginning of the vector, obtained using v.begin().

  • Example: v.insert(v.begin() + 2, 5); inserts the value 5 at the third position (index 2) in the vector.

Removing Elements

• v.pop_back(): Removes the last element from the vector.

• v.erase(position): Removes the element at the specified position. The position is an iterator relative to the beginning of the vector, obtained using v.begin().

  • Example: v.erase(v.begin() + 2); removes the element at the third position (index 2) in the vector.

• v.clear(): Removes all elements from the vector, making it empty.

Memory Allocation and Capacity Growth

When a vector's size exceeds its capacity, it reallocates memory to accommodate the new elements. The reallocation typically involves:

1. Allocating a new block of memory with a larger capacity (often a multiple of the current capacity).
2. Copying the existing elements from the old memory location to the new memory location.
3. Deallocating the old memory.

The capacity often increases in powers of 2 (e.g., 2, 4, 8, 16), but this behavior is compiler-dependent. Reallocation can be an expensive operation, so it's important to consider the potential for reallocation when working with large vectors.

Looping Through Vectors

Vectors can be iterated using various loop constructs:

For Loop

for (int i = 0; i < v.size(); ++i) {
    std::cout << v[i] << " ";
}

For-Each Loop (Range-Based For Loop)

for (int element : v) {
    std::cout << element << " ";
}

While Loop

int i = 0;
while (i < v.size()) {
    std::cout << v[i] << " ";
    ++i;
}

Example Problems and Solutions

1. Find the Last Occurrence of an Element

Problem: Given a vector and an element x, find the index of the last occurrence of x in the vector.

Solution:

Approach 1: Iterate from the beginning

int findLastOccurrence(const std::vector<int>& v, int x) {
    int lastOccurrence = -1;
    for (int i = 0; i < v.size(); ++i) {
        if (v[i] == x) {
            lastOccurrence = i;
        }
    }
    return lastOccurrence;
}

Approach 2: Iterate from the end

int findLastOccurrence(const std::vector<int>& v, int x) {
    for (int i = v.size() - 1; i >= 0; --i) {
        if (v[i] == x) {
            return i;
        }
    }
    return -1;
}

2. Count the Number of Occurrences of an Element

Problem: Given a vector and an element x, count the number of times x appears in the vector.

Solution:

int countOccurrences(const std::vector<int>& v, int x) {
    int count = 0;
    for (int element : v) {
        if (element == x) {
            ++count;
        }
    }
    return count;
}

3. Count the Number of Elements Strictly Greater Than x

Problem: Given a vector and an element x, count the number of elements in the vector that are strictly greater than x.

Solution:

int countGreaterThanX(const std::vector<int>& v, int x) {
    int count = 0;
    for (int i = 0; i < v.size(); ++i) {
        if (v[i] > x) {
            ++count;
        }
    }
    return count;
}

4. Check if an Array is Sorted

Problem: Given an array, determine if it is sorted in ascending order.

Solution:

bool isSorted(const int arr[], int size) {
    for (int i = 1; i < size; ++i) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}

5. Find the Difference Between the Sum of Elements at Even Indices and the Sum of Elements at Odd Indices

Problem: Given an array, calculate the difference between the sum of elements at even indices and the sum of elements at odd indices.

Solution:

int differenceOfSums(const int arr[], int size) {
    int sum = 0;
    for (int i = 0; i < size; ++i) {
        if (i % 2 == 0) {
            sum += arr[i];
        } else {
            sum -= arr[i];
        }
    }
    return sum;
}

Conclusion

Vectors provide a flexible and efficient way to manage collections of elements in C++. Their dynamic resizing capabilities and contiguous memory allocation make them a powerful tool for a wide range of applications. Understanding the concepts of size, capacity, and reallocation is crucial for optimizing vector usage. The example problems demonstrate how vectors can be used to solve common programming tasks.