擦除范围是否比分别擦除每个元素更有效？

Question

如果您定义了要“擦除”的元素范围，对范围内的每个元素调用 vector::erase(iterator) 还是调用一次 vector::erase(iterator,iterator 更有效？

Answer 1

使用 std::remove_if 比使用 for 循环调用方法 erase 更有效，因为每次调用方法 erase 从擦除位置开始的所有元素都会移动到左边。即同一个元素可以多次向左移动

使用该算法，每个元素只向左移动一次。

注意在C++ 20中附加了两个函数std::erase和std::erase_if可以用来代替习语erase-remove。也就是说，如果在 C++ 20 标准之前您需要编写

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

那么现在你可以写

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

Answer 2

来自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

擦除一个范围应该更有效，因为这允许结束迭代器之后和包括结束迭代器的元素只移动一次（但移动量更大）。当然它是特定于实现的。

Answer 3

当然要视情况而定，不过你可以通过运行一些细节来感受一下。让我们看一个例子：

#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()会从前面一个一个擦掉。 erase2()将从后面逐项擦除，erase3()将擦除整个范围。

这个运行的结果是：

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

结果是循环的。

可以看出从正面擦除的代价是很大的。从后面看要快得多，但显然仍然是 O(N)。并且擦除范围几乎是瞬时的并且 O(1).

擦除范围是否比分别擦除每个元素更有效？

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

c++

algorithm

vector

erase-remove-idiom