如果您已經定義了要“擦除”的vector::erase(iterator)元素范圍，那么呼叫該范圍內的每個元素還是呼叫vector::erase(iterator,iterator一次更有效？
uj5u.com熱心網友回復：
當然，這取決于具體情況，但您可以通過運行一些細節來感受一下。讓我們看一個例子：
#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)。
uj5u.com熱心網友回復：
來自https://en.cppreference.com/w/cpp/container/vector/erase
Complexity Linear：呼叫T的解構式的次數與擦除的元素個數相同，T的賦值運算子呼叫次數等于擦除元素后向量中的元素個數
擦除范圍應該更有效，因為這允許在結束迭代器之后和包括結束迭代器之后的元素僅移動一次（但移動量更大）。當然，它是特定于實作的。
uj5u.com熱心網友回復：
Usingstd::remove_if比使用 for 回圈呼叫方法更有效，erase因為對于方法的每次呼叫，erase從擦除位置開始的所有元素都向左移動。也就是說，同一個元素可以多次向左移動。
使用該演算法，每個元素僅向左移動一次。
要注意，在C 20有附在兩個功能std::erase并且std::erase_if能夠用于代替成語擦除-洗掉。也就是說，如果在 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; } );
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400696.html