Mastering C++ Vectors: Built-in Functions, Usage, and Complexity

What is a Vector in C++?

A vector in C++ is a dynamic array that can grow or shrink in size automatically. Unlike regular arrays, which have a fixed size, vectors offer flexibility by managing memory dynamically.

Why Use Vectors Instead of Arrays?

• Dynamic Sizing: Unlike arrays, vectors can resize themselves automatically when needed.
• Ease of Use: Vectors provide built-in functions for adding, removing, and modifying elements efficiently.
• Memory Management: They handle memory allocation and deallocation automatically.
• Standard Library Support: Vectors are part of the C++ Standard Template Library (STL), making them widely used and optimized.

Comparison: Vector vs. Array

Feature	Vector	Array
Size	Dynamic (resizable)	Fixed (cannot be resized)
Memory Allocation	Automatic	Manual
Ease of Insertion/Deletion	Easy with push_back and erase	Difficult, requires shifting elements
Performance	Slight overhead due to dynamic resizing	More efficient in memory if size is known
STL Support	Yes	No

---

Vector Initialization

C++ provides multiple ways to initialize vectors:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v1; // Empty vector
    vector<int> v2(5); // Vector with 5 elements (default initialized to 0)
    vector<int> v3(5, 10); // Vector with 5 elements, all initialized to 10
    vector<int> v4(v3); // Copy constructor
    int arr[] = {1, 2, 3, 4, 5};
    vector<int> v5(arr, arr + 5); // Initialize from array

    return 0;
}

Name	Details	Time Complexity
vector<type> v;	Constructs a vector with 0 elements.	O(1)
vector<type> v(N);	Constructs a vector with N elements.	O(N)
vector<type> v(N, V);	Constructs a vector with N elements initialized to V.	O(N)
vector<type> v(v2);	Constructs a vector by copying another vector v2.	O(N)
vector<type> v(A, A+N);	Constructs a vector by copying elements from an array A of size N.	O(N)

---

Vector Capacity Functions

These functions help manage the size and storage capacity of vectors:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10, 5);
    cout << "Size: " << v.size() << endl;
    cout << "Capacity: " << v.capacity() << endl;
    cout << "Max Size: " << v.max_size() << endl;
    v.clear();
    cout << "Is empty: " << v.empty() << endl;
    return 0;
}

Name	Details	Time Complexity
v.size()	Returns the number of elements in the vector.	O(1)
v.max_size()	Returns the maximum number of elements the vector can hold.	O(1)
v.capacity()	Returns the current allocated capacity of the vector.	O(1)
v.clear()	Removes all elements but does not free memory.	O(N)
v.empty()	Checks if the vector is empty. Returns true/false.	O(1)
v.resize(N)	Changes the size of the vector.	O(K), where K is the difference between new size and current size.

---

Vector Modifiers

Modifiers allow you to update vector elements dynamically:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.pop_back();
    v.insert(v.begin(), 5);
    v.erase(v.begin() + 1);

    for (int num : v) {
        cout << num << " ";
    }
    return 0;
}

Name	Details	Time Complexity
v = or v.assign()	Assigns a new vector.	O(N) if sizes differ, O(1) otherwise.
v.push_back(value)	Adds an element to the end of the vector.	O(1)
v.pop_back()	Removes the last element.	O(1)
v.insert(position, value)	Inserts an element at a specific position.	O(N+K), where K is the number of elements inserted.
v.erase(position)	Deletes elements from a specific position.	O(N+K), where K is the number of elements deleted.
replace(v.begin(), v.end(), old_value, new_value)	Replaces all occurrences of old_value with new_value. (Uses <algorithm> library).	O(N)
find(v.begin(), v.end(), value)	Finds an element in the vector. (Uses <algorithm> library).	O(N)

---

Element Access Functions

These functions allow direct access to vector elements:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40};
    cout << "First Element: " << v.front() << endl;
    cout << "Last Element: " << v.back() << endl;
    cout << "Element at index 2: " << v.at(2) << endl;
    return 0;
}

Name	Details	Time Complexity
v[i]	Accesses the ith element.	O(1)
v.at(i)	Accesses the ith element with bounds checking.	O(1)
v.front()	Returns the first element.	O(1)
v.back()	Returns the last element.	O(1)

---

Vector Iterators

Iterators help traverse and manipulate vector elements efficiently:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40};
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    return 0;
}

Name	Details	Time Complexity
v.begin()	Returns an iterator to the first element.	O(1)
v.end()	Returns an iterator to the last element.	O(1)

---

Conclusion

Vectors in C++ provide robust functionality with efficient time complexities. They offer dynamic resizing, built-in functions, and ease of use, making them superior to traditional arrays in many cases. Understanding their built-in functions allows developers to utilize them effectively for dynamic data storage and manipulation.