Vector erase() function in C++
In this article, you will learn about the Vector erase() function in C++ with their examples.
Introduction:
In C++, a "vector" is like a dynamic array that can grow or shrink in size. It's a container that can hold a lot of things in a certain order, like words or numbers. Consider removing a certain number, say 15, from a vector of numbers that contains [5, 10, 15, 20, and 25]. The erase() function can be applied in this situation.
The erase() function is like an eraser for your vector. It helps you remove elements from the vector. A vector adjusts itself to fill in the space left by an element that has been erased when you use the erase() function on it and specify the element you want to remove from the vector.
Method 1: Element Removal Approach using the erase() Function
Algorithm:
Step-1: Input:
A vector of elements and the position/index of the element to be removed.
Step-2: Output:
Updated vector with the specified element removed.
Step-3: Procedure:
- Get the input vector and the position/index of the element to be removed.
- Use the erase() function on the vector, providing the iterator (position) pointing to the element to be removed.
- The erase() function removes the specified element from the vector and shifts the remaining elements to fill the gap.
- The vector is now updated with the element removed.
Stet-4: Example:
- Consider the following vector: [5, 10, 15, 20, 25], where we wish to eliminate the element at position 2 (15).
- Input: Vector [5, 10, 15, 20, 25], Position 2.
- Using erase() function on position 2: vector.erase(vector.begin() + 2);
- Resulting vector: [5, 10, 20, 25].
Program:
Let's take an example to understand the use of the erase() function in C++.
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers = {5, 10, 15, 20, 25};
int positionToRemove = 2;
numbers.erase(numbers.begin() + positionToRemove);
std::cout << "Updated vector: ";
for (int num : numbers) {
std::cout << num << " ";
}
return 0;
}
Output:
Updated vector: 5 10 20 25
Complexity analysis:
Time Complexity: O(n)
- Initializing the vector takes O(n) time complexity, where n is the number of initial elements in the vector (in this case, 5).
- The erase() function is used to remove an element at a specific position in the vector. In the worst case, this operation involves shifting all elements after the erased element by one position to fill the gap. It takes O(n) time complexity, where n is the vector's size after the deleted element. However, the vector is small (4 elements after erasing), so the time complexity is insignificant.
- Printing the updated vector takes O(n) time complexity, where n is the number of elements in the updated vector.
- The dominant time complexity is from the erase() operation in this specific example, but it's not a concern because the vector is small. The time complexity can be approximated as O(n).
Space Complexity: O(n)
- The memory needed to hold the vector itself affects the space complexity. In this instance, the complexity of the space is O(n), where n is the number of elements in the vector.
Method 2: Value Removal Approach using std::find() and erase()
Introduction:
The "Value Removal Approach using std::find() and erase()" is a technique in C++ that allows you to efficiently remove a specific value from a vector, which is a dynamic list of elements. This approach is particularly useful when you know the value you want to remove but not its position in the vector.
Algorithm:
Step-1: Input:
A vector of values where you wish to remove the value.
Step-2: Output:
Updated vector after removing the specified value.
Step-3: Procedure:
- Get the input vector and the value you want to remove.
- Use the std::find() function to search for the value in the vector.
- If std::find() returns an iterator that's not pointing to the end of the vector, it means the value was found in the vector.
- In that case, use the erase() function with the iterator to remove the value from the vector.
- Print the updated vector.
Step-4: Example:
Let's work with a vector: [5, 10, 15, 20, 25], and we want to remove the value 15.
- Input: Vector [5, 10, 15, 20, 25], Value to Remove 15.
- Using std::find() to search for 15. The iterator points to position 2.
- Use the erase() function with the iterator from step 3 to remove 15.
- Resulting vector: [5, 10, 20, 25].
Program:
Let's take an example to understand the use of the erase() function in C++.
#include <iostream>
#include <vector>
#include <algorithm> // Include the algorithm library for std::find()
int main() {
std::vector<int> numbers = {5, 10, 15, 20, 25};
int valueToRemove = 15;
auto it = std::find(numbers.begin(), numbers.end(), valueToRemove);
if (it != numbers.end()) {
numbers.erase(it);
std::cout << "Updated vector: ";
for (int num : numbers) {
std::cout << num << " ";
}
} else {
std::cout << "Value not found in the vector.";
}
return 0;
}
Output:
Updated vector: 5 10 20 25
Complexity analysis:
Time Complexity:
- The vector is searched via the std::find() algorithm to locate the required value. In the worst scenario, it might be necessary to traverse the entire vector, which would have an O(n) time complexity, where n is the total number of entries in the vector.
- In the worst scenario, shifting the elements after the removed element to fill the gap takes O(n) time complexity because the erase() operation only runs once.
- Printing the updated vector involves iterating through all elements, which takes O(n) time complexity.
- The dominant time complexity is from this specific example's std::find() operation. The time complexity can be approximated as O(n).
Space Complexity:
- The memory that was used to store the input vector has an impact on the space complexity. Because there are n entries in the vector, the answer in this example is O(n).
- The std::find() procedure has an O(1) space complexity since it utilizes a fixed amount of extra memory.
- The space used for other variables, like the iterator, is also constant.
- Space complexity is still O(n), where n is the number of elements in the vector.