網站首頁 編程語言 正文
一、vector迭代器失效問題
1. insert迭代器失效
上文我們寫了insert的模擬實現，最開始的版本是有許多Bug的，比如迭代器失效，最后經過優化修改實現了insert，這里我們以最初的版本為例，分析并解決迭代器失效問題。如下：
void insert(iterator pos, const T& x)
{
//檢測參數合法性
assert(pos >= _start);
assert(pos <= _finish);
//檢測是否需要擴容
if (_finish == _endofstorage)
{
size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapcacity);
}
//挪動數據
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
//插入指定的數據
*pos = x;
_finish++;
}
insert的迭代器失效分為兩大類：
1.1.擴容導致野指針
我們給出兩組測試用例如下：
我們發現push_back尾插4個后調用insert會出現隨機值，而push_back尾插5個后調用insert就沒有問題。
這里我們就不墨跡了，問題就是擴容導致pos迭代器失效，原因在于pos沒有更新，導致非法訪問野指針。
上述當尾插4個數字后，再頭插一個數字，發生擴容，根據reserve擴容機制，_ start和_ finish都會更新，但是這個插入的位置pos沒有更新，此時pos依舊執行舊空間，再者reserve后會釋放舊空間，此時的pos就是野指針，導致*pos = x就是對非法訪問野指針。因為pos迭代器沒有更新，所以后續挪動數據并沒有實現，而插入數據是對釋放的空間進行操作，同樣沒有意義。這也就是說不論你在哪個位置插入，都沒有效果。
解決辦法：
可以通過創建變量n來計算擴容前pos迭代器（指針）位置和_ start迭代器（指針）位置的相對距離，最后在擴容后，讓_start再加上先前算好的相對距離n就是更新后的pos指針的位置了。
修正如下：
void insert(iterator pos, const T& x)
{
//檢測參數合法性
assert(pos >= _start);
assert(pos <= _finish);
//檢測是否需要擴容,擴容以后pos就失效了，需要更新一下
if (_finish == _endofstorage)
{
size_t n = pos - _start;//計算pos和start的相對距離
size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapcacity);
// 擴容會導致pos迭代器失效，需要更新處理一下
pos = _start + n;//防止迭代器失效，要讓pos始終指向與_start間距n的位置
}
//挪動數據
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
//插入指定的數據
*pos = x;
_finish++;
}
此時的迭代器失效已經解決了一部分，當然還存在一個迭代器失效問題，見下文：
1.2.迭代器指向位置意義改變
比如現在我要在所有的偶數前面 插入2，可是測試結果確是如下：
這里發生了斷言錯誤，這段代碼發生了兩個錯誤：
- 和上面的錯誤一樣，首先it是指向原來的空間，當insert插入新元素時會發生擴容，原來的舊數據被拷貝到了新空間上，并且釋放舊空間，這也就意味著舊空間已經被操作系統回收，而it一直是指向舊空間的，隨后遍歷it時就非法訪問野指針，也就失效了。形參的改變不會影響實參，即使你內部pos的指向改變了，但是并不會影響我外部的it。所以我們仍然無法通過it去訪問元素。
- 為了解決上面的錯誤，有人可能會說提前reserve開辟足夠大的空間即可避免發生野指針的現象，但是又出現了一個新的問題，看圖：
此時insert以后雖然沒有擴容，it也沒有成為野指針，但是it指向位置意義變了，每插入一個數據，it就指向插入數據的下一個數據，導致我們這個程序重復插入20。
解決辦法：
給insert函數加上返回值即可解決，返回指向新插入元素的位置。
iterator insert(iterator pos, const T& x)
{
//檢測參數合法性
assert(pos >= _start);
assert(pos <= _finish);
//檢測是否需要擴容,擴容以后pos就失效了，需要更新一下
if (_finish == _endofstorage)
{
size_t n = pos - _start;//計算pos和start的相對距離
size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapcacity);
// 擴容會導致pos迭代器失效，需要更新處理一下
pos = _start + n;//防止迭代器失效，要讓pos始終指向與_start間距n的位置
}
//挪動數據
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
//插入指定的數據
*pos = x;
_finish++;
return pos;
}
我們調用函數模塊也得改動，讓it自己接收insert后的返回值：
//在所有的偶數前面插入2
void test_vector3()
{
vector<int> v;
v.reserve(10);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = find(v.begin(), v.end(), 1);
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.insert(it, 20);
}
it++;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
擴展：
有的同學可能說，能否用引用，那樣就不用返回迭代器了，引用需要傳一個左值變量，但是如果我傳insert(bgein()，0)中的begin()是表達式的返回值，是一個臨時變量，具有常性。不能這樣使用。還有一些原因涉及到更深層次的問題。
1.3.windows下VS中標準庫和Linux下g++中標準庫對insert迭代器失效的處理
VS：
針對于擴容發生野指針類的迭代器失效，VS官方庫是直接斷言報錯。把相同的代碼放到Linux的g++下面試試看呢？
Linux：
很明顯Linux這里可以直接訪問，甚至是可以修改?？梢姴煌h境下對待迭代器失效的處理方式是不一樣的，windows下更加嚴格，Linux下比較佛系。
2. erase迭代器失效
和insert函數一樣，erase同樣會存在迭代器失效問題，這里先給出erase模擬實現的代碼，存在一些問題：
// 返回刪除數據的下一個數據
// 方便解決:一邊遍歷一邊刪除的迭代器失效問題
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
//從pos + 1的位置開始往前覆蓋，即可完成刪除pos位置的值
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
}
_finish--;
}
- erase的失效都是意義變了，或者不在有效訪問數據的有效范圍內
- 一般不會使用縮容的方案，那么erase的失效，一般也不存在野指針的失效
2.1.迭代器失效指向位置意義改變
現在要對如下代碼進行測試：
void test_vector2()
{
cpp::vector<int> v;
//v.reserve(10);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
cout << v.size() << ":" << v.capacity() << endl;
vector<int>::iterator it = find(v.begin(), v.end(), 2);
if (it != v.end())
{
v.erase(it);
}
cout << *it << endl; // 讀
(*pos)++; // 寫
cout << *it << endl << endl;
cout << v.size() << ":" << v.capacity() << endl;
for (auto e : v)
{
cout << e << " ";
}
}
運行結果：
這里首先在尾插4個數據后，比較了下size和capacity的大小，此時是相等的，接下來刪除值為2的數，此時* it就是刪除數字的下一個數據，沒有問題，并且有效數據size也少了一個，后續修改*it也沒有問題。
可是當我要刪除值為4的數據呢，再執行上述測試用例會是什么結果呢？
這里我總共就有4個數字，按理說把最后一個數字刪去后，有效數字只有1、2、3，這里應該不存在訪問最后一個值的現象，但是此結果確實是刪掉4后又訪問了4，離譜的是還修改了4為5，這就是erase典型的迭代器失效。因為你空間還沒有縮容，刪掉的4還存在，導致最終還能夠被訪問。
總結：
可見代碼確實是實現了刪除，但是程序訪問出現問題，原因就是erase后pos失效了，pos的意義變了，（但是在不同平臺下對于訪問pos的反應是不一樣的，因此我們使用的時候要特別小心，統一以失效的角度去看待）。但如果不訪問pos指向的內容就不會出問題。比如我們沒有訪問v.end()。
2.2.windows下VS中標準庫和Linux下g++中標準庫對erase迭代器失效的處理
這里我們以如上程序進行對比vs和g++標準庫對erase迭代器失效的處理：
VS下：
VS環境下檢查非常嚴格， 直接強制檢查斷言錯誤。
Linux下：
很明顯看出Linux下對于迭代器失效的檢查就松懈很多，不會報錯。
結論如下：
- erase(pos)以后pos失效了，pos的意義變了，但是在不同平臺下面對于訪問pos的反應是不一樣的，我們用的時候要以失效的角度去看待此問題。
- 對于insert和erase造成迭代器失效問題，linux的g++平臺檢查并不是很嚴格，基本靠操作系統本身野指針越界檢查機制。windows下VS系列檢查更嚴格一些，使用一些強制檢查機制，意義變了可能會檢查出來。
- 雖然g++對于迭代器失效檢查時是并不嚴格，但是套在實際場景中，迭代器意義變了，也會出現各種問題。
總結：
大家可能發現我們實現的vector如果不使用std::命名空間封裝的話，結果和Linux下的結果一樣。這是因為VS使用的STL標準庫是PJ版本，它檢查更為復雜，實現更為復雜；而我們使用的STL標準庫是SGI版，是Linux的g++編譯器使用的版本，也是侯捷老師的《STL源碼剖析》的版本。它檢查較為松懈，因為這里的迭代器就是原生指針，沒有進行封裝檢查等。
下面分別給出三組測試用例：
- 1 2 3 4
- 1 2 3 4 5
- 1 2 2 3 4 5
void test_vector4()
{
//刪除所有的偶數
std::vector<int> v;
//v.reserve(10);
// 第一組測試用例:
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
it++;
}
for (auto e : v)
{
cout << e << " ";
}
}
在VS下用官方庫去測試會三組數據都崩潰：
而Linux下的結果如下：
畫圖演示錯誤過程：
原因分析：
毫無疑問上訴代碼會崩潰，因為erase后迭代器it所指向的位置失效，（雖然感覺是可以繼續使用的，但在vs下就是不可以使用，在Linux下就可以對這個位置進行訪問），所以下面我們用返回值來更新迭代器。
解決方案如下：
給erase加上返回值即可避免問題，返回刪除元素的下一個位置。
修正如下：
// 返回刪除數據的下一個數據
// 方便解決:一邊遍歷一邊刪除的迭代器失效問題
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
//從pos + 1的位置開始往前覆蓋，即可完成刪除pos位置的值
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
}
_finish--;
return pos;
}
我們調用函數模塊也得改動，讓it自己接收erase后的返回值：
void test4()
{
//刪除所有的偶數
std::vector<int> v;
//v.reserve(10);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
it++;
}
}
for (auto e : v)
{
cout << e << " ";
}
}
分析：
erase刪除pos位置元素后，pos位置之后的元素會往前移動，沒有導致底層空間的改變，理論上講迭代器不會失效，但是如果pos位置剛好是最后一個元素，刪完之后pos剛好是end的位置，而end的位置是沒有有效元素的，那么pos就失效了。因此刪除vector中任意位置元素時，vs均認為該位置上迭代器失效了！也就是說vector刪除一定會導致迭代器失效。
3.迭代器失效總結
vector迭代器失效有2種
1、擴容，導致野指針失效
2、迭代器指向的位置意義變了
系統越界機制檢查，不一定能檢查到；編譯實現機制檢查，相對靠譜。
總結：
- 對于insert和erase造成迭代器失效問題，linux g++平臺檢查很松懈，基本依靠操作系統自身野指針越界檢查機制，windows下vs系列檢查更嚴格，使用一些強制檢查機制，意義變了也可能會檢查出來。
- 雖然g+＋對于erase迭代器失效檢查時非常雞肋的，但是套在實際場景中，迭代器意義變了，也會出現各種問題，所以我們要有正確處理迭代器失效的方式,比如用函數返回值來更新迭代器。
- windows下vs系列對意義失效的檢查很雙標，由insert函數引起的意義失效檢查不出來，而且可以訪問pos位置，但是由erase函數引起的意義失效卻檢查很嚴格，絲毫不準訪問pos位置。但是Linux平臺下都檢查不出來，都可以訪問pos位置。
二、深淺拷貝問題
1.拷貝構造淺拷貝問題
我們的拷貝構造是存在一定問題的，存在淺拷貝問題，會導致程序崩潰。
// 拷貝構造 v1(v)
// 傳統寫法
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
_start = new T[v.capacity()]; // 開辟一塊和v大小相同的空間
memcpy(_start, v._start, sizeof(T) * v.size()); //error
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
注意：
將容器當中的數據一個個拷貝過來時不能使用memcpy函數，當vector存儲的數據是內置類型或無需進行深拷貝的自定義類型時，使用memcpy函數是沒什么問題的，但當vector存儲的數據是需要進行深拷貝的自定義類型時，使用memcpy函數就會出現問題。例如，當vector存儲的數據是string類的時候。
并且vector當中存儲的每一個string都指向自己所存儲的字符串。
如果此時我們使用的是memcpy函數進行拷貝構造的話，那么拷貝構造出來的vector中每個string的成員變量的值，將與被拷貝的vector中每個string的成員變量的值相同，即兩個vector當中的每個對應的string成員都指向同一個字符串空間。
這顯然不是我們得到的結果，那么所給代碼是如何解決這個問題的呢？
解決辦法：使用for循環把容器v中的數據一個一個拷貝過來。
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
注意：_start[i] = _v[i] 本質是調用string類的賦值運算符重載函數進行深拷貝。
代碼中看似是使用普通的“=”將容器當中的數據一個個拷貝過來，實際上是調用了所存元素的賦值運算符重載函數，而string類的賦值運算符重載函數就是深拷貝，所以拷貝結果是這樣的：
代碼修改如下：
// 拷貝構造 v1(v)
// 傳統寫法
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
_start = new T[v.capacity()]; // 開辟一塊和v大小相同的空間
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
//memcpy(_start, v._start, sizeof(T) * v.size()); //error
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
總結一下： 如果vector當中存儲的元素類型是內置類型（int）或淺拷貝的自定義類型（Date），使用memcpy函數進行進行拷貝構造是沒問題的，但如果vector當中存儲的元素類型是深拷貝的自定義類型（string），則使用memcpy函數將不能達到我們想要的效果。
2.擴容淺拷貝問題
接下來用先前模擬實現的vector來測試楊輝三角以此來解釋我們的深淺拷貝問題，由于楊輝三角不太好理解，還是換個簡單點的：
namespace vector_realize
{
/* class Solution {
public:
// 核心思想：找出楊輝三角的規律，發現每一行頭尾都是1，中間第[j]個數等于上一行[j-1]+[j]
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);// 先開辟楊輝三角的空間
for (size_t i = 0; i < vv.size(); ++i)
{
vv[i].resize(i + 1, 0);
vv[i][0] = vv[i][vv[i].size() - 1] = 1;// 每一行的第一個和最后一個都是1
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
if (vv[i][j] == 0)
{
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
}
}
}
return vv;
}
};
void test_vector9()
{
vector<vector<int>> vvRet = Solution().generate(5);
for (size_t i = 0; i < vvRet.size(); ++i)
{
for (size_t j = 0; j < vvRet[i].size(); ++j)
{
cout << vvRet[i][j] << " ";
}
cout << endl;
}
cout << endl;
}*/
vector<vector<int>> vv;
vector<int> v(5, 1);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
for (size_t i = 0; i < vv.size(); i++)
{
for (size_t j = 0; j < vv[i].size(); j++)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
運行結果：
這里如果我只插入4個元素就不會發生報錯，所以關鍵就在插入第五個元素改變了什么？改變容量，因為我們擴容的代碼有問題。
把擴容的代碼給出：
//reserve擴容
void reserve(size_t n)
{
int oldSize = size();
if (capacity() < n)
{
// 1.開辟新空間
T* tmp = new T[n];
if (_start)
{
//2.拷貝元素
memcpy(tmp, _start, sizeof(T) * size());
//3. 釋放舊空間
delete[] _start;
}
_start = tmp;
}
// 這里_start的地址變了，而_finish還是原來的位置
//_finish = _start + size(); error
_finish = _start + oldSize;
_endofstorage = _start + n;
}
分析如下：
這里出錯的原因在于擴容，錯在擴容時調用的memcpy是淺拷貝，導致先前存儲的數據被memcpy后再delete就全刪掉變成隨機值了。vector調用析構函數析構掉原來的對象，每個對象又調用自身的析構函數，把指向的空間釋放掉，然后就會出現隨機值。
畫圖演示上述測試用例的原因：
總結：
- vector中，當T設計深淺拷貝的類型時，如：string/vector等等，我們擴容使用memcpy拷貝數據是存在淺拷貝問題。
- memcpy是內存的二進制格式拷貝，將一段內存空間中內容原封不動的拷貝到另外一段內存空間中。
- 如果拷貝的是自定義類型的元素，memcpy即高效又不會出錯，但如果拷貝的是自定義類型元素，并且自定義類型元素中涉及到資源管理時，就會出錯，因為memcpy的拷貝實際是淺拷貝。
解決方案：
reserve擴容時不使用memcpy，改成for循環來解決：
//reserve擴容
void reserve(size_t n)
{
int oldSize = size();
if (capacity() < n)
{
// 1.開辟新空間
T* tmp = new T[n];
if (_start)
{
//2.拷貝元素
// 這里直接用memcpy會有問題，發生淺拷貝
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i]; // 本質調用賦值運算符重載進行深拷貝
}
//3. 釋放舊空間
delete[] _start;
}
_start = tmp;
}
// 這里_start的地址變了，而_finish還是原來的位置
//_finish = _start + size(); error
_finish = _start + oldSize;
_endofstorage = _start + n;
}
分析：這里使用for循環，看似是使用普通的“=”將容器當中的數據一個個拷貝過來，實際上是調用了所存元素的賦值運算符重載函數，而vector的賦值運算符重載函數就是深拷貝，所以拷貝過程是這樣的：
使用這種方式就能完美避免上述問題，我們運行試一下：
總結：
原文鏈接：https://blog.csdn.net/m0_64224788/article/details/128283755
相關推薦
- 2022-05-02 Numpy中創建數組的9種方式小結_python
- 2023-01-02 詳解LeakCanary分析內存泄露如何實現_Android
- 2022-08-30 C語言例題講解指針與數組_C 語言
- 2022-12-05 TensorFlow中關于tf.app.flags命令行參數解析模塊_python
- 2022-02-03 ionic 富文本編輯樣式后，前臺不能回顯樣式
- 2021-11-01 redux工作原理講解及使用方法_React
- 2022-05-06 mac goland 常用快捷鍵
- 2022-11-03 淺析C++淺拷貝與深拷貝的聯系和區別_C 語言
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速