vector會出現無效迭代器嗎?
當面試官提問這個問題,是否感到詫異?
首先要回答 會
在泛型編程還是STL的實際運用中,迭代器(iterator)無疑扮演者重要的角色。迭代器是一種類似於指針的對象(如可以內容提領,成員訪問等),但他又不僅僅是一種普通的指針。
我們先看如下代碼:
<code>std
::vector
<int
> vec={1
,2
,3
,4
,5
,6
};std
::vector
<int
>::iterator it = vec.begin();while
(it != vec.end()) {if
(*it %2
==0
) { it = vec.erase(it); ++it; } }/<code>
這樣的代碼乍一看好像沒有什麼問題,但是他是有問題的,因為在vector是順序存儲的,在vector中刪除一個元素之後,我們需要為vector重新分配一個空間,存放在舊的空間的元素被複制到新的空間,如果刪除的這個元素的迭代器會指向下一個元素之後還++it,則在複製的時候找不到下一個元素,因此會使刪除點及刪除點之後的迭代器失效。正確做法是:
<code>std
::vector
<int
> vec={1
,2
,3
,4
,5
,6
};std
::vector
<int
>::iterator it = vec.begin();while
(it != vec.end()) {if
(*it %2
==0
) { it = vec.erase(it); }else
{ ++it; } }/<code>
對於添加元素也是同理,如果當前容器中有10個元素,現在又要添加元素到容器中,如果內存中沒有多餘的空間,因此vector需要重新開闢空間來存儲原來的元素以及新添加的元素。在新的空間複製原理來的元素,並插入新的元素,最後撤銷原來的空間,這種情況發生會使所有迭代器都失效。
總結 vector迭代器的幾種失效的情況:
- 當插入(push_back)一個元素後,end操作返回的迭代器肯定失效。
- 當插入(push_back)一個元素後,capacity返回值與沒有插入元素之前相比有改變,則需要重新加載整個容器,此時first和end操 作返回的迭代器都會失效。
- 當進行刪除操作(erase,pop_back)後,指向刪除點的迭代器全部失效;指向刪除點後面的元素的迭代器也將全部失效。
從以上三個方面回答應該是滿足面試官的答案。