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.
Top comments (0)