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();
    }
}

Comments

[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();
    }
}

[dinhluanbmt]

you are right! template is better^^

[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.

[dinhluanbmt]

thank you