DEV Community

dinhluanbmt
dinhluanbmt

Posted on

C++, Delete(erase) item from vector in O(1) time

#cpp #vector #erase #fast

Deleting an item in the middle of a large vector is expensive because all items after the deleted item must be shifted to the left.
In case the index of the item/the order is not important, we can delete the item in O(1) time.

void fast_erase(vector<int>& v, int idx){
    if(idx < v.size()){
        v[idx] = std::move(v.back());
        v.pop_back();
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (4)

Collapse
 
pauljlucas profile image
Paul J. Lucas •

That really should be:

template<typename T>
void erase_at( std::vector<T> &v, typename std::vector<T>::size_type i ) {
    if ( i < v.size() ) {
        if ( i < v.size() - 1 )
            v[i] = std::move( v.back() );
        v.pop_back();
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
dinhluanbmt profile image
dinhluanbmt •

you are right! template is better^^

Collapse
 
pauljlucas profile image
Paul J. Lucas •

Templates are just one thing. The other two things are that (1) you really should use size_type (or at least size_t) and (2) you didn't take the degenerate case where the index == size()-1 into account.

Thread Thread
 
dinhluanbmt profile image
dinhluanbmt •

thank you

Read next

dbhatasana profile image

The Role of Change Management in Digital Adoption: A Pathway to Successful SQL Implementation

Divyesh Bhatasana -

virajlakshitha profile image

Orchestrating Complex Workflows with AWS Step Functions and NestJS: A Deep Dive

Viraj Lakshitha Bandara -

func25 profile image

Go Singleflight Melts in Your Code, Not in Your DB

Phuong Le -

garciadiazjaime profile image

React + AWS Cognito: Email Authentication Setup Guide (First Part)

Jaime -