之前對vector的一些功能使用了一下 接下來手動實現一下vector? vector的實現和string還是有不小區別的? ?有很多地方都有細節的問題

不同于string的成員變量一個指針一個size一個capacity的成員變量? vector里面存的是三個迭代器iterator? 這的迭代器其實就是模版T的指針? 這樣就可以存各種類型的數據了

三個指針? statr指向第一個位置 finish指向最后一個元素的后一個位置? end_of_storage指向能存儲容量的后一個位置

因為用到了模版 所以不能分兩個文件來寫 就都寫到vector.h里面

接下來一步步實現vector的功能 在實際的過程中遇到了各種的問題 一步步分析并解決

容量操作

首先先實現簡單的一些容量的接口

size和capacity只需要分別返回finish-start和_end_of_storage? ?empty只需要判斷finish是否等于start

reserve

如果按照string那樣的方式如下圖的方式來寫reserve會出問題

這里的三個成員變量都是指針? 擴容開新空間釋放原來空間之后 需要讓三個成員變量進行更新 _start和_end_of_storage按照上面寫的沒有什么問題? 但是_finish的更新需要依靠size這個函數如下? 此時_finish是更新前的? 而_start是更新后的 此時相減就出問題了

解決方法

1.? 先更新_finish 再更新start? 先更新finish的話 此時的finish和start都指向原來的空間 size可以正常算 那么finish的就可以指向更新后的位置了

2. finish更新位置需要用到size 那么在更新start之前就提前算一下size并存起來到old_size中

有了reserve之后 我們就可以寫尾插的函數了? 先判斷空間滿沒有 滿了先用reserve來擴容??然后進行尾插并更新finish?

?形參用引用是因為?用傳值傳參的方式會進行拷貝構造?如果傳的是自定義類型的話拷貝代價比較大? 同時如果實參傳遞的時候傳的不是變量而是1? 2 直接的數字這種方式 此時的實參具有常性 如果這里引用的不用const修飾的話 相當于權限放大了 會報錯

然后再重載[]之后我們就可以用下標的方式進行打印了

如下實現四個迭代器之后 我們就可以通過迭代器的方式和范圍for的方式進行打印了 這些都和之前一樣

insert

在string那里insert插入我們實現的是下標的方式 在上次vector使用中我們發現標準庫中的insert只有迭代器的方式 所以這里也用迭代器的方式

如果按下圖的方式進行insert插入的操作就會出問題 之后再對pos其實出的問題和之前reserve中_finish更新的問題相似 不過這里是pos的問題

下面來分析一下為什么會出現上述的問題

在insert插入之前 如果空間不夠需要先擴容? 擴容操作通過reserve實現開新空間和將三個迭代器進行更新? 但是pos沒有更新還是指向之前空間的某個位置如下圖

而且擴容操作會把原來的空間給釋放掉? 此時pos位置指向的是被是否掉的空間 類似野指針?*pos=x操作是在原來空間的位置進行的 新的空間數據將原來數據拷貝之后?但是finish正常進行了++ 就導致還是最終會多打印一個數據? 但這個數據為隨機數

問題解決

我們知道出問題的原因和reserve那里類似 pos的位置還指向原來的空間

所以我們需要對pos的位置進行更新? 在reserve更新之前存pos和_start相減的值 通過reserve更新空間及三個迭代器之后 再更新pos的位置 這樣就可以正常的運行了

find可以查找傳的兩個迭代器區間內傳的第三個參數? ?并返回該位置的迭代器

迭代器失效

有了insert之外再結合find? 我們就可以選擇在想要的位置進行插入了 如下圖 find找到2的位置并返回給了pos insert再根據這個pos進行插入 但是在插入之后將pos進行*10的操作 沒有將2*10 而是新插入的6*10了

這還是剛剛類似的問題 在insert函數里面pos位置插入數據后pos指向的還是原來的位置 這時候這個位置的數據是新插入的6了? 也就是之前的通過find得到的pos失效了 pos的意義改變了

另一種失效問題

如下圖先尾插4個數據 再在2的位置插入一個6 再對pos位置*10 這次這里什么都沒有變 這里是在insert函數里面空間不夠通過reserve擴容了? 擴容了之后pos指向的還是原來的舊空間? 剛剛我們更新pos是在insert函數里面對形參pos進行的 對于實參pos還是指向舊的空間? ?這種的其實就類似野指針一樣

所以pos再使用一次之后就不要再次直接使用了

實際上對于pos的二次使用標準庫中的vector在vs下這樣都會直接報錯（如下圖）? ?linux下gcc編譯器不會報錯 會和我們上面自己寫的一樣可以運行?

解決方法

錯誤方式

既然是在里面形參改變沒有影響實參? 那么如果采用加引用的方式呢

采取這種方式? 對于右下這種正常的寫法就不能使用了（函數返回的臨時對象具有常性 這里傳過來相當于權限放大）

正確解決方法? ?

insert返回pos+1的位置? pos每次使用之后更新它的位置? 如下圖就可以正常進行了 并符合我們的預期

在類外寫一個Printf_vector函數 這里的x是被const修飾的? 調用begin時候也是調用的const的版本返回值也為const類型的迭代器??

但是這樣只能打印int類型的 所以這里可以用模版函數的方式 如下圖

但是這里會報如下圖的錯誤

這是因為在類外用域作用符::訪問類里面時候 可能訪問的是類型 也可能是類的靜態成員變量 編譯器不知道是什么? 這是規定 沒有實例化的類模板里面取東西，編譯器不能區分這里const_iterator

解決方法

在前面加上typename就是告訴編譯器我們訪問的是類型? 如果是要訪問靜態的那后面也不會有變量i

除了在前面加typename之外 也可以用auto來自動識別類型的方式解決

另外打印還可以如下 這樣不只是vector可以打印 任意類型的容器用迭代器方式都可以打印

erase實現

如下圖要用erase刪除全部的偶數? 迭代器it從begin開始每次判斷該位置的值是不是偶數是就用erase刪去然后it++? 一直到最后一個位置? ?但是結果不和我們預期的一樣 會有以下兩種問題

第一個報錯了? 第二個沒有刪干凈?

原因是這個代碼如果該位置是偶數的話會把這個數給刪掉然后后面的數在函數里面會向左移動?然后此時it指向的已經是下一個數據了?此時再++就跳過這個數據了 第二種情況就是這樣

如果最后一個是偶數的話 把最后一個刪掉之后此時it指向的就是finish了 但是還會++就跳過finish了之后再走也永遠不會等于finish 第一種錯誤就是這樣

解決

因為刪除之后再里面就會自動移位了 所以如果刪除的話不需要再移動it? 為了分清也可以讓erase返回pos位置的然后每次更新一下it 這樣我們會更容易控制代碼

resize

第二個參數之前string那里我們只需要一個字符? 但這里是模版類的形式? 第二個參數可能是內置類型的int double char都有可能?或者是自定義類型的 所以這里固定缺省值為某一個類型是不行的

這里缺省值用到了匿名對象的方式 對于自定義類型 這種方式就會調用他們的默認構造函數? 但是這樣子如果是內置類型怎么辦呢? 內置類型有構造嗎?

本來內置類型是沒有的 但是為了支持類似這樣的寫法 就讓內置類型也支持構造了? 如下

??

而對于里面的處理??

分為三種情況 n<size? ?size<n<capacity? ? n>capacity

對于第一種情況 直接改變_finish指向的位置就可以了

對于第二三中情況 不管哪種都直接reserve反正對于第三種情況也不會縮容? ?然后空間夠了之后直接用迭代器finish位置到start+n之前都用val來填充就額可以了 在結束的時候finish的位置也剛好是它正確的位置

拷貝構造還是需要我們自己來寫 不然默認的是淺拷貝 v2和v1指向的是同一塊的空間??在我們寫了析構函數之后 對于同一塊空間就會析構兩次就會崩掉? 所以拷貝構造函數需要我們自己來寫實現深拷貝

拷貝構造有以下兩種方式來實現 第一種和之前的類似?先開空間再更新對應的成員變量 然后拷貝數據? 第二種方式是用范圍for的方式 范圍for每一次從v1取一個值然后尾插給新的要創建的

這里要注意?如果我們自己寫了拷貝構造? 編譯器默認的構造就不能使用了 我們需要自己來寫一個默認構造函數(無參的或者全缺省的)? ? ?或者使用強制調用編譯器默認構造的方式

對于以下自己實現的無參構造函數? ??

這里的具體過程是? ?在聲明位置我們把三個成員變量都=nullptr的方式了? 在調用函數里面內容之前會先用初始化列表把三個成員變量都初始化為空指針 然后才會進入函數里面 如果大于0執行下面的邏輯 如果等于0再經過初始化列表全部初始化為空指針就結束了不會再進行下面操作

賦值

下面這種方式和構造類似? 不過之前可能有數據? 先用clear把原來的數據給清理掉

還用另一種的方式 如下圖??

直接把傳的形參和現在的進行交換? 這里要注意兩個點

? 一個是形參不能為引用了（這里要交換 不能把原來的實參給改變了）?

另一個是這個swap我們最好自己來實現一下 std庫里的swap為了讓各種類型都可以用 用模版的方式 在里面的實現用的是簡單粗暴的?創建新變量c存a 然后a=b b=c這種方式

對于內置類型沒有什么大的消耗 但是對于自定義類型也這樣的話 里面有很多的數據 需要進行三次拷貝構造 代價就很大了? 所以我們最好自己寫一個swap的函數? 如下圖二我們自己寫的 只是把兩個對象的三個指針進行了交換?

在類模版里面也可以寫一個函數模版 它既是類模版的成員函數也是函數模版? 如下面的函數模版寫在類模版中? 這樣就可以支持各種類型的迭代器來初始化vector對象

如下圖v1用vector類型的v的迭代器進行初始化? ?v2用list類型的l1進行初始化??

但是用其他類型迭代器初始化的時候 如這里的v2? ?l1里面需要存的也是int類型或者是可以轉換為int類型 這樣才可以進行初始化

像這樣在類模版里面再寫一個支持各種類型的迭代器使用的函數模版? ?如果我們想把list對象排序 在list中排序不方便我們就可以放到vector中這樣的函數模版 來排序?

寫了這個之后 我們使用之前寫的兩個參數的構造函數初始化的時候又會報錯

為什么呢

如下圖 兩個都是構造函數 如果是用左邊的 兩個形參類型可以直接都實例化為int 而對于右邊第一個參數需要從int到size_t類型的隱式轉換 所以會調用左邊的 而對于int類型在左邊進行解引用操作就會報錯了

解決方法

1.在傳值的時候指定類型 如這里在10后面加一個u? 代表該整數是unsigned類型 就會匹配第二個構造函數了?

2.再寫一個構造函數第一個參數為需要的類型 就會優先匹配這個構造函數了? 實際上的std庫中vector實現就是用到這種方法 寫了多個這樣的構造函數

.

最后reserve其實還存在一個問題

如上圖 如果vector里面存的是自定義類型? 在push_back里面空間不夠會調用reserve reserve里面擴容是通過開新空間拷貝數據釋放原來空間的方式 這里拷貝用到的是mercpy 是按字節拷貝的? 對于內置類型不會出什么問題

但是如果是自定義類型的話 只能進行淺拷貝 把string里面的指針給拷貝了過去? 然后釋放原來空間時候會先把原來空間中指向的字符串空間先給全部釋放了

如下圖? 原來vector存著四個string類型 每個string里面有一個指針指向堆區動態申請的空間? 在開新空間之后用memcpy的方式只會把每一個string對象的指針和size cpapcity給拷貝過去? 然后對于原來的空間會先把string對象str指向的空間給釋放掉再釋放掉舊的空間 此時新空間中存的指針指向的空間是已經被釋放掉的空間?

解決

不用memcpy的方式? 而是對vector中每一個數據直接賦值的方式? 對于自定義類型如string 就會調用string的賦值運算符 會自動開一塊新的空間 然后把內容拷貝過去