鑒于讀者的響應，打算將文章拆分一下，方便觀看，基本接口可看 深入淺出STL之vector類

一、源碼引入

• 以下我所介紹的都是基于【SGI】版本的STL，對源碼有興趣的同學可以去看看 侯捷老師的《STL源碼剖析》

• 然后呢我們就去調出【vector】的一些核心源碼，這里我們主要關注的就是這個使用原生指針value_type*所定義出來的迭代器 iterator
• 然后我們又看到了保護成員：[start]、[finish]、[end_of_stroage]?？吹剿鼈兡闶欠裼邢肫鹞覀冊?模擬string 的時候寫到過的 [a]、[size]、[capacity]；沒錯，它們就存在著一定的對應關系

• 但是呢，只看上面這些成員變量還不夠，我們要將其帶入到具體的場景中，例如下面有兩個接口分別為【尾插】和【擴容】，對于push_back()封裝得沒有那么厲害，讀者結合下面的圖應該就能看得懂，分別就是 未滿追加的邏輯和已滿擴容的邏輯
• 那對于reserve()來說，就是一個擴容的邏輯，【allocate_and_copy】是開辟和拷貝空間，那【deallocate】就是釋放空間。在擴完容之后不要忘了去對三個成員變量做更新，這一塊的模擬實現(xiàn)我在下面馬上就會講到

• 最后的話我們再來看看 構造函數(shù)construct和析構函數(shù)destroy，光看代碼，不知你是否回憶起了我們曾經(jīng)在 C/C++內存管理 中有講到【定位new】這個概念，而且提到了 內存池 這個概念
• 其實我們在調用構造函數(shù)的時候，都是通過【空間適配器】在 內存池 中開出空間；那在出了作用域之后這些所開的空間都要銷毀了，所以就會去調用析構函數(shù)完成釋放

?? 對于上面的這些源碼呢，讀者可以在學習了STL一段時間后，配合侯捷老師的《STL源碼剖析》再去展開閱讀，因為考慮到讀者的基礎，就不在繼續(xù)深入講解了~

二、模擬實現(xiàn)

然后我們就來模擬實現(xiàn)一下【vector】中的各種接口

• 還是一下，我們先簡述一下整體的架構。這個vector類還是包在【bit】這個命名空間中，而對于這個類而言，我要將其定義為一個 模版類，這一塊如果還有同學不太熟悉的話可以去看看 C++模版
• 其他部分可以看到迭代器我定義的就是原生指針類型，然后將[_start]、[_finish]、[_end_of_storage]也定義為了三個迭代器類型，并且采用提前聲明的形式將它們都初始化為nullptr，這樣當我們后面在寫 構造函數(shù)和析構函數(shù) 的時候就不需要再去做初始化了

namespace bit {
	template<class T>
	class vector {
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
	// 主要接口函數(shù)
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
}

1、迭代器

• 首先的話簡單一點，來實現(xiàn)一下迭代器，分為非const版本和const版本

iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

const_iterator begin()  const
{
	return _start;
}

const_iterator end()	const
{
	return _finish;
}

2、容量

• 然后我們來講講容量相關的接口，首先的話就是【size】和【capacity】這兩個接口

size_t size()
{
	return _finish - _start;
}

size_t capacity()
{
	return _end_of_storage - _start;
}

• 對于【size】而言指的是當前這個容器中的數(shù)據(jù)個數(shù)，那也就是我們在上面所講的_start和_finish這兩個迭代器之間的距離，我們之前有說到過迭代器它的底層其實就是指針，那要計算出兩個指針之間的數(shù)據(jù)個數(shù)的話讓它們做一個相減_finish - _start
• 那對于整個容器的容量【capacity】來說，即為_end_of_storage - _start。讀者通過下圖便可一目了然地看出來

• 然后呢再來說說擴容這一塊的接口【reserve】，首先在一進來的時候我們要去做一個判斷，只有當所傳入的值要比原先的capacity()來得大的時候，我們才去執(zhí)行一個擴容的邏輯，在內部的擴容邏輯中可以看到我們使用到了前面所定義的模版參數(shù)T，這樣去寫的話就可以根據(jù)不同的類型參數(shù)開出不同的空間
• 接下去我們所執(zhí)行的就是拷貝的邏輯，采取到的是內存函數(shù)memcpy()，拷貝完后再去釋放原空間，接下去把這些成員變量去做一個更新即可

看著邏輯很清晰，但是呢下面的代碼存在著非常多的漏洞

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];		// 開一塊新空間
		if (_start)
		{
			memcpy(tmp, _start, sizeof(T) * size());
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + size();
		_end_of_storage = _start + n;
	}
}

• 我們這里再寫一個push_back的接口（后面講），讓代碼先跑起來

void push_back(const T& x)
{
	if (_finish == _end_of_storage)
	{
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	*_finish = x;
	_finish++;
}

??第一輪測試 — 空指針異常

下面是測試的代碼

void test_vector1()
{
	bit::vector<int> v;

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

• 但是呢在運行起來后卻發(fā)現(xiàn)程序出現(xiàn)了崩潰，這是為什么呢？

• 按下【F5】以調試的方式運行起來就可以發(fā)現(xiàn)有地方出現(xiàn)了 空指針異常

• 進一步，我們通過【調試窗口】再來看看，很明顯得就看到這個_finish的值為【0x00000000】

• 知道了問題所在，接下去我們就通過調試一步步地來看。雖然這個代碼是崩在191，但是呢其實真正的問題還是出在【reserve】這個擴容的邏輯中，隨著我們一步一步地去看，可以看到_start和_end_of_storage這兩個都沒什么問題，但是_finish就是沒有什么變化，所以呢我們可以鎖定到下面這句話

_finish = _start + size();

• 此時就需要去看看這個【size】了，之前我們使用的是_finish - _start來計算的 size()，在執(zhí)行這句話時_start已經(jīng)發(fā)生了改變，因為我們去開出了一塊新的空間，但是這時_finish的值還是一開始的【nullptr】，那么這個 size() 最后計算出來的大小即為 -_start，此時再和_start去做一個結合的話即為 0

?? 所以，上述就是為什么這個_finish的值為【0x00000000】原因，那我們要如何去修改呢？

• 首先第一種解決方案，就是先去更新這個_finish，用開出空間的 tmp 去做一個更新，然后再用 tmp 去更新_start，這樣就不會出現(xiàn)問題了

_finish = tmp + size();
_start = tmp;
_end_of_storage = _start + n;

• 通過調試來觀察看看就發(fā)現(xiàn)確實不為空了

?? 但是呢上面這種方案的話可能你的徒弟在維護你的代碼的時候就會覺得很奇怪，又給改回去了，導致原先的問題再度發(fā)生，所以我們可以采取下面這種策略

• 我們可以在每次沒開始擴容之前我們都可以去事先保存一下這個 size()，后面的更新順序就不需要發(fā)生變動了，在加的時候加上sz即可

if (n > capacity())
{
	// 先保存一下原先的size()
	size_t sz = size();
	T* tmp = new T[n];		// 開一塊新空間
	if (_start)
	{
		memcpy(tmp, _start, sizeof(T) * size());
		delete[] _start;
	}
	_start = tmp;
	_finish = _start + sz;
	_end_of_storage = _start + n;
}

• 通過調試再來看到確實也可以起到同樣的效果

?? 但是呢這還沒完，【reserve】接口還是存在問題

??第二輪測試 — memcpy的拷貝問題

• 下面是我們要進行第二輪測試的代碼，內部類型使用的是 string類

void test_vector2()
{
	bit::vector<string> v;

	v.push_back("11111");
	v.push_back("22222");
	v.push_back("33333");
	v.push_back("44444");

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

• 運行起來看并沒有什么問題

• 但是呢當我再去push_back("55555")的時候程序卻出現(xiàn)了問題

?? 那此時有的同學腦子轉得很快，感覺到一定是【reserve】擴容的地方出現(xiàn)了問題

• 于是經(jīng)過我們的排查，先定位到了這一句，有同學就覺得是不是因為每次sizeof(T)的對象大小不一樣了?

memcpy(tmp, _start, sizeof(T) * size());

我覺得上述這個老鐵提出來的問題非常好，我們一起來看看。請讀者思考一下下面的結果是多少

void test_vector3()
{
	string s1("11111");
	string s2;
	string s3("222222222222222222");

	cout << sizeof(s1) << endl;
	cout << sizeof(s2) << endl;
	cout << sizeof(s3) << endl;
}

• 如果有閱讀過 深入淺出STL之string類 的同學一定可以知道在VS下對于每個string對象的大小都是固定死的，均為 28B，即使是通過不同的構造形式構造出來的對象也是一樣的

接下去呢，就帶讀者好好地通過調試觀察一下??

v.push_back("1111111111111111");
v.push_back("2222222222222222");
v.push_back("3333333333333333");
v.push_back("4444444444444444");
v.push_back("5555555555555555");

• 如果對深淺拷貝這一塊比較了解的同學一定可以知曉這里很明顯地發(fā)生了一個 淺拷貝 的問題，所以導致在delete[] _start的時候發(fā)生了一個 并發(fā)修改 的問題

• 這就導致了我們在釋放原本的這塊空間時導致拷貝后的這塊空間也造成了另一塊空間的問題

可能有的讀者還是不太理解這其中的原理，我們通過畫圖再來看看

• 可以看到，在擴容的時候我們去開出了一塊新的空間，然后使用memcpy()將數(shù)據(jù)原封不動地拷貝到了另一塊空間中，再去做了一個擴容，那在上面我們也看到過了，就是因為這個memcpy()原封不動拷貝的問題，就使得新空間和舊空間雖然是兩塊獨立的空間，但是呢每個對象中的_str都和另一個對象指向了那一塊同樣的空間

• 那么在接下去在執(zhí)行這句代碼的時候就會先去調用當前對象的析構函數(shù)將每一塊空間中的內容先清理掉，然后再去調用delete釋放掉整塊空間。因為每兩個對象所指向的空間都是同一塊的，所以在釋放的時候就會造成同時修改的問題

delete[] _start;

【總結一下】：

vector是深拷貝，但是vector空間上存的對象是string的數(shù)組，使用memcpy()導致string對象的淺拷貝

那我們要如何去避免這一種問題呢？

• 很簡單，我們去換一下這個拷貝的邏輯就可以了，不要使用memcpy()去進行淺拷貝，而是使用下面這種形式去進行拷貝
• 對于tmp[i] = _start[i]如果對代碼比較敏感的同學應該可以很快地看出這會去調用 string類 的賦值重載，然后去做一個深拷貝，此時就不會造成兩個_str指向同一塊空間了

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

• 最后通過調試再來觀察一下??

以下就是【reserve】這個接口的最終完整版實現(xiàn)邏輯

void reserve(size_t n)
{
	if (n > capacity())
	{
		// 先保存一下原先的size()
		size_t sz = size();
		T* tmp = new T[n];		// 開一塊新空間
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T) * size());
			for (size_t i = 0; i < size(); i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

接下去的話我們再來看看【resize】這個接口該如何去實現(xiàn)

• 還是一樣分為三類來進行討論：
  • 一個是n < _finish的情況；
  • 第二個是n > _finish && n <= _end_of_storage的情況；
  • 第三個是n >_end_of_storage的情況；
• 對于后兩種情況我們可以做一個合并，使用上面【reserve】去做一個容量的檢查

• 我們來看一下具體的代碼，首先是第一種，直接讓_finish = _start + n即可；如果是另一種情況的話，就先使用【reserve】去檢查一下是否需要擴容，然后再去通過循環(huán)追加對應的數(shù)據(jù)即可

void resize(size_t n, const T& val = T())
{
	if (n < size())
	{
		_finish = _start + n;
	}
	else
	{
		// 先使用reserve()去檢查一下是否需要擴容
		reserve(n);
		while (_finish != _start + n)
		{
			*_finish = val;
			_finish++;
		}
	}
}

• 可能有同學比較好奇這個T()是干嘛的，還記我們在 C++缺省參數(shù) 中所講到的知識點嗎。沒錯，這個T()就是給到的默認缺省參數(shù)，因為當前的形參【val】的類型使用的就是模版參數(shù)類型，采取自動推導的形式去進行自動識別
• 而T()就是我們在 類和對象小知識 中所學習過的【匿名對象】，切記這里不可以給0，因為當前的數(shù)據(jù)類型不一定就是 整型，我們就可以根據(jù)這個匿名對象去生成不同的默認值

const T& val = T()

簡單地來測試一下

3、元素訪問

• 對于元素訪問的話我們最常用的就是下標 + []的形式，這里給出兩種，一個是const版本和非const版本

T& operator[](size_t pos)
{
	assert(pos < size());
	return _start[pos];
}

T& operator[](size_t pos)	const
{
	assert(pos < size());
	return _start[pos];
}

4、修改操作

接下去的話我們來講講有關修改操作的一些接口

• 首先第一個的話就是push_back，這個我在上面講【reserve】的時候給出過，現(xiàn)在仔細地再來講一講：首先的話我們要考慮的就是擴容的邏輯，上面我們有講到在VS下是呈現(xiàn) 1.5倍 的增長趨勢，但是在g++下呈現(xiàn)的則是 2倍 的擴容邏輯，這里的擴容的話我們就交給【reserve】來實現(xiàn)

void push_back(const T& x)
{
	if (_finish == _end_of_storage)
	{
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	*_finish = x;
	_finish++;
}

然后的話我們來實現(xiàn)一下【insert】這個接口

void insert(iterator pos, const T& x)

這一塊的話我們已經(jīng)講過很多遍了，要在某一個位置插入數(shù)據(jù)的話就需要先去挪動部分的數(shù)據(jù)，這里我們從后往前挪，防止造成覆蓋的情況，當數(shù)據(jù)挪動完畢后，再在pos這個位置插入指定的數(shù)據(jù)即可

• 在一進入函數(shù)的時候大家可以去做一個斷言的操作，不過很多同學可能會好奇這邊的pos >= _start，為什么可以位于首部

assert(pos >= _start && pos <= _finish);

?? 在講解 string類 的時候我們確實講到了這種寫法的缺陷，但是讀者要看清楚了，這里pos的類型是 iterator，為一個迭代器。而我們在 string類 中所講到的這個pos呢是一個無符號整數(shù)

• 位于首部的迭代器pos不可能是0，因為它是一段空間的地址，有效空間的地址不可能是0，

string& insert (size_t pos, const string& str);

• 不過呢，既然是插入數(shù)據(jù)的話就一定會存在容量不足的情況，此時就需要一個擴容邏輯，這里我們直接用上面在push_back()接口中所寫的即可

// 1.首先考慮擴容邏輯
if (_finish == _end_of_storage)
{
	size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
	reserve(newCapacity);
}

以下是整體的代碼

void insert(iterator pos, const T& x)
{
	assert(pos >= _start && pos <= _finish);
	// 1.首先考慮擴容邏輯
	if (_finish == _end_of_storage)
	{
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}

	// 2.挪動數(shù)據(jù)
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;
	++_finish;
}

• 那么對于push_back()這個接口我們就可以去復用一下【insert】這個接口了

void push_back(const T& x)
{
	/*if (_finish == _end_of_storage)
	{
		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);
	}
	*_finish = x;
	_finish++;*/
	insert(end(), x);
}

??第三輪測試 — 迭代器失效問題

• 好，在寫完【insert】接口后，我們再來做一個測試?？梢园l(fā)現(xiàn)程序崩潰了

馬上，我們通過調試來觀察一下

• 此時我們已經(jīng)往【v】中插入了4個數(shù)據(jù)，馬上使用insert(v.begin(), 100)去做一個頭插，那么一進到函數(shù)中我們就可以知道這個當前對象的_start和pos所處的迭代器位置是相同的，也就是同一段空間的地址

• 那此時我們知道容器中的空間已經(jīng)滿了，所以會去走一個擴容的邏輯，此時可以看到當前對象this的_start已經(jīng)發(fā)生了改變

• 可以看到，在擴完容之后，當前對象的_start和待插入位置的pos已經(jīng)發(fā)生了變化，那么在此時我們再去挪動數(shù)據(jù)進行插入的時候就會出現(xiàn)問題了

?? 我們可以通過下面的圖示來看看到底這個擴完容之后是怎樣的

• 可以看到_start確實發(fā)生了一個變化，但是呢pos還是指向原來的那個地方。那讀者可以自己去想象一下子在遍歷挪動數(shù)據(jù)的時候究竟何時才是個頭呢？

• 我們可以通過調試再來觀察一下挪動數(shù)據(jù)這段邏輯，可以看到在挪動完幾次數(shù)據(jù)后就出現(xiàn)了隨機值，并且出現(xiàn)了死循環(huán)的問題

?? 以上所出現(xiàn)的這個問題就被稱作是 【迭代器失效的問題】

那我們要如何去解決呢？

?? 有同學說，內部外部無法一起修改的話參數(shù)部分加個引用不就行了

void insert(iterator& pos, const T& x)

• 這其實是不對的，因為有些時候我們所傳遞的迭代器位置是v.begin() + 3，在這中間會去產生一個臨時對象，我們知道臨時對象是具有常性的，那么傳遞進去的時候就會造成【權限放大】的問題

v.insert(v.begin() + 3, 6);

?? 那有同學又說，那防止一下權限放大不就好了，加個const

• 這肯定是不可以的，看到程序依舊會出現(xiàn)問題

• 首先大家要明白的一個點是出錯的根本原因在于：_start的位置改變了但是pos的位置沒有發(fā)生改變。
• 所以我們所要做的一個點就是：讓pos的位置隨著_start的變動而一起變動，這樣就不會出現(xiàn)問題了。以下我們需要改進的代碼部分，在進行擴容之前，我們可以先去計算一下從【_start】到【pos】的位置有多遠；
• 然后呢我們在執(zhí)行完擴容的邏輯之后，就要去更新一下這個【pos】迭代器的位置所在，就使用剛才計算出來的這段距離即可

// 1.首先考慮擴容邏輯
if (_finish == _end_of_storage)
{
	// 首先保存一下從_start到pos的距離
	size_t len = pos - _start;

	size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
	reserve(newCapacity);

	// 再擴完容之后更新一下pos, 解決迭代器失效問題
	pos = _start + len;
}

那代碼做了更新之后迭代器失效的問題真的解決了呢，我們通過調試一起來看看

• 可以看到，通過我們的騷操作??【pos】位置就隨著【start】的變化而隨著變化

• 但是呢就上面這樣還不夠，我們只解決了內部迭代器失效的問題，而外部迭代器失效的問題并沒有很好地解決。
• 外部迭代器，那是什么東西？ 我們來看下這段代碼

bit::vector<int>::iterator it = v.begin();
v.insert(it, 33);
bit::print(v);

cout << *it << endl;

bit::print(v);

可以看到，在使用完這個這個迭代器之后再去訪問就出現(xiàn)了問題

如果直接其換成庫里面的【vector】的話，就直接崩潰了

?? 所以，對于迭代器這一塊我們在使用的時候一定要慎重，在使用完之后不要去輕易地修改它

it = v.insert(it, 33);

• 如何執(zhí)意要進行修改的話也不是沒有辦法，我們只需要在【insert】之后去接受一下當前所操作的這個迭代器的位置即可，記住這個位置，下次在訪問的時候也就不會出問題

具體代碼如下：

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start && pos <= _finish);
	// 1.首先考慮擴容邏輯
	if (_finish == _end_of_storage)
	{
		// 首先保存一下從_start到pos的距離
		size_t len = pos - _start;

		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newCapacity);

		// 再擴完容之后更新一下pos, 解決迭代器失效問題
		pos = _start + len;
	}

	// 2.挪動數(shù)據(jù)
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;
	++_finish;

	return pos;
}

有【insert】，那一定少不了【erase】，我們繼續(xù)來看看

• 對于【erase】來說，我們也是需要先去挪動數(shù)據(jù)的，但是在這里呢我們需要從前往后挪，也是防止造成覆蓋的情況

具體代碼如下：

void erase(iterator pos)
{
	assert(pos >= _start && pos < _finish);

	iterator end = pos + 1;
	// 移動覆蓋
	while (end != _finish)
	{
		*(end - 1) = *end;
		++end;
	}
	--_finish;
}

立馬來測試一下：

?? 對于【insert】來說會存在迭代器失效的問題，那對【erase】來說也會有嗎？

• 我們立馬通過下面的代碼來測試一下

void test_vector8()
{
	bit::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	bit::print(v);

	auto it = v.begin();
	v.erase(it);

	cout << *it << endl;
	it++;
	cout << *it << endl;
	bit::print(v);
}

• 運行起來我們可以看到，并沒有出現(xiàn)任何的問題，首先去刪除了第一個元素，然后再訪問到首個位置便是【2】，接下去再去執(zhí)行it++并訪問的話便是【3】

• 但若是我們將代碼換成下面這樣的話就會出現(xiàn)問題了

auto it = v.begin() + 3;

• 運行起來可以看到，當我們刪除完最后一個元素后再讓迭代器后移，就造成了訪問越界的問題，出現(xiàn)了隨機值的情況

不過呢，上面只是我們使用自己模擬的【vector】，來用用庫里的會看會發(fā)生什么情況

• 但是呢我們可以看到如果使用庫里面的話就會直接造成程序崩潰的問題

?? 上面呢是在VS下的運行結果，之前有說過VS在的STL是【PJ版】，而Linux下則是【SGI版】，所以我們都要去做一個對比

• 可以看到，神奇的事情發(fā)生了~ 在Linux下執(zhí)行同樣的兩段代碼，卻沒有發(fā)生像VS里面那樣的報錯，甚至在訪問越界之后也沒有出現(xiàn)隨機值的問題，而是【0】

【小結】：

erase以后，迭代器失效了，不能訪問。VS進行強制，訪問會直接報錯；Linux下則不會

然后我們再來看一個點

• 下面這個場景是通過迭代器的形式去刪除其中的偶數(shù)

auto it = v.begin();
while(it != v.end())
{
    if(*it % 2 == 0)
    {
		v.erase(it);
    }
    ++it;
}

通過運行結果我們可以看出，確實所有的偶數(shù)都被刪除了

換一個測試用例，我們加一個【2】，然后在刪除的時候就發(fā)現(xiàn)【2】沒有被刪干凈

再換一個測試用例，我在最后加了一個【6】，運行之后發(fā)現(xiàn)報出了Segmentation fault，這是Linux下的段錯誤問題

我們通過畫圖來分析一下

• 首先是對于第二種，根據(jù)代碼來進行走讀，當我們刪除了第一個【2】后，后面的四個元素就往前移動了一個位置，接著迭代器++后移，就來到了【3】的位置，所以就錯過了第2個【2】

• 那對于第三種測試案例，因為最后一個是 偶數(shù) 的原因，所以在刪除之后迭代器進行了后移，此時呢它已經(jīng)是越過了end()的位置，再去判斷的話永遠都到不了，所以就出現(xiàn)了【Segmentation fault】的問題

?? 那要如何去避免呢？

• 這其實很簡單，我們不要讓這個迭代器每次都后移就可以了

auto it = v.begin();
while(it != v.end())
{
    if(*it % 2 == 0)
    {
		v.erase(it);
    }
   	else
    {   
    	++it;
	}
}

再去打印看一下看看就發(fā)現(xiàn)沒什么問題了

• 但是呢這段代碼如果放到VS上去的話就不一樣了，在Linux下確實是不會出現(xiàn)什么問題，但是在VS下還是一樣會直接報錯，因為VS會進行強制檢查，在訪問了一次迭代器之后就不可以再繼續(xù)訪問了

?? 此時我們需要去考慮一下【erase】這個接口的詳情了

• 我們要看的是這個返回值，其返回值是一個迭代器，而且是剛剛被刪除那個元素的下一個位置

iterator erase (const_iterator position);

• 那如果是這樣的話我們就可以考慮在每次刪除完一個位置的數(shù)據(jù)后拿返回值接收一下這個所刪除元素的下一個位置，那么在下一次繼續(xù)訪問的時候就不會造成修改操作的問題了

it = v.erase(it);

最后【erase】接口的整體代碼如下所示：

iterator erase(iterator pos)
{
	assert(pos >= _start && pos < _finish);

	iterator end = pos + 1;
	// 移動覆蓋
	while (end != _finish)
	{
		*(end - 1) = *end;
		++end;
	}
	--_finish;
	return pos;
}

在有了【erase】之后，我們就可以讓pop_back()去復用這個接口了，可以達到尾刪的邏輯

void pop_back()
{
	// 復用erase
	erase(end() - 1);
}

• 最后的話再來講講【swap】這個接口，很簡單，就是去調用庫里面的這個模版函數(shù)swap，去一一交換兩個對象中的三個成員變量即可。這個接口我下面在講【賦值重載】時會使用到

void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}

5、默認成員函數(shù)

講了這么多，終于能來講講默認的成員函數(shù)了

• 首先的話一定是構造函數(shù)，有參構造是一定要實現(xiàn)的，因為這里的邏輯和resize()是類似的，因此我們直接去做一個復用即可

// 有參構造
vector(size_t n, const T& val = T())
{
	resize(n, val);
}

• 那我們在構造的時候就可以去做一個初始化了，發(fā)現(xiàn)和v.resize(10, 0)是同樣的效果

bit::vector<int> v(10, 0);

?? 那有同學可能會問，三個私有成員變量不需要去做初始化嗎？

• 同學，難道你忘了我們在一開始的時候已經(jīng)給到了它們初始值為nullptr嗎？這個措施就是很好地避免編譯器對內置類型不會去做初始化的問題

private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _end_of_storage = nullptr;

• 除了上面這種初始化，我再介紹一種方法：那就是使用 迭代器區(qū)間

• 這里我們可以去使用循環(huán)配合【push_back】接口去做一個初始化

// [first, last)
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

??第四輪測試 — 雙重構造引發(fā)調用歧義

接下去，我們馬上對這個迭代器區(qū)間做的初始化操作去所一個測試

void test_vector6()
{
	bit::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	bit::vector<int> v2(v.begin(), v.end());

	string s("abcdef");
	bit::vector<int> v2(s.begin(), s.end());

	int a[] = { 1,2,3,4 };
	bit::vector<int> v2(a, a + 4);
}

可以看到，除了去初始化自己【vector】對象的迭代器區(qū)間，【string】對象也可以，而且指針也沒問題

?? 但此時呢，如果我再去以下面的有參構造進行初始化的話就會出現(xiàn)一些問題

bit::vector<int> v5(10, 1);

可以看到，說是“非法的間接尋址”

• 這里對迭代器first去進行解引用目的就是為了獲取這個位置上的數(shù)據(jù)，我們在 指針一文 有所提到 只有指針和迭代器可以解引用，基本數(shù)據(jù)類型不能解引用

?? 但是有同學一定會疑惑說：為什么這里不會去匹配有參構造，而是去匹配的迭代器區(qū)間構造呢？

• 在講 C++模版 的時候，我們有說到過模版參數(shù)會去進行自動類型推導，從而匹配最合適函數(shù)模版。因為我們在這里所傳入的【10】和【1】都是int類型，但是呢有參構造的第一個形參類型為size_t，并不是最匹配的
• 而迭代器區(qū)間初始化其參數(shù)類型都是模版參數(shù)，所以在匹配的時候它是最優(yōu)先進行匹配的

那我們該如何去進行預防呢？

• 很簡單，我們可以利用在 C++重載函數(shù) 中所學習的參數(shù)類型不同去另寫一個有參構造的重載形式

vector(size_t n, const T& val = T())
{
	resize(n, val);
}

vector(int n, const T& val = T())
{
	resize(n, val);
}

通過調試我們可以看出這里在調用的時候就沒有歧義了

?? 最后再補充一個小的知識點，作為拓展

• 那我們在寫了這個重載函數(shù)后要如何去調用對應的無符號類型size_t呢，此時我們只需要在傳遞的參數(shù)后加上一個u即可，那么編譯器在進行識別的時候就會自動將其識別成為無符號整數(shù)

bit::vector<int> v6(10u, 6);

一樣通過調試來看就可以很清楚

講完構造函數(shù)了，我們來看看拷貝構造

• 首先讀者要明確為什么要寫拷貝構造，這個我們通過調試來看一下就知道了：很明顯可以看到這里只是做了一個淺拷貝，而不是去做了深拷貝

• 所以我們要自己去實現(xiàn)一個深拷貝，邏輯很簡單，就不贅述

// 拷貝構造
vector(vector<int>& v)
{
	_start = new T[v.capacity()];
	memcpy(tmp, v._start, sizeof(T) * v.size());
	_finish = tmp + v.size();
	_end_of_storage = tmp + v.capacity();
}

• 但是看到上面這個memcpy()，你是否會有一種警惕的心理呢，因為我們上面講到過 vector 對象中存放的是 string數(shù)組，在拷貝的過程中會產生淺拷貝的問題，那就不可以去使用這個memcpy()，具體問題間下圖

• 所以拷貝構造的正確形式應該是下面這樣的

// 拷貝構造
vector(vector<T>& v)
{
	_start = new T[v.capacity()];
	//memcpy(_start, v._start, sizeof(T) * v.size());
	for (size_t i = 0; i < v.size(); i++)
	{
		_start[i] = v._start[i];
	}
	_finish = _start + v.size();
	_end_of_storage = _start + v.capacity();
}

• 可以看到，在改成深拷貝后就不會出現(xiàn)類似的問題了

• 當然我們也可以去做一個投機取巧，復用當前已經(jīng)實現(xiàn)過的接口【reserve】和【push_back】，首先根據(jù)所傳遞進來對象的容量去做一個擴容的邏輯，開出足夠多的空間后再將這個對象中的數(shù)據(jù)一一尾插進當前對象即可

vector(vector<int>& v)
{
	// 根據(jù)v的capacity()去開出對應的空間
	reserve(v.capacity());
	for (size_t i = 0; i < v.size(); i++)
	{
		push_back(v[i]);
	}
}

有了拷貝構造，【賦值重載】也少不了

• 還記得我們在上面所實現(xiàn)過的【swap】接口嗎，在進行 string模擬 的時候，我們又使用到這么一個巧計，那就是使用 傳值傳參，首先會去調用一個拷貝構造構造一個臨時對象，但是臨時對象出了作用域之后肯定是要銷毀的
• 此時我們就可以使用【swap】和當前對象去做一個交換，我呢獲取到了你里面的內容，你幫我釋放了不需要的內容，簡直一舉兩得（還記得PUA弟弟的故事嗎??）

// 賦值重載
const vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

• 好，我們來調試觀察一下。看到在調用賦值重載前就會去 調用拷貝構造

最后的舞臺，給到【析構函數(shù)】，再怎么花里胡哨，最后最后空間都是要還給操作系統(tǒng)的

~vector()
{
	delete[] _start;
	_start = _finish = _end_of_storage = nullptr;
}

OK，以上就是有關vector深度剖析及模擬實現(xiàn)，希望對您有幫助??

文章來源地址http://www.zghlxwxcb.cn/news/detail-629571.html

到了這里，關于【C++】透過STL源碼深度剖析及模擬實現(xiàn)vector的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！