Dynamic Arrays using std::vector

Removing Elements from the Middle of a Vector

How can I efficiently remove elements from the middle of a std::vector?

Abstract art representing computer programming

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:

#include <iostream>
#include <vector>

int main(){
  std::vector<int> numbers{1, 2, 3, 4, 5};

  // Remove the element at index 2
  // (the third element)
  numbers.erase(numbers.begin() + 2); 

  for (int num : numbers) {
    std::cout << num << ' ';
  }
}
1 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)O(n), where nn 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:

#include <iostream>
#include <vector>

int main(){
  std::vector<int> numbers{
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  // Remove objects from index 2 to 5 (inclusive)
  numbers.erase(numbers.begin() + 2, 
                numbers.begin() + 6); 

  for (int num : numbers) {
    std::cout << num << ' ';
  }
}
1 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:

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  std::vector<int> numbers{
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  // Remove all even numbers
  numbers.erase(
    std::remove_if(
      numbers.begin(), numbers.end(),
      [](int n){ return n % 2 == 0; }), 
    numbers.end());

  for (int num : numbers) {
    std::cout << num << ' ';
  }
}
1 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.

Answers to questions are automatically generated and may not have been reviewed.

3D art showing a progammer setting up a development environment
Part of the course:

Intro to C++ Programming

Become a software engineer with C++. Starting from the basics, we guide you step by step along the way

Free, unlimited access

This course includes:

  • 57 Lessons
  • Over 200 Quiz Questions
  • 95% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved