Deleting items from somewhere in the middle of an std::vector
takes O(n) time. This is because the resulting gap from removing an item must be filled by moving all the items which come after the gap one slot to the left.
While moving items around like this, which might be expensive if they are complex and/or very large and include many items, we preserve their order. If preserving the order is not important, we can optimize this, as this section shows.
In this section, we will fill an std::vector
instance with some example numbers, and implement a quick remove function, which removes any item from a vector in O(1) time.
- First, we need to include the required header files.
#include <iostream> #include <vector> #include <algorithm>
- Then, we define a main function where we instantiate a vector with example numbers.
int main() { std::vector<int> v {123, 456, 789,...