c++ vector 使用效率問(wèn)題

1. vector中的erase方法效率是很低。

因?yàn)闉榱吮３講ector中元素在內(nèi)存空間中的連續(xù)性，在刪除某個(gè)元素之后，需要將其后的元素依次向前移動(dòng)一個(gè)位置，平均復(fù)雜度為o(n)。

gcc 下erase的實(shí)現(xiàn)如下：

iterator erase(iteratorposition)

{

if (position + 1 != end())

copy(position + 1, finish, position); // 后續(xù)元素往前移動(dòng)

--finish;

destroy(finish); // 一個(gè)釋放資源的全局函數(shù)

return position;

}

解決辦法：

如果要?jiǎng)h除了元素在最后一個(gè)位置，則不需要移動(dòng)其他元素，只需要o(1)的時(shí)間開(kāi)銷，基于這種思想，可以實(shí)現(xiàn)一種高效的vector中刪除元素的方法

for(int i=0; i

{

if( some condition )

{

swap( vec[i], vec[vec.size()-1]);

vec.pop_back();

}

else

{

i ++ ;

}

}

2.迭代器使用

vector int_vec;

for( vector::iterator iter = int_vec.begin(); iter != int_vec.end(); ++ iter)

{

…

}

千萬(wàn)注意要使用++iter 不能使用iter++

iter++ 是先拷貝一份值，再進(jìn)行++,效率很低