Is erasing a range more efficient than erasing each of the elements separately?

Question

If you have defined a range of elements you want to "erase", is it more efficient to call vector::erase(iterator) for every element in the range, or to call vector::erase(iterator,iterator once?

Answer 1

Of course it depends on circumstance but you can have a feeling by running some specifics. Let's see one example:

#include <iostream>
#include <vector>

uint64_t now() {
    return __builtin_ia32_rdtsc();
}

template< typename T >
void erase1( std::vector<T>& vec ) {
    while ( !vec.empty() ) {
        vec.erase( vec.begin() );
    }
}

template< typename T >
void erase2( std::vector<T>& vec ) {
    while ( !vec.empty() ) {
        vec.erase( vec.begin()+vec.size()-1 );
    }
}

template< typename T > 
void erase3( std::vector<T>& vec ) {
    vec.erase( vec.begin(), vec.end() );
}


int main() {
    for ( unsigned N = 1; N< (1<<20); N*=2 ) { 
        std::vector<int> vec;
        vec.resize( N );
        for ( uint32_t j=0; j<N; ++j ) vec[j] = N;
        uint64_t t0 = now();
        erase1( vec );
        uint64_t t1 = now();

        vec.resize( N );
        for ( uint32_t j=0; j<N; ++j ) vec[j] = N;
        uint64_t t2 = now();
        erase2( vec );
        uint64_t t3 = now();

        vec.resize( N );
        for ( uint32_t j=0; j<N; ++j ) vec[j] = N;
        uint64_t t4 = now();
        erase3( vec );
        uint64_t t5 = now();
        std::cout << (t1-t0) << " " << (t3-t2) << " " << (t5-t4) << std::endl;
    }
}

erase1() will erase one by one from the front. erase2() will erase item by item from the back and erase3() will erase on the entire range.

The results of this run are:

Program stdout
54 46 22
1144 66 24
230 116 22
362 74 24
596 108 24
924 128 22
2906 230 38
4622 270 24
11648 542 22
31764 960 34
94078 1876 24
313308 3874 32
1089342 7470 34
4967132 14792 34
25695930 14720 24
134255144 61492 24
585366944 122838 34
3320946224 115778 22
17386215680 484930 24

Results are in cycles.

You can see that erasing from the front is very costly. From the back is way faster but still apparently O(N). And erasing the range is almost instantaneous and O(1).

Answer 2

Using std::remove_if is more efficient than using a for loop with calling the method erase because for each call of the method erase all elements starting from the erasing position are moved to the left. That is the same element can be moved several times to the left.

Using the algorithm each element is moved to the left only one time.

Pay attention to that in C++ 20 there were appended two functions std::erase and std::erase_if that can be used instead of the idiom erase-remove. That is if before the C++ 20 standard you needed to write as for example

std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
v.erase( std::remove_if( std::begin( v ), std::end( v ),
                         []( const auto &item )
                         {
                             return item % 2;
                         } ), std::end( v ) );

Then now you can just write

std::erase_if( v, []( const auto &item ) { return item % 2; } );

Answer 3

From https://en.cppreference.com/w/cpp/container/vector/erase

Complexity Linear: the number of calls to the destructor of T is the same as the number of elements erased, the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements

It should be much more efficient to erase a range, as that allows the elements after and including the end iterator to be moved only once (but by a larger amount). Surely it's implementation specific.