一、vector迭代器失效問題

1. insert迭代器失效

上文我們寫了insert的模擬實現(xiàn)，最開始的版本是有許多Bug的，比如迭代器失效，最后經(jīng)過優(yōu)化修改實現(xiàn)了insert，這里我們以最初的版本為例，分析并解決迭代器失效問題。如下：

void insert(iterator pos, const T& x)
{
	//檢測參數(shù)合法性
	assert(pos >= _start);
    assert(pos <= _finish);
	//檢測是否需要擴容
	if (_finish == _endofstorage)
	{
		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapcacity);
	}
	//挪動數(shù)據(jù)
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	//插入指定的數(shù)據(jù)
	*pos = x;
	_finish++;
}

insert的迭代器失效分為兩大類：

1.1.擴容導致野指針

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

我們發(fā)現(xiàn)push_back尾插4個后調(diào)用insert會出現(xiàn)隨機值，而push_back尾插5個后調(diào)用insert就沒有問題。

這里我們就不墨跡了，問題就是擴容導致pos迭代器失效，原因在于pos沒有更新，導致非法訪問野指針。

上述當尾插4個數(shù)字后，再頭插一個數(shù)字，發(fā)生擴容，根據(jù)reserve擴容機制，_ start和_ finish都會更新，但是這個插入的位置pos沒有更新，此時pos依舊執(zhí)行舊空間，再者reserve后會釋放舊空間，此時的pos就是野指針，導致*pos = x就是對非法訪問野指針。因為pos迭代器沒有更新，所以后續(xù)挪動數(shù)據(jù)并沒有實現(xiàn)，而插入數(shù)據(jù)是對釋放的空間進行操作，同樣沒有意義。這也就是說不論你在哪個位置插入，都沒有效果。

解決辦法：

可以通過創(chuàng)建變量n來計算擴容前pos迭代器（指針）位置和_ start迭代器（指針）位置的相對距離，最后在擴容后，讓_start再加上先前算好的相對距離n就是更新后的pos指針的位置了。

修正如下：

void insert(iterator pos, const T& x)
{
	//檢測參數(shù)合法性
	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的位置
	}
	//挪動數(shù)據(jù)
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	//插入指定的數(shù)據(jù)
	*pos = x;
	_finish++;
}

此時的迭代器失效已經(jīng)解決了一部分，當然還存在一個迭代器失效問題，見下文：

1.2.迭代器指向位置意義改變

比如現(xiàn)在我要在所有的偶數(shù)前面 插入2，可是測試結(jié)果確是如下：

這里發(fā)生了斷言錯誤，這段代碼發(fā)生了兩個錯誤：

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

此時insert以后雖然沒有擴容，it也沒有成為野指針，但是it指向位置意義變了，每插入一個數(shù)據(jù)，it就指向插入數(shù)據(jù)的下一個數(shù)據(jù)，導致我們這個程序重復插入20。

解決辦法：

給insert函數(shù)加上返回值即可解決，返回指向新插入元素的位置。

iterator insert(iterator pos, const T& x)
{
	//檢測參數(shù)合法性
	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的位置
	}
	//挪動數(shù)據(jù)
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	//插入指定的數(shù)據(jù)
	*pos = x;
	_finish++;

    return pos;
}

我們調(diào)用函數(shù)模塊也得改動，讓it自己接收insert后的返回值：

//在所有的偶數(shù)前面插入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：

針對于擴容發(fā)生野指針類的迭代器失效，VS官方庫是直接斷言報錯。把相同的代碼放到Linux的g++下面試試看呢？

Linux：

很明顯Linux這里可以直接訪問，甚至是可以修改。可見不同環(huán)境下對待迭代器失效的處理方式是不一樣的，windows下更加嚴格，Linux下比較佛系。

2. erase迭代器失效

和insert函數(shù)一樣，erase同樣會存在迭代器失效問題，這里先給出erase模擬實現(xiàn)的代碼，存在一些問題：

// 返回刪除數(shù)據(jù)的下一個數(shù)據(jù)
// 方便解決:一邊遍歷一邊刪除的迭代器失效問題
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的失效都是意義變了，或者不在有效訪問數(shù)據(jù)的有效范圍內(nèi)
• 一般不會使用縮容的方案，那么erase的失效，一般也不存在野指針的失效

2.1.迭代器失效指向位置意義改變

現(xiàn)在要對如下代碼進行測試：

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 << " ";
	}
}

運行結(jié)果：

這里首先在尾插4個數(shù)據(jù)后，比較了下size和capacity的大小，此時是相等的，接下來刪除值為2的數(shù)，此時* it就是刪除數(shù)字的下一個數(shù)據(jù)，沒有問題，并且有效數(shù)據(jù)size也少了一個，后續(xù)修改*it也沒有問題。

可是當我要刪除值為4的數(shù)據(jù)呢，再執(zhí)行上述測試用例會是什么結(jié)果呢？

這里我總共就有4個數(shù)字，按理說把最后一個數(shù)字刪去后，有效數(shù)字只有1、2、3，這里應(yīng)該不存在訪問最后一個值的現(xiàn)象，但是此結(jié)果確實是刪掉4后又訪問了4，離譜的是還修改了4為5，這就是erase典型的迭代器失效。因為你空間還沒有縮容，刪掉的4還存在，導致最終還能夠被訪問。

總結(jié)：

可見代碼確實是實現(xiàn)了刪除，但是程序訪問出現(xiàn)問題，原因就是erase后pos失效了，pos的意義變了，（但是在不同平臺下對于訪問pos的反應(yīng)是不一樣的，因此我們使用的時候要特別小心，統(tǒng)一以失效的角度去看待）。但如果不訪問pos指向的內(nèi)容就不會出問題。比如我們沒有訪問v.end()。

2.2.windows下VS中標準庫和Linux下g++中標準庫對erase迭代器失效的處理

這里我們以如上程序進行對比vs和g++標準庫對erase迭代器失效的處理：

VS下：

VS環(huán)境下檢查非常嚴格， 直接強制檢查斷言錯誤。

Linux下：

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

結(jié)論如下：

1. erase(pos)以后pos失效了，pos的意義變了，但是在不同平臺下面對于訪問pos的反應(yīng)是不一樣的，我們用的時候要以失效的角度去看待此問題。
2. 對于insert和erase造成迭代器失效問題，linux的g++平臺檢查并不是很嚴格，基本靠操作系統(tǒng)本身野指針越界檢查機制。windows下VS系列檢查更嚴格一些，使用一些強制檢查機制，意義變了可能會檢查出來。
3. 雖然g++對于迭代器失效檢查時是并不嚴格，但是套在實際場景中，迭代器意義變了，也會出現(xiàn)各種問題。

總結(jié)：

大家可能發(fā)現(xiàn)我們實現(xiàn)的vector如果不使用std::命名空間封裝的話，結(jié)果和Linux下的結(jié)果一樣。這是因為VS使用的STL標準庫是PJ版本，它檢查更為復雜，實現(xiàn)更為復雜；而我們使用的STL標準庫是SGI版，是Linux的g++編譯器使用的版本，也是侯捷老師的《STL源碼剖析》的版本。它檢查較為松懈，因為這里的迭代器就是原生指針，沒有進行封裝檢查等。

下面分別給出三組測試用例：

• 1 2 3 4
• 1 2 3 4 5
• 1 2 2 3 4 5

void test_vector4()
{
	//刪除所有的偶數(shù)
	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下用官方庫去測試會三組數(shù)據(jù)都崩潰：

而Linux下的結(jié)果如下：

畫圖演示錯誤過程：

原因分析：

毫無疑問上訴代碼會崩潰，因為erase后迭代器it所指向的位置失效，（雖然感覺是可以繼續(xù)使用的，但在vs下就是不可以使用，在Linux下就可以對這個位置進行訪問），所以下面我們用返回值來更新迭代器。

解決方案如下：

給erase加上返回值即可避免問題，返回刪除元素的下一個位置。

修正如下：

// 返回刪除數(shù)據(jù)的下一個數(shù)據(jù)
// 方便解決:一邊遍歷一邊刪除的迭代器失效問題
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;
}

我們調(diào)用函數(shù)模塊也得改動，讓it自己接收erase后的返回值：

void test4()
{
	//刪除所有的偶數(shù)
	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.迭代器失效總結(jié)

vector迭代器失效有2種

1、擴容，導致野指針失效

2、迭代器指向的位置意義變了

系統(tǒng)越界機制檢查，不一定能檢查到；編譯實現(xiàn)機制檢查，相對靠譜。

總結(jié)：

1. 對于insert和erase造成迭代器失效問題，linux g++平臺檢查很松懈，基本依靠操作系統(tǒng)自身野指針越界檢查機制，windows下vs系列檢查更嚴格，使用一些強制檢查機制，意義變了也可能會檢查出來。
2. 雖然g+＋對于erase迭代器失效檢查時非常雞肋的，但是套在實際場景中，迭代器意義變了，也會出現(xiàn)各種問題，所以我們要有正確處理迭代器失效的方式,比如用函數(shù)返回值來更新迭代器。
3. windows下vs系列對意義失效的檢查很雙標，由insert函數(shù)引起的意義失效檢查不出來，而且可以訪問pos位置，但是由erase函數(shù)引起的意義失效卻檢查很嚴格，絲毫不準訪問pos位置。但是Linux平臺下都檢查不出來，都可以訪問pos位置。

二、深淺拷貝問題

1.拷貝構(gòu)造淺拷貝問題

我們的拷貝構(gòu)造是存在一定問題的，存在淺拷貝問題，會導致程序崩潰。

// 拷貝構(gòu)造 v1(v)
// 傳統(tǒng)寫法
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();
}

注意：

將容器當中的數(shù)據(jù)一個個拷貝過來時不能使用memcpy函數(shù)，當vector存儲的數(shù)據(jù)是內(nèi)置類型或無需進行深拷貝的自定義類型時，使用memcpy函數(shù)是沒什么問題的，但當vector存儲的數(shù)據(jù)是需要進行深拷貝的自定義類型時，使用memcpy函數(shù)就會出現(xiàn)問題。例如，當vector存儲的數(shù)據(jù)是string類的時候。

并且vector當中存儲的每一個string都指向自己所存儲的字符串。

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

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

解決辦法：使用for循環(huán)把容器v中的數(shù)據(jù)一個一個拷貝過來。

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

注意：_start[i] = _v[i] 本質(zhì)是調(diào)用string類的賦值運算符重載函數(shù)進行深拷貝。

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

代碼修改如下：

// 拷貝構(gòu)造 v1(v)
// 傳統(tǒng)寫法
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();
}

總結(jié)一下： 如果vector當中存儲的元素類型是內(nèi)置類型（int）或淺拷貝的自定義類型（Date），使用memcpy函數(shù)進行進行拷貝構(gòu)造是沒問題的，但如果vector當中存儲的元素類型是深拷貝的自定義類型（string），則使用memcpy函數(shù)將不能達到我們想要的效果。

2.擴容淺拷貝問題

接下來用先前模擬實現(xiàn)的vector來測試楊輝三角以此來解釋我們的深淺拷貝問題，由于楊輝三角不太好理解，還是換個簡單點的：

namespace vector_realize
{
	/* class Solution {
	public:
        // 核心思想：找出楊輝三角的規(guī)律，發(fā)現(xiàn)每一行頭尾都是1，中間第[j]個數(shù)等于上一行[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;
}

運行結(jié)果：

這里如果我只插入4個元素就不會發(fā)生報錯，所以關(guān)鍵就在插入第五個元素改變了什么？改變?nèi)萘浚驗槲覀償U容的代碼有問題。

把擴容的代碼給出：

//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;
}

分析如下：

這里出錯的原因在于擴容，錯在擴容時調(diào)用的memcpy是淺拷貝，導致先前存儲的數(shù)據(jù)被memcpy后再delete就全刪掉變成隨機值了。vector調(diào)用析構(gòu)函數(shù)析構(gòu)掉原來的對象，每個對象又調(diào)用自身的析構(gòu)函數(shù)，把指向的空間釋放掉，然后就會出現(xiàn)隨機值。

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

總結(jié)：

1. vector中，當T設(shè)計深淺拷貝的類型時，如：string/vector等等，我們擴容使用memcpy拷貝數(shù)據(jù)是存在淺拷貝問題。
2. memcpy是內(nèi)存的二進制格式拷貝，將一段內(nèi)存空間中內(nèi)容原封不動的拷貝到另外一段內(nèi)存空間中。
3. 如果拷貝的是自定義類型的元素，memcpy即高效又不會出錯，但如果拷貝的是自定義類型元素，并且自定義類型元素中涉及到資源管理時，就會出錯，因為memcpy的拷貝實際是淺拷貝。

解決方案：

reserve擴容時不使用memcpy，改成for循環(huán)來解決：

//reserve擴容
void reserve(size_t n)
{
	int oldSize = size();
	if (capacity() < n)
	{
		// 1.開辟新空間
		T* tmp = new T[n];
		if (_start)
		{
			//2.拷貝元素
			// 這里直接用memcpy會有問題，發(fā)生淺拷貝
			//memcpy(tmp, _start, sizeof(T) * size());
			for (size_t i = 0; i < oldSize; i++)
			{
				tmp[i] = _start[i]; // 本質(zhì)調(diào)用賦值運算符重載進行深拷貝
			}
			//3. 釋放舊空間
			delete[] _start;
		}
		_start = tmp;
	}
	// 這里_start的地址變了，而_finish還是原來的位置
	//_finish = _start + size(); error 
	_finish = _start + oldSize;
	_endofstorage = _start + n;
}

分析：這里使用for循環(huán)，看似是使用普通的“=”將容器當中的數(shù)據(jù)一個個拷貝過來，實際上是調(diào)用了所存元素的賦值運算符重載函數(shù)，而vector的賦值運算符重載函數(shù)就是深拷貝，所以拷貝過程是這樣的：

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

總結(jié)：

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

最新評論