別被Vector最后一個元素Erase錯誤
前言:
vector我們經(jīng)常使用,對vector里面的基本函數(shù)構(gòu)造函數(shù)、增加函數(shù)、刪除函數(shù)、遍歷函數(shù)我們也會用到。其中在使用遍歷之后erase刪除元素過程中,會出現(xiàn)一種刪除最后一個元素破壞了迭代器的情況。
如下所示 刪除到最后一個元素的時候就會報錯:
- vector<int> data(10);
- auto temp_begin = data.begin(), temp_end= data.end();
- for(;temp_begin!=temp_end;){
- data.erase(temp_begin);
- }
產(chǎn)生這個問題的原因是:當我們調(diào)用erase方法刪除元素的時候,erase方法會返回下一個元素的迭代器。當刪除到最后一個元素的時候,這個時候返回的是最后一個元素之后的容器,而不是最后一個元素。
原因分析:
vector:
Because vectors keep an array format, erasing on positions other than the vector end also moves all the elements after the segment erased to their new positions, which may not be a method as efficient as erasing in other kinds of sequence containers (deque, list). This invalidates all iterator and references to position (or first) and its subsequent elements.
假設(shè)你的 vector 中有多個對象,最后一個被標記為銷毀。當您調(diào)用erase時,它將返回一個新的有效迭代器,該迭代器指向已刪除元素之后的元素。被刪除的元素之后沒有元素,因此返回的迭代器為data.end()。
然后,我們繼續(xù)循環(huán)的頂部并取消引用此迭代器,這是無效的。如果要讓迭代器指向有效元素,則需要在擦除后減少其迭代器。vec.end() 給你元素的迭代器以下容器的最后一個元素??催@里:
list和vector區(qū)別(list 這樣刪除就沒事)
List:
This effectively reduces the list size by the number of elements removed, calling each element's destructor before.
lists are sequence containers specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence. Compared to the other base sequence containers (vector and deque), lists are the most efficient container erasing at some position other than the beginning or the end of the sequence, and, unlike in these, all of the previously obtained iterators and references remain valid after the erasing operation and refer to the same elements they were referring before (except, naturally, for those referring to erased elements).
列表是序列容器,專門設(shè)計用于在任何位置高效插入和刪除元素,甚至在序列的中間。list erase不會改變原來的iterator,所以不會出現(xiàn)像vector刪除最后一個iterator后程序錯誤。
修改建議
下面修改的建議都是讓vector的end迭代器可以一直更新,重新判斷當前位置。
- vector<int> data(10);
- auto iter = data.begin();
- while(iter != data.end())
- {
- data.erase(iter);
- }
- for (iter = data.begin(); it != data.end();)
- {
- data.erase(iter);
- }
將刪除最后一個元素
- data.erase(data.end() - 1);
- data.erase(data.begin() + data.size() - 1);
應(yīng)該提到的是,如果向量為空,則該操作將崩潰,因此出于安全考慮,我們可以再添加一個vector是否為空的判斷
- if (!data.empty())
- data.erase(vec.end() - 1);
另外我們也發(fā)現(xiàn) vector 的 erase 需要整個vector 移動,這個代價十分高,所以盡量少用。若排序順序不是很重要的話,可以和最后的那個item swap,然后刪掉最后那個,這樣可以顯著的提高效率。
結(jié)語
這就是我分享的項目中一些vector使用,如果大家有更好的想法和需求,也歡迎大家加我好友交流分享哈。
作者:良知猶存,白天努力工作,晚上原創(chuàng)公號號主。公眾號內(nèi)容除了技術(shù)還有些人生感悟,一個認真輸出內(nèi)容的職場老司機,也是一個技術(shù)之外豐富生活的人,攝影、音樂 and 籃球。關(guān)注我,與我一起同行。