C語言數據結構之vector底層實現機制解析
一、vector底層實現機制刨析
通過分析 vector 容器的源代碼不難發(fā)現，它就是使用 3 個迭代器（可以理解成指針）來表示的：
其中statrt指向vector 容器對象的起始字節(jié)位置；
finish指向當前最后一個元素的末尾字節(jié)
end_of指向整個 vector 容器所占用內存空間的末尾字節(jié)。
如圖 演示了以上這 3 個迭代器分別指向的位置
如圖 演示了以上這 2個迭代器分別指向的位置
在此基礎上，將 3 個迭代器兩兩結合，還可以表達不同的含義，例如：
start 和 finish 可以用來表示 vector 容器中目前已被使用的內存空間；
finish 和 end_of可以用來表示 vector 容器目前空閑的內存空間；
start和 end_of可以用表示 vector 容器的容量。
二、vector的核心框架接口的模擬實現
1.vector的迭代器實現
typedef T* Iteratot;
typedef T* const_Iteratot;
Iteratot cend()const {
return final_end;
}
Iteratot cbegin()const {
return start;
}
Iteratot end() {
return final_end;
}
Iteratot begin() {
return start;
}
vector的迭代器是一個原生指針,他的迭代器和String相同都是操作指針來遍歷數據：
- begin()返回的是vector 容器對象的起始字節(jié)位置；
- end()返回的是當前最后一個元素的末尾字節(jié)；
2.reserve()擴容
void reserve(size_t n) {
if (n > capacity()) {
T* temp = new T [n];
//把statrt中的數據拷貝到temp中
size_t size1 = size();
memcpy(temp, start, sizeof(T*) * size());
start = temp;
final_end = start + size1;
finally = start + n;
}
}
當 vector 的大小和容量相等（size==capacity）也就是滿載時，如果再向其添加元素，那么 vector 就需要擴容。vector 容器擴容的過程需要經歷以下 3 步：
- 完全棄用現有的內存空間，重新申請更大的內存空間；
- 將舊內存空間中的數據，按原有順序移動到新的內存空間中；
- 最后將舊的內存空間釋放。
這也就解釋了，為什么 vector 容器在進行擴容后，與其相關的指針、引用以及迭代器可能會失效的原因。
由此可見，vector 擴容是非常耗時的。為了降低再次分配內存空間時的成本，每次擴容時 vector 都會申請比用戶需求量更多的內存空間（這也就是 vector 容量的由來，即 capacity>=size），以便后期使用。
vector 容器擴容時，不同的編譯器申請更多內存空間的量是不同的。以 VS 為例，它會擴容現有容器容量的 50%。
使用memcpy拷貝問題
reserve擴容就是開辟新空間用memcpy將老空間的數據拷貝到新開空間中。
假設模擬實現的vector中的reserve接口中，使用memcpy進行的拷貝，以下代碼會發(fā)生什么問題？
int main()
{
bite::vector<bite::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
問題分析:
- memcpy是內存的二進制格式拷貝，將一段內存空間中內容原封不動的拷貝到另外一段內存空間中
- 如果拷貝的是自定義類型的元素，memcpy即高效又不會出錯，但如果拷貝的是自定義類型元素，并且自定義類型元素中涉及到資源管理時，就會出錯，因為memcpy的拷貝實際是淺拷貝。
結論：如果對象中涉及到資源管理時，千萬不能使用memcpy進行對象之間的拷貝，因為memcpy是淺拷貝，否則可能會引起內存泄漏甚至程序崩潰。
3.尾插尾刪(push_back(),pop_back())
void push_back(const T&var) {
if (final_end ==finally) {
size_t newcode = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcode);
}
*final_end = var;
++final_end;
void pop_back() {
final_end--;
}
插入問題一般先要判斷空間是否含有閑置空間，如果沒有，就要開辟空間。我們final_end==finally來判斷是否含有閑置空間。如果容器含沒有空間先開辟4字節(jié)空間，當滿了后開2capacoity()空間。在final_end部插入數據就行了。對final_end加以操作。
4.對insert()插入時迭代器失效刨析
Iteratot insert(Iteratot iterator,const T&var) {
assert(iterator <= final_end && iterator >= start);
size_t pos = iterator - start;
if (final_end == finally) {
size_t newcode = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcode);
}
//插入操作
auto it = final_end;
while (it >= start+pos) {
*(it+1)=*it;
it--;
}
*iterator = var;
final_end++;
return iterator;
}
假設這是一段vector空間要在pos插入數據，但是剛剛好final_end和final在同一位置，這個容器滿了，要對這這個容器做擴容操作。首先對開辟和這個空間的2唄大小的空間
接著把老空間數據拷貝到新空間中釋放老空間。
由于老空間釋放了pos指向的內存不見了。pos指針就成了野指針。
這如何解決呢就是在老空間解決之間保存這個指針，接著讓他重新指向新空間的原來位置。
而insert()函數返回了這個位置迭代器這為迭代器失效提供了方法，這個方法就是重新賦值。讓這個指針重新指向該指向的位置。
5.對erase()數據刪除時迭代器失效刨析
Iteratot erase(Iteratot iterator) {
assert(iterator <= final_end && iterator >= start);
auto it = iterator;
while (it <final_end) {
*it = *(it+1);
it++;
}
final_end--;
return iterator;
}
vector使用erase刪除元素，其返回值指向下一個元素，但是由于vector本身的性質（存在一塊連續(xù)的內存上），刪掉一個元素后，其后的元素都會向前移動，所以此時指向下一個元素的迭代器其實跟剛剛被刪除元素的迭代器是一樣的。
以下為解決迭代器失效方案：
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int a[] = {1, 4, 3, 7, 9, 3, 6, 8, 3, 3, 5, 2, 3, 7};
vector<int> vector_int(a, a + sizeof(a)/sizeof(int));
/*方案一*/
// for(int i = 0; i < vector_int.size(); i++)
// {
// if(vector_int[i] == 3)
// {
// vector_int.erase(vector_int.begin() + i);
// i--;
// }
// }
/*方案二*/
// for(vector<int>::iterator itor = vector_int.begin(); itor != vector_int.end(); ++itor)
// {
// if (*itor == 3)
// {
// vector_int.erase(itor);
// --itor;
// }
// }
/*方案三*/
vector<int>::iterator v = vector_int.begin();
while(v != vector_int.end())
{
if(*v == 3)
{
v = vector_int.erase(v);
cout << *v << endl;
}
else{
v++;
}
}
/*方案四*/
// vector<int>::iterator v = vector_int.begin();
// while(v != vector_int.end())
// {
// if(*v == 3)
// {
// vector_int.erase(v);
// }
// else{
// v++;
// }
// }
for(vector<int>::iterator itor = vector_int.begin(); itor != vector_int.end(); itor++)
{
cout << * itor << " ";
}
cout << endl;
return 0;
}
一共有四種方案。
方案一表明vector可以用下標訪問元素，顯示出其隨機訪問的強大。并且由于vector的連續(xù)性，且for循環(huán)中有迭代器的自加，所以在刪除一個元素后，迭代器需要減1。
方案二與方案一在迭代器的處理上是類似的，不過對元素的訪問采用了迭代器的方法。
方案三與方案四基本一致，只是方案三利用了erase()函數的返回值是指向下一個元素的性質，又由于vector的性質（連續(xù)的內存塊），所以方案四在erase后并不需要對迭代器做加法。
以上就是C語言數據結構之vector底層實現機制解析的詳細內容，更多關于C語言 vector底層機制的資料請關注腳本之家其它相關文章！
相關文章
有時候需要類的一些成員與類本身相關聯，而不是與類的每個對象相關聯。比如類的所有對象都要共享的變量，這個時候我們就要用到類的靜態(tài)成員，今天通過實例代碼給大家詳細介紹，需要的朋友參考下吧2021-07-07
這篇文章主要給大家介紹了關于C++11中union的使用方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-09-09
這篇文章主要介紹了如何使用C++實現LINUX守護進程，文中代碼非常詳細，供大家學習參考，感興趣的小伙伴可以了解下2020-06-06
本文主要介紹了C++ list-map鏈表與映射表的簡單使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-05-05
Cocos2d-x UI開發(fā)之CCControlSlider控件類使用實例
這篇文章主要介紹了Cocos2d-x UI開發(fā)之CCControlSlider控件類使用實例,本文代碼中包含大量注釋講解了CCControlSlider控件類的使用,需要的朋友可以參考下2014-09-09
這篇文章主要為大家詳細介紹了QT實現TCP網絡聊天室，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了C++計算中國農歷的深入淺析，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-05-05
歸并排序是比較穩(wěn)定的排序方法。它的基本思想是把待排序的元素分解成兩個規(guī)模大致相等的子序列。本文將用C++實現這一排序算法，需要的可以參考一下2022-09-09
這篇文章主要為大家詳細介紹了C語言實現哈夫曼樹，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
這篇文章主要為大家介紹了C語言如何用順序棧來實現回文序列的判斷，文中含有詳細的代碼示例及分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-10-10