DEV Community

dinhluanbmt
dinhluanbmt

Posted on

1

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

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

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay