柚子快報激活碼778899分享：c++ vector

http://yzkb.51969.com/

vector

1.vector的介紹及使用1.1 vector的介紹

2 vector的使用2.1 vector的定義2.2 vector iterator的使用2.3 vector 內容存儲2.5 迭代器失效問題 (重點)

3 vector的實現(xiàn)

1.vector的介紹及使用

1.1 vector的介紹

vector的介紹文檔

使用STL的三個境界：能用，明理，能擴展 ，那么下面學習vector，我們也是按照這個方法去學習

2 vector的使用

在學習vector過程中重要的是理解接口的功能，并加以運用

2.1 vector的定義

接下來展示vector重要接口：

(constructor)構造函數(shù)聲明接口說明vector()（重點）無參構造vector（size_type n, const value_type& val =value_type()）構造并初始化 n valvector (const vector& x); （重點）拷貝構造vector (InputIterator ?rst, InputIterator last);使用迭代器進行初始化構造

vector的構造代碼演示

2.2 vector iterator的使用

iterator的使用接口說明begin + end（重點獲取第一個數(shù)據(jù)位置的iterator/const_iterator， 獲取最后一個數(shù)據(jù)的下一個位置的 iteratorrbegin +rend獲取最后一個數(shù)據(jù)位置的reverse_iterator，獲取第一個數(shù)據(jù)前一個位置的reverse_iterator

如圖所示可以更好地理解：

迭代器的實現(xiàn)代碼演示

2.3 vector 內容存儲

容量空間接口說明size()（重點獲取數(shù)據(jù)個數(shù)capacity()（重點）獲取容器大小empty()判斷是否為空resize() (重點)可以改變vector的size大小reserve() （重點）可以改變capacity的大小

以下有幾點需注意：

1：capacity的代碼在vs和g++下分別運行會發(fā)現(xiàn)，vs下capacity是按1.5倍增長的，g++是按2倍增長的。這個問題經常會考察，不要固化的認為，vector增容都是2倍，具體增長多少是根據(jù)具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL。

2：reserve只負責開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價缺陷問題。

void reserve(int x)

{

if (x > capacity())

{

int temp = size();

T* tmp = new T[x];

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

for (int i = 0;i < temp;i++)

{

tmp[i] = _start[i];//如果vector存的值是string為了防止淺拷貝,tmp[i]就是string類型,_start[i]也是string類型,而string" = "是深拷貝,那么用string深拷貝來解決這個問題

}

delete[]_start;

_start = tmp;

_finish = tmp + temp;

_end_of_storage = tmp + x;

}

}

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

{

if (n < size())

{

_finish =_start + n;

}

else

{

reserve(n);

while(_finish<_start+n)

{

push_back(val);

}

}

}

int capacity()

{

return _end_of_storage - _start;

}

bool empty()

{

return _start==_finish;

}

int size()

{

return _finish-_start;

}

代碼演示

2.4 vector的增刪查改

vector的增刪查改接口說明push_back（重點）尾插pop_back （重點）尾刪?nd查找。（注意這個是算法模塊實現(xiàn)）insert (重點)在position之前插入valerase （重點）刪除position位置的數(shù)據(jù)swap交換倆個vector的數(shù)據(jù)operator[](重點）與訪問數(shù)組一樣

vector插入和刪除代碼實現(xiàn) vector插入和刪除代碼使用

2.5 迭代器失效問題 (重點)

迭代器的主要作用就是讓算法能夠不用關心底層數(shù)據(jù)結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：vector的迭代器就是原生態(tài)指針T 。因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經失效的迭代器，程序可能會崩潰)。*

1:會引起其底層空間改變的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

#include

using namespace std;

#include

int main()

{

vector v{1,2,3,4,5,6};

auto it = v.begin();

// 將有效元素個數(shù)增加到100個，多出的位置使用8填充，操作期間底層會擴容

// v.resize(100, 8);

// reserve的作用就是改變擴容大小但不改變有效元素個數(shù)，操作期間可能會引起底層容量改變

// v.reserve(100);

// 插入元素期間，可能會引起擴容，而導致原空間被釋放

// v.insert(v.begin(), 0);

// v.push_back(8);

// 給vector重新賦值，可能會引起底層容量改變

v.assign(100, 8);

/*

出錯原因：以上操作，都有可能會導致vector擴容，也就是說vector底層原理舊空間被釋

放掉，而在打印時，it還使用的是釋放之間的舊空間，在對it迭代器操作時，實際操作的是一塊

已經被釋放的空間，而引起代碼運行時崩潰。

解決方式：在以上操作完成之后，如果想要繼續(xù)通過迭代器操作vector中的元素，只需給

it重新賦值即可。

*/

while(it != v.end())

{

cout<< *it << " " ;

++it;

}

cout<

return 0;

}

2.指定位置元素的刪除操作 erase

#include

using namespace std;

#include

int main()

{

int a[] = { 1, 2, 3, 4 };

vector v(a, a + sizeof(a) / sizeof(int));

// 使用find查找3所在位置的iterator

vector::iterator pos = find(v.begin(), v.end(), 3);

// 刪除pos位置的數(shù)據(jù)，導致pos迭代器失效。

v.erase(pos);

cout << *pos << endl; // 此處會導致非法訪問

return 0;

}

可得：

erase刪除pos位置元素后，pos位置之后的元素會往前搬移，沒有導致底層空間的改變，理論上講迭代器不應該會失效，但是：如果pos剛好是最后一個元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，那么pos就失效了。因此刪除vector中任意位置上元素時，vs就認為該位置迭代器失效了。

SGI STL中，迭代器失效后，代碼并不一定會崩潰，但是運行 結果肯定不對，如果it不在begin和end范圍內，肯定會崩潰的。

3.與vector類似，string在插入+擴容操作+erase之后，迭代器也會失效(數(shù)據(jù)的挪動而導致空間與數(shù)據(jù)不對齊)

#include

void TestString()

{

string s("hello");

auto it = s.begin();

// 放開之后代碼會崩潰，因為resize到20會string會進行擴容

// 擴容之后，it指向之前舊空間已經被釋放了，該迭代器就失效了

// 后序打印時，再訪問it指向的空間程序就會崩潰

//s.resize(20, '!');

while (it != s.end())

{

cout << *it;

++it;

}

cout << endl;

it = s.begin();

while (it != s.end())

{

it = s.erase(it);

// 按照下面方式寫，運行時程序會崩潰，因為erase(it)之后

// it位置的迭代器就失效了

// s.erase(it);

++it;

}

}

3 vector的實現(xiàn)

頭文件（包含接口的實現(xiàn)）

#pragma once

#include

#include

#include

#include

using namespace std;

template

class vector

{

typedef T* iterator;

/*typedef const T* const_iterator;*/

public:

vector()//默認構造

{}

~vector()//析構

{

if (_start != nullptr)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

vector(vector& v)//拷貝構造

{

reserve(v.size());

for(auto& e : v)

{

push_back(e);

}

}

vector& operator=(vector& v)

{

assert(_start != v.begin());

reserve(v.size());

for (auto& e : v)

{

push_back(e);

}

return *this;

}

//void swap(vector& v)

//{

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

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

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

//}

//

//void Swap(vector& v)

//{

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

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

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

//}

//現(xiàn)代寫法

//vector& operator=(vector& v)

//{

// Swap(v);

// return *this;

//}

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

//const_iterator begin()

//{

// return _start;

//}

//const_iterator end()

//{

// return _finish;

//}

int size()

{

return _finish - _start;

}

int capacity()

{

return _end_of_storage - _start;

}

void reserve(int x)

{

if (x > capacity())

{

int temp = size();

T* tmp = new T[x];

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

for (int i = 0;i < temp;i++)

{

tmp[i] = _start[i];//如果vector存的值是string為了防止淺拷貝,tmp[i]就是string類型,_start[i]也是string類型,而string" = "是深拷貝,那么用string深拷貝來解決這個問題

}

delete[]_start;

_start = tmp;

_finish = tmp + temp;

_end_of_storage = tmp + x;

}

}

//void reserve(size_t n)

//{

// if (n > capacity())

// {

// size_t old_size = size();

// T* tmp = new T[n];

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

// delete[] _start;

// _start = tmp;

// _finish = tmp + old_size;

// _end_of_storage = tmp + n;

// }

//}

void push_back(const T& x)

{

if (_finish != _end_of_storage)

{

*_finish = x;

_finish++;

}

else

{

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

*_finish = x;

_finish++;

}

/* if (_finish == _end_of_storage)

{

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

}

*_finish = x;

++_finish;*/

}

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

{

if (n < size())

{

_finish =_start + n;

}

else

{

reserve(n);

while(_finish<_start+n)

{

push_back(val);

}

}

}

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

{

reserve(n);

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

{

push_back(val);

}

}

vector(int n, T val = T())

{

reserve(n);

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

{

push_back(val);

}

}

template

vector(T first, T second)

{

while (first != second)

{

push_back(*first);

first++;

}

}

iterator erase(iterator pos)

{

assert(!(_finish==_start));

iterator end = pos + 1;

while (end < _finish)

{

*(end-1) = *end;

end++;

}

_finish--;

return pos;

}

iterator insert(iterator pos, const T& x)

{

if (capacity() == size())

{

int tmp = pos-_start;

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

pos = _start + tmp;

}

iterator end = _finish-1;

while (end >= pos)

{

*(end+1) = *end;

end--;

}

*pos = x;

++_finish;

return pos;

}

bool empty()

{

return _start==_finish;

}

void pop_back()

{

assert(!empty());

_finish--;

}

T& operator[](int x)

{

assert(!empty());

return _start[x];

}

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

//{

// // 擴容

// if (_finish == _end_of_storage)

// {

// size_t len = pos - _start;

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

// pos = _start + len;

// }

// iterator end = _finish - 1;

// while (end >= pos)

// {

// *(end + 1) = *end;

// --end;

// }

// *pos = x;

// ++_finish;

// return pos;

//}

private:

iterator _start = nullptr;//初始化列表的缺省參數(shù)

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

};

感謝大家觀看！??！

柚子快報激活碼778899分享：c++ vector

http://yzkb.51969.com/

好文閱讀