Removing Elements from the Middle of a Vector

Removing elements from the middle of a std::vector can be done using the erase() function. However, it's important to understand the performance implications and some best practices.

Using erase()

The erase() function removes an element at a specific position or a range of elements. Here's how you can use it:

1#include <iostream>
2#include <vector>
3
4int main(){
5  std::vector<int> numbers{1, 2, 3, 4, 5};
6
7  // Remove the element at index 2
8  // (the third element)
9  numbers.erase(numbers.begin() + 2); 
10
11  for (int num : numbers) {
12    std::cout << num << ' ';
13  }
14}

11 2 4 5

Performance Considerations

When you remove an element from the middle of a std::vector, all elements after the removed element need to be shifted to fill the gap. This operation has a time complexity of $O(n)$, where $n$ is the number of elements after the removal point.

If you need to remove multiple elements, it's more efficient to remove them in a single operation:

1#include <iostream>
2#include <vector>
3
4int main(){
5  std::vector<int> numbers{
6    1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
7
8  // Remove objects from index 2 to 5 (inclusive)
9  numbers.erase(numbers.begin() + 2, 
10                numbers.begin() + 6); 
11
12  for (int num : numbers) {
13    std::cout << num << ' ';
14  }
15}

11 2 7 8 9 10

Efficient Removal of Multiple Elements

If you need to remove multiple elements that don't form a contiguous range, consider using the erase-remove idiom:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int main(){
6  std::vector<int> numbers{
7    1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
8
9  // Remove all even numbers
10  numbers.erase(
11    std::remove_if(
12      numbers.begin(), numbers.end(),
13      [](int n){ return n % 2 == 0; }), 
14    numbers.end());
15
16  for (int num : numbers) {
17    std::cout << num << ' ';
18  }
19}

11 3 5 7 9

This approach is more efficient as it only performs one pass through the vector, moving elements that should be kept to the front.

Remember, if you frequently need to remove elements from the middle of a container, std::vector might not be the best choice. Consider using std::list or std::deque for such scenarios, as they offer more efficient insertion and deletion in the middle.