C++中的vector和C數(shù)據(jù)結(jié)構(gòu)中的動(dòng)態(tài)順序表是相似的。
vector屬于C++STL中的容器，STL在主流上有PJ版本（Windows Visual C++采用，可讀性較差）、SGI（被Linux采用，可移植性好，閱讀性也高）等。
這里的使用在VS環(huán)境下進(jìn)行，后續(xù)模擬實(shí)現(xiàn)參考SGI版本。
值得注意的是，因?yàn)轭惸０宓某霈F(xiàn)，容器中如vector，只是一個(gè)類模板，而真正的類需要實(shí)例化，如
vector，所以定義一個(gè)vector對象，應(yīng)該是類似vector這樣的。v
?
1.1 vector的構(gòu)造、拷貝構(gòu)造與迭代器先認(rèn)識一下，包括vector的構(gòu)造、拷貝構(gòu)造、賦值。
構(gòu)造：
(為了更好理解使用，做了一些關(guān)于空間配置器的省略)
重慶分公司
重慶分公司
//第一種無參構(gòu)造
vector()
//第二種，第一個(gè)參數(shù)代表初始有效個(gè)數(shù)，val代表賦的初始值
vector(size_type n, const value_type& val = value_type());
//第三種，迭代器賦值
template(class InputIterator)
vector(InputIterator first, InputIterator last);拷貝構(gòu)造:
拷貝構(gòu)造很簡單
vector (const vector& x);賦值:
賦值注意的是兩種不同的形式，代表不同含義。
//第一種 直接賦值
vectorv1;
vectorv2(10, 0);
v1 = v2;
//第二種 表面賦值，其實(shí)是拷貝構(gòu)造
vectorv3 = v2; 實(shí)例:
#include#includeusing namespace std;
void vector_test1()
{//構(gòu)造
vectorv1;
vectorv2(10, 0);
vectorv3(v2.begin(), v2.end());
string s = "hello world";
vectorvs(s.begin(), s.end());
//拷貝構(gòu)造
vectorv4(v2);
vectorv5 = v2;
//賦值
vectorv6;
v6 = v2;
}
int main()
{vector_test1();
return 0;
} vector中的迭代器使用
迭代器在C++中，封裝了iterator和const_iterator兩個(gè)類。在使用層面上與指針的使用一致，但在底層實(shí)現(xiàn)上不同STL版本，不一致，不能簡單和指針等同。
首先介紹簡單的begin和end。
//begin 返回指向vector中首元素位置的迭代器
iterator begin();
//end 返回指向vector中末尾元素再下一個(gè)位置的迭代器
iterator end();比如:
void vector_test2()
{//構(gòu)造
vectorv1(10, 1);
vectorv2(v1.begin(), v1.end());
//打印
vector::iterator it = v2.begin();
while(it != v2.end())
{cout<< *it;
++it;
}
cout<< endl;
} ?
const 迭代器的使用
const迭代器保護(hù)的是指向的數(shù)據(jù)不能被修改，而迭代器本身是可以被修改的。
//begin 返回指向vector中首元素位置的迭代器
const iterator begin();
//end 返回指向vector中末尾元素再下一個(gè)位置的迭代器
const iterator end() const;比如：
void vector_test3()
{//構(gòu)造
vectorv1(10, 1);
//權(quán)限的縮小
const vectorv2(v1.begin(), v1.end());
//打印
//切記不能寫成 因?yàn)檫@樣是使得it不能修改。
//const vector::iterator it = v2.begin();
//這樣改變的是迭代器類型，得換的是一個(gè)類
vector::const_iterator it = v2.begin();
while(it != v2.end())
{cout<< *it;
++it;
}
cout<< endl;
} 在迭代器成員函數(shù)中還有rbegin，rend。它們使用和begin、end一樣，只是返回迭代器指向位置反了過來。
?
vector作為動(dòng)態(tài)數(shù)組，也有著當(dāng)前有效數(shù)據(jù)個(gè)數(shù)（size）和當(dāng)前總?cè)萘?capacity)。
size相關(guān)的成員函數(shù):
//返回當(dāng)前有效數(shù)據(jù)個(gè)數(shù)
size_type size() const;
//重新設(shè)置當(dāng)前有效數(shù)據(jù)個(gè)數(shù)
void resize(size_type n, value_type val = value_type());capacity相關(guān)的成員函數(shù):
//返回當(dāng)前總?cè)萘看笮?size_type capacity() const;
//重新設(shè)置總?cè)萘看笮?不縮容只擴(kuò)容
void reserve(size_type n);隨機(jī)訪問與其它:
//[]是運(yùn)算符重載，返回值是單個(gè)數(shù)據(jù)
reference operator[](size_type n);
const_reference operator[](size_type n) const;
//at和[]結(jié)果一樣，只不過是函數(shù)，不怎么用
reference at (size_type n);
const_reference at (size_type n) const;
//返回首元素
reference front();
const_reference front() const;
//返回末尾元素
reference back();
const_reference back() const;void vector_test4()
{vectorv1(1, 5);
cout<< v1.size()<< endl;
cout<< v1.front()<< endl;
//擴(kuò)大size，補(bǔ)4
v1.resize(11, 4);
cout<< v1.back()<< endl;
for (int i = 0; i< v1.size(); ++i)
{cout<< v1[i];
}
cout<< endl;
//縮小size, 截?cái)? v1.resize(6);
for (int i = 0; i< v1.size(); ++i)
{cout<< v1.at(i);
}
cout<< endl;
//不縮容只擴(kuò)容
v1.reserve(10);
cout<< v1.capacity()<< endl;//11
v1.reserve(12);
cout<< v1.capacity()<< endl;//12
} 
注意:vector的插入和刪除，一定要注意返回的迭代器，在進(jìn)行插入刪除后，最好對迭代器指向的位置進(jìn)行更新，不然可能會引起迭代器失效問題。
//尾插
void push_back (const value_type& val);
//尾刪
void pop_back();
//指定位置插入刪除
//指向位置pos插入val, 返回插入新元素的位置
iterator insert (iterator position, const value_type& val);
//指定位置刪除，返回下一個(gè)位置
iterator erase (iterator position);
//指定范圍插入刪除
//指定位置，范圍插入。
templatevoid insert (iterator position, InputIterator first, InputIterator last);
//指定范圍刪除，返回刪除范圍后一個(gè)位置
iterator erase (iterator first, iterator last);
//交換數(shù)據(jù)
void swap (vector& x);
//清空數(shù)據(jù)，容量不變
void clear(); 測試:
void vector_test5()
{//測試尾插尾刪
vectorv1;
v1.push_back(1);
v1.push_back(2);
v1.pop_back();
//測試指定位置插入刪除
vector::iterator it = v1.begin();
it = v1.insert(it, 0);
it = v1.erase(it);
for (int i = 0; i< v1.size(); ++i)
{cout<< v1[i];
}
cout<< endl;
//測試指定范圍插入刪除
vectorv2(10, 1);
it = v1.begin();
v1.insert(it, v2.begin(), v2.end());
it = v1.erase(v1.begin(), v1.begin() + 3);
//其它
v1.swap(v2);
for (int i = 0; i< v1.size(); ++i)
{cout<< v1[i];
}
cout<< endl;
v2.clear();
cout<< v2.size()<< endl;
cout<< v2.capacity()<< endl;
} 使用完~
2、vector的模擬實(shí)現(xiàn)因?yàn)镾GI版STL可讀性比較好，模擬實(shí)現(xiàn)以它為參考。
由于vector的模擬實(shí)現(xiàn)簡單易懂，這里只說部分重要的。
?
2.1 vector的迭代器由于vector是一個(gè)連續(xù)的線性空間，所以原生指針可以作為vector的迭代器且滿足所有必要條件。（但vs中vector的迭代器底層不是這樣的）
templateclass vector
{public:
typedef T* iterator;
typedef const T* const_iterator;
...
} 所以
vector::iterator it; it就是int*.
2.2 vector的結(jié)構(gòu)構(gòu)建vector是一個(gè)線性連續(xù)空間。在SGI底層，用三個(gè)迭代器start、finish、end_of_storage分別指向空間來標(biāo)識范圍。
templateclass vector
{public:
typedef T* iterator;
typedef const T* const_iterator;
...
private:
iterator _start; //表示已使用用空間的頭
iterator _finish; //表示已使用空間的尾
iterator _end_of_storage; //表示目前可用空間的尾
} 通過這三個(gè)迭代器，可以很輕松的聯(lián)系上以下功能
templateclass vector
{public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{return _start;
}
const_iterator begin() const
{return _start;
}
iterator end()
{return _finish;
}
const_iterator end() const
{return _finish;
}
size_t size() const
{return end()-begin();
}
size_t capacity() const
{return _end_of_storage - begin();
}
bool empty() const
{return end() == begin();
}
T& operator[](size_t pos)
{assert(pos< size());
return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos< size());
return _start[pos];
}
private:
iterator _start; //表示已使用用空間的頭
iterator _finish; //表示已使用空間的尾
iterator _end_of_storage; //表示目前可用空間的尾
} 
?
vector構(gòu)造有三種：
vector();
vector(size_t n, const T& val = T());
templatevector(InputIterator first, InputIterator last); 值得注意的是:第二個(gè)構(gòu)造在調(diào)用時(shí)可能是vector v(10,1);這樣的，由于10和1的類型一樣，可能會導(dǎo)致調(diào)用第三個(gè)構(gòu)造造成尋址錯(cuò)誤，所以下面通過函數(shù)重載避免其出現(xiàn)。
#include#include
using namespace std;
namespace test
{templateclass vector
{public:
...
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
//構(gòu)造
vector(size_t n, const T& val = T()) //默認(rèn)0
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{ size_t i = 0;
for (i = 0; i< n; ++i)
{ push_back(val);
}
}
//重載解決類似vectorv(10, 1);這樣引發(fā)的尋址錯(cuò)誤
vector(int n, const T& val = T()) //默認(rèn)0
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{ int i = 0;
for (i = 0; i< n; ++i)
{ push_back(val);
}
}
templatevector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{ while (first != last)
{ push_back(*first);
++first;
}
}
...
...
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
} vector的拷貝構(gòu)造，可以多進(jìn)行函數(shù)復(fù)用，來精簡代碼。
//拷貝構(gòu)造 寫法一
//vector(const vector& v)
// :_start(nullptr)
// , _finish(nullptr)
// , _end_of_storage(nullptr)
//{// reserve(v.capacity());
// for (const auto& e : v) //注意要加& 不然T可能是自定義類型
// {// push_back(e);
// }
//}
//函數(shù)復(fù)用 寫法二
vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{ vectortmp(v.begin(), v.end());
swap(tmp);
}
//利用v拷貝構(gòu)造的臨時(shí)對象進(jìn)行交換
vector& operator=(vectorv)
{ swap(v);
return *this;
}
//調(diào)用官方std中的淺拷貝
void swap(vector& v)
{ std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
插入中的迭代器需要注意，擴(kuò)容可能會導(dǎo)致原本空間被釋放，需要迭代器重新指向新空間。
reserve實(shí)現(xiàn)有兩個(gè)注意點(diǎn)：
1. 因?yàn)閿U(kuò)容是會開辟新空間，歸還舊空間的，所以指向原來舊空間的指針也需要更新。
2. 在拷貝舊空間數(shù)據(jù)的時(shí)候，需要深拷貝，不然自定義類型數(shù)據(jù)淺拷貝會出現(xiàn)析構(gòu)錯(cuò)誤。
void reserve(size_t n)
{if (n >capacity())
{ //使用oldsize 記錄舊空間size大小
size_t oldSize = size();
T* tmp = new T[n];
if (_start)
{ //memcpy(tmp, _start, sizeof(T) * oldSize); 拷貝的是內(nèi)置數(shù)據(jù) 對于自定義類型是淺拷貝
for (size_t i = 0; i< oldSize; ++i)
{tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;
_end_of_storage = _start + n;
}
}insert實(shí)現(xiàn)要注意迭代器失效問題，迭代器pos在擴(kuò)容以后與原來start的相對距離是固定的，但是指向的位置是原來舊空間的位置，在擴(kuò)容后需要更新。
iterator insert(iterator pos, const T& val)
{assert(pos >= _start);
assert(pos< _finish);
if (_finish == _end_of_storage)
{ // 迭代器失效
// 擴(kuò)容導(dǎo)致迭代器失效
size_t oldPos = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
pos = _start + oldPos; //但形參不改變實(shí)參
}
iterator end = _finish - 1;
while (end >= pos)
{ *(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
iterator erase(iterator pos)
{assert(pos >= _start);
assert(pos< _finish);
iterator begin = pos + 1;
while (begin< _finish)
{ *(begin - 1) = *(begin);
++begin;
}
--_finish;
return pos;
}最后在vector中，insert或者erase后，一定要注意迭代器的位置，如果在插入或刪除后需要使用迭代器，一定要讓迭代器接收返回值，不然會出現(xiàn)迭代器失效。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
