c++ - 擦除范围是否比单独擦除每个元素更有效？

Question

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

Answer 1

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

Complexity Linear：调用T的析构函数的次数与擦除的元素个数相同，T的赋值运算符调用次数等于擦除元素后向量中的元素个数

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

Answer 2

当然，这取决于具体情况，但您可以通过运行一些细节来感受一下。让我们看一个例子：

#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)。

Answer 3

usingstd::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; } );