C++中vector迭代器失效與深淺拷貝問題詳析

Posted on by

一、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.擴容導致野指針

我們給出兩組測試用例如下：

image-20221210163325836

我們發現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，可是測試結果確是如下：

這裡發生瞭斷言錯誤，這段代碼發生瞭兩個錯誤：

  1. 和上面的錯誤一樣，首先it是指向原來的空間，當insert插入新元素時會發生擴容，原來的舊數據被拷貝到瞭新空間上，並且釋放舊空間，這也就意味著舊空間已經被操作系統回收，而it一直是指向舊空間的，隨後遍歷it時就非法訪問野指針，也就失效瞭。形參的改變不會影響實參，即使你內部pos的指向改變瞭，但是並不會影響我外部的it。所以我們仍然無法通過it去訪問元素。
  2. 為瞭解決上面的錯誤，有人可能會說提前reserve開辟足夠大的空間即可避免發生野指針的現象，但是又出現瞭一個新的問題，看圖：

image-20221210194937971

image-20221210194825202

此時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：

image-20221210225541838

很明顯Linux這裡可以直接訪問，甚至是可以修改。可見不同環境下對待迭代器失效的處理方式是不一樣的，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 << " ";
	}
}

運行結果：

image-20221211151638605

這裡首先在尾插4個數據後，比較瞭下size和capacity的大小，此時是相等的，接下來刪除值為2的數，此時* it就是刪除數字的下一個數據，沒有問題，並且有效數據size也少瞭一個，後續修改*it也沒有問題。

可是當我要刪除值為4的數據呢，再執行上述測試用例會是什麼結果呢？

image-20221211151718980

這裡我總共就有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下：

image-20221211154109695

很明顯看出Linux下對於迭代器失效的檢查就松懈很多，不會報錯。

結論如下：

  1. erase(pos)以後pos失效瞭，pos的意義變瞭，但是在不同平臺下面對於訪問pos的反應是不一樣的，我們用的時候要以失效的角度去看待此問題。
  2. 對於insert和erase造成迭代器失效問題，linux的g++平臺檢查並不是很嚴格，基本靠操作系統本身野指針越界檢查機制。windows下VS系列檢查更嚴格一些，使用一些強制檢查機制，意義變瞭可能會檢查出來。
  3. 雖然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下用官方庫去測試會三組數據都崩潰：

image-20221211004903014

而Linux下的結果如下：

image-20221211003242304

畫圖演示錯誤過程：

image-20221211003147185

原因分析：

毫無疑問上訴代碼會崩潰，因為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、迭代器指向的位置意義變瞭

系統越界機制檢查，不一定能檢查到；編譯實現機制檢查，相對靠譜。

總結：

  1. 對於insert和erase造成迭代器失效問題，linux g++平臺檢查很松懈，基本依靠操作系統自身野指針越界檢查機制，windows下vs系列檢查更嚴格，使用一些強制檢查機制，意義變瞭也可能會檢查出來。
  2. 雖然g+＋對於erase迭代器失效檢查時非常雞肋的，但是套在實際場景中，迭代器意義變瞭，也會出現各種問題，所以我們要有正確處理迭代器失效的方式,比如用函數返回值來更新迭代器。
  3. 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都指向自己所存儲的字符串。

image-20221211230130182

如果此時我們使用的是memcpy函數進行拷貝構造的話，那麼拷貝構造出來的vector中每個string的成員變量的值，將與被拷貝的vector中每個string的成員變量的值相同，即兩個vector當中的每個對應的string成員都指向同一個字符串空間。

image-20221211225603459

這顯然不是我們得到的結果，那麼所給代碼是如何解決這個問題的呢？

解決辦法：使用for循環把容器v中的數據一個一個拷貝過來。

for (size_t i = 0; i < v.size(); i++)
{
	_start[i] = v[i];
}

註意：_start[i] = _v[i] 本質是調用string類的賦值運算符重載函數進行深拷貝。

代碼中看似是使用普通的“=”將容器當中的數據一個個拷貝過來，實際上是調用瞭所存元素的賦值運算符重載函數，而string類的賦值運算符重載函數就是深拷貝，所以拷貝結果是這樣的：

image-20221211225213846

代碼修改如下：

// 拷貝構造 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調用析構函數析構掉原來的對象，每個對象又調用自身的析構函數，把指向的空間釋放掉，然後就會出現隨機值。

畫圖演示上述測試用例的原因：

image-20221212012506593

總結：

  1. vector中，當T設計深淺拷貝的類型時，如：string/vector等等，我們擴容使用memcpy拷貝數據是存在淺拷貝問題。
  2. memcpy是內存的二進制格式拷貝，將一段內存空間中內容原封不動的拷貝到另外一段內存空間中。
  3. 如果拷貝的是自定義類型的元素，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的賦值運算符重載函數就是深拷貝，所以拷貝過程是這樣的：

image-20221212012253102

使用這種方式就能完美避免上述問題，我們運行試一下：

image-20221212012955763

總結：

我們析構舊空間的時候，析構的是對象數組，每個數組調用自身的析構函數，會析構數組的空間。我們用memcpy淺拷貝時，拷貝的臨時對象和原來的對象指向同一塊空間，所以舊空間被銷毀後，我們擴容的新空間中的前4個對象變成野指針，訪問的數據都是隨機值。我們用for循環調用vector的賦值運算符重載可以將舊空間的數據拷貝到新空間，這樣析構舊空間就不會影響新空間。

推薦閱讀：