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

mugesh_gcce_6f2fa7326bcf profile image

"Cracking the Chessboard Challenge: The N-Queens Problem Explained"

MUGESH G CCE -

saravanan_d2501e36b94233f profile image

Rat and Maze Problem

Saravanan -

chandra_priyan_73c13146f6 profile image

Blockchain Implementation: A Beginner's Guide to Decentralized Innovation

Chandra priyan -

tom-takeru profile image

The simplest demo on SSE(Server-Send Events)

tom-takeru -