柚子快報邀請碼778899分享：C++：模擬實現(xiàn)vector

http://yzkb.51969.com/

目錄

成員變量與迭代器

size

capacity

empty

迭代器有關函數(shù)

實現(xiàn)默認成員函數(shù)的前置準備

reserve

?編輯

?編輯

push_back

構造函數(shù)

無參構造

迭代器區(qū)間構造

n個val來進行構造?

析構函數(shù)

拷貝構造函數(shù)

賦值重載

增刪查改

clear

resize

pop_back

insert

erase

重載[]

print_Container

成員變量與迭代器

我們還是需要在一個命名空間里模擬實現(xiàn)vector，防止和標準庫里的起沖突。

namespace zh

{

template

class vector

{

public:

typedef T* iterator;

typedef const T* const_iterator;

private:

iterator _start = nullptr;

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

};

}

解釋說明：

1.vector是一個非常通用的容器，是一個動態(tài)大小的數(shù)組，可以存儲任意類型的元素，并且能夠自動調整大小以適應元素的添加和刪除。所以我們的模擬實現(xiàn)要寫成類模板。

2.vector可以看做順序表的升級，但是模擬實現(xiàn)vector跟我們以往實現(xiàn)順序表有所不同，順序表是使用一個動態(tài)開辟的數(shù)組、數(shù)組有效元素個數(shù)size和數(shù)組容納最大有效數(shù)據(jù)的個數(shù)capacity維護的，而模擬實現(xiàn)vector需要三個（模板參數(shù)）T* 類型的指針，而vector的迭代器功能恰恰又和T*類型指針類似，所以干脆把T*封裝成迭代器。當然迭代器需要有兩個版本，普通版本和const版本。

3.參數(shù)的含義

_start指向數(shù)組首元素，_finish指向最后一個有效元素的下一個位置，?_end_of_storage指向數(shù)組空間末尾。

通過三個指針也可以模擬出size和capacity的功能。

size

返回有效數(shù)據(jù)個數(shù)的函數(shù)。

size_t size() const

{

return _finish - _start;

}

capacity

返回數(shù)組最大容納有效數(shù)據(jù)個數(shù)（容量大小）的函數(shù)。

size_t capacity() const

{

return _end_of_storage - _start;

}

empty

判斷數(shù)組是否為空，判斷_start與_finish是否相等即可。

bool empty() const

{

return _finish == _start;

}

迭代器有關函數(shù)

主要實現(xiàn)begin函數(shù)和end函數(shù)。

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin() const

{

return _start;

}

const_iterator end() const

{

return _finish;

}

實現(xiàn)默認成員函數(shù)的前置準備

reserve

用于vector數(shù)組空間不足時擴容的函數(shù)（擴容成n個空間）。

void reserve(size_t n)

{

if (n > capacity()) //n大于數(shù)組容量才擴容

{

size_t oldsize = size(); //用oldsize避免新_start和老_finish的問題

T* tmp = new T[n];

//memcpy(tmp, _start, size() * sizeof(T)); //這里是淺拷貝，如果是內置類型，沒問題

//如果vector存的是自定義類型，就是大坑

for (size_t i = 0; i < oldsize; ++i)

{

tmp[i] = _start[i];

}

delete _start; //這里delete_start，_finish 和_end_of_storage是野指針

//更新成員變量

_start = tmp;

_finish = tmp + oldsize;

_end_of_storage = tmp + n;

}

}

reserve有幾個問題需要注意：

1.開空間的時候要使用new而不要用malloc，因為malloc只是去開空間，不會去調用構造函數(shù)。

2.新_start和_finish的問題。

錯誤示范。

將原有數(shù)據(jù)拷貝到新空間后，釋放了舊空間的資源，_strat指向了新的空間，但是_finish和_end_of_storage還是指向舊空間，這兩個指針就變成野指針了。而最關鍵的是_finish不能被正確賦值。

3.memcpy淺拷貝問題

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

memcpy是淺拷貝，如果vector存的是內置類型，那么淺拷貝就沒有問題，如果存的是自定義類型，那淺拷貝就是個大坑。假如vector存的是string類型，那么擴容時，將數(shù)據(jù)從舊空間拷貝到新空間時，因為是淺拷貝，所以兩個空間里的string的_str是同一個地址，釋放舊空間的時候就連帶這把新空間的資源也釋放了。

這樣就擴容失敗了，因為你把原空間的數(shù)據(jù)丟失了，而且搞不好有可能程序還會崩潰。

要解決這個問題，我們就得手動實現(xiàn)深拷貝，?因為new出來的空間如果是自定義類型的話就自動調用構造函數(shù)初始化了，所以這里走的是賦值重載來實現(xiàn)深拷貝。

push_back

用于在數(shù)組末尾尾插一個元素的函數(shù)。

void push_back(const T& x)

{

//插入之前先判斷空間是否足夠

if (_finish == _end_of_storage)

{

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

}

//插入元素，更新_finish

*_finish = x;

_finish++;

}

構造函數(shù)

vector的構造函數(shù)我們實現(xiàn)無參構造、迭代器區(qū)間構造和n個val構造。

無參構造

無參構造其實我們并不需要寫，因為已經(jīng)在成員變聲明時給了缺省值，編譯器自動生成的無參構造函數(shù)走初始化列表滿足需求了。但是由于我們寫了其他構造函數(shù)，編譯器就不自動生成了。

這里時候可以自己寫無參構造，也可以用default強制編譯器生成（C++11的用法）。

//構造

/*vector()

{}*/

//c++11 強制生成構造

vector() = default;

迭代器區(qū)間構造

//類模板的成員函數(shù)，還可以繼續(xù)是函數(shù)模版

template

vector(InputIerator first, InputIerator last)

{

while (first != last)

{

push_back(*first);

++first;

}

}

這里給這個函數(shù)再套一層模板是為了讓vector不僅能用vector的迭代器區(qū)間構造，還能用其他容器（list、string等）的迭代器來進行構造。

這里又有個問題，就是while循環(huán)判斷條件的!=不能改成<，因為<對于vector的迭代器時可以的，但是對于其他容器的迭代器，如list，last不一定比first要大。

n個val來進行構造?

vector(size_t n, const T& val = T())

{

//先開好空間

reserve(n);

for (size_t i = 0; i < n; ++i)

{

push_back(val);

}

}

使用的時候val可能不傳參，所以要給缺省值。

因為val的類型不確定，可能是內置類型，也可能是自定義類型。

在不傳參使用缺省值時

對于自定義類型，比如strng，先調用構造函數(shù)構造一個匿名對象，再拷貝構造給val。（編譯器會優(yōu)化，直接對val進行構造），這樣val就有了缺省值。

對于內置類型，本來是沒有構造函數(shù)的說法的，但是為了適應這里，也支持類似類那種使用構造函數(shù)初始化的方式。

int a = int();

int b = int(2);

int c(3);

cout << a << endl;

cout << b << endl;

cout << c << endl;

析構函數(shù)

直接delete就可以了，把三個迭代器置空。

//析構

~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

拷貝構造函數(shù)

先開好空間，然后尾插就可以了。

//拷貝構造

vector(const vector& v)

{

reserve(v.size());

for (auto& e : v)

{

push_back(e);

}

}

賦值重載

首先實現(xiàn)一個交換函數(shù)，然后傳值調用，將兩個對象交換即可。

//void swap(vector& v) 可以這樣寫

void swap(vector& v)

{

std::swap(_start, v._start);

std::swap(_finish, v._finish);

std::swap(_end_of_storage, v._end_of_storage);

}

vector& operator=(vector v)

{

swap(v);

return *this;

}

增刪查改

clear

不需要真的刪除，直接將更改_finish的值即可。

void clear()

{

_finish = _start;

}

resize

控制有效數(shù)據(jù)個數(shù)。

若n < size，直接將_finish更改為_start + n即可。若_size < n < capacity或者n > capacity，直接擴容成n個空間（空間足夠就不會擴容），從_finish拷貝足夠數(shù)量的val即可。

void resize(size_t n, T val = T())

{

if (n < size())

{

_finish = _start + n;

}

else

{

reserve(n);

while (_finish != _start + n)

{

*_finish = val;

++_finish;

}

}

}

pop_back

先判斷數(shù)組是否為空，尾刪一個元素，_finish-- 即可。

void pop_back()

{

//判斷下數(shù)組是否為空

assert(!empty());

--_finish;

}

insert

在pos位置插入一個元素。

iterator insert(iterator pos, const T& x) //pos不會為0，因為是有效的迭代器

{

assert(pos >= _start);

assert(pos <= _finish);

if (_finish == _end_of_storage) //涉及到擴容，pos會失效，pos指向原來的空間

{

size_t len = pos - _start;

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

pos = _start + len;

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

--end;

}

//插入元素，更新

*pos = x;

++_finish;

return pos;

}

注意的問題：

1.如果插入涉及到了擴容，要提前把pos相對于首元素的相對長度記錄下來，擴容完畢后，更新pos。因為擴容會導致pos失效。

2.插入之后要返回新元素的迭代器。（這里其實也算迭代器是失效了，因為pos指向的元素發(fā)生了更改，迭代器失效了就不要在使用了。）

erase

刪除pos位置的元素，刪除完后返回刪除元素下一位置的迭代器。

iterator erase(iterator pos)

{

assert(pos >= _start);

assert(pos < _finish);

iterator it = pos + 1;

while (it != end())

{

*(it - 1) = *it;

++it;

}

--_finish;

return pos;

}

拋出一個問題，利用迭代器刪除vector中所有的偶數(shù)。

錯誤做法

auto it = v.begin();

while (it != v.end())

{

if (*it % 2 == 0)

{

it = v.erase(it);

}

it++；

}

刪完一個偶數(shù)后，it已經(jīng)是下一元素的迭代器了，it不需要++了。

正確做法

auto it = v.begin();

while (it != v.end())

{

if (*it % 2 == 0)

{

it = v.erase(it);

}

else

{

++it;

}

}

重載[]

為了方便訪問和修改數(shù)組中的元素。

T& operator[](size_t i)

{

assert(i < size());

return _start[i];

}

const T& operator[](size_t i) const

{

assert(i < size());

return _start[i];

}

print_Container

通用打印容器函數(shù)，套一層模板即可。

注意：

?

template

void print_Container(const Container& v)

{

//typename vector::const_iterator it = v.begin(); //typename標定為類型

//從沒有實例化的類模板取出來的可能是類型或者成員變量，編譯器無法區(qū)分

auto it = v.begin();

while (it != v.end())

{

cout << *it << ' ';

++it;

}

cout << endl;

/*for (auto num : v)

{

cout << num << ' ';

}

cout << endl;*/

}

?

從未實例化的類取出來的有可能是類型或者成員變量，要加關鍵字typename告訴編譯器是類型，不加的話會發(fā)生編譯錯誤。

當然直接用auto更方便。

拜拜，下期再見?

摸魚ing???

柚子快報邀請碼778899分享：C++：模擬實現(xiàn)vector

http://yzkb.51969.com/

精彩鏈接