vector與array非常相似，兩者唯一差别在于空間運用的靈活性
array是靜态空間，一旦配置了就不能改變；若要改變使用的空間大小，一切瑣碎由用戶端自己來處理：先配置新空間，然後将元素從舊址一一搬到新址去，在退還原來的空間
vector則是動态空間，随着元素的加入，它的内部機制會自行擴充空間以容納新的元素
以下為sgi vector源碼：
//alloc即為之前講過的空間配置器
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type* iterator; //可以看到，這裡iterator直接就是指針
typedef const value_type* const_iterator;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
//聲明一個空間配置器對象
typedef simple_alloc<value_type, Alloc> data_allocator;
iterator start; //目前使用空間的開頭
iterator finish; //目前使用空間的尾部
iterator end_of_storage; //目前可用空間的尾部
void insert_aux(iterator position, const T& x); //此函數将對象x插入到某個位置上，且此函數負責改變vector的大小
void deallocate() {
//直接将整個vector釋放
if (start) data_allocator::deallocate(start, end_of_storage- start);
}
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_type size() const { return size_type(end() -begin()); }
size_type capacity() const { returnsize_type(end_of_storage - begin()); }
bool empty() const { return begin() == end(); }
reference operator[](size_type n) { return *(begin() + n); }
//構造函數
vector() : start(0), finish(0),end_of_storage(0) {}
vector(size_type n, const T& value) {fill_initialize(n, value); }
vector(int n, const T& value) {fill_initialize(n, value); }
vector(long n, const T& value) {fill_initialize(n, value); }
explicit vector(size_type n) { fill_initialize(n, T()); }
vector(const vector<T,Alloc>& x) {
start = allocate_and_copy(x.end() -x.begin(), x.begin(), x.end());
finish = start + (x.end() - x.begin());
end_of_storage = finish;
}
~vector() {
//destroy函數在空間配置器章節中講過，通過使用value_type判斷是否有對每個對象調用析構函數的必要性，沒有就直接free， 有的話才調用每個的析構函數
destroy(start,finish);
//這個函數就是上面看到的，調用了空間配置器對象的deallocate函數，主要看釋放記憶體的大小，看調用的是第一級配置器還是第二級
deallocate();
}
vector<T, Alloc>& operator=(const vector<T,Alloc>& x);
void reserve(size_type n) {
if (capacity() < n) {
const size_type old_size = size();
iterator tmp = allocate_and_copy(n,start, finish);
destroy(start, finish);
deallocate();
start = tmp;
finish = tmp + old_size;
end_of_storage = start + n;
}
}
//可見，front和back都是實實在在的指向第一個元素和最後一個元素
reference front() { return *begin(); }
reference back() { return *(end() - 1); }
//将元素插入至最尾端
void push_back(const T& x) {
if (finish != end_of_storage) {
construct(finish, x); //之前接觸了，就是調用 placement new，在finish指向的未初始化記憶體構造一個對象
++finish; //finish指向下一個未初始化的記憶體
}
else
insert_aux(end(), x);
}
void swap(vector<T, Alloc>& x) { //交換兩個vector的内容
__STD::swap(start, x.start);
__STD::swap(finish, x.finish);
__STD::swap(end_of_storage,x.end_of_storage);
}
//插入某個元素在某個位置
iterator insert(iterator position, const T& x) {
size_type n = position - begin();
if (finish != end_of_storage && position == end()){
construct(finish, x);
++finish;
}
else
insert_aux(position, x);
return begin() + n;
}
iterator insert(iterator position) { return insert(position,T()); }
void insert (iterator pos, size_type n, const T& x);
void insert (iterator pos, int n, const T& x) {
insert(pos, (size_type) n, x);
}
void insert (iterator pos, long n, const T& x) {
insert(pos, (size_type) n, x);
}
//将最尾端元素取出，要注意的是先将finish減一在釋放，因為finish指向最後一個元素的下一個沒有對象的記憶體位置
void pop_back() {
--finish;
destroy(finish);
}
//整體前移
iterator erase(iterator position) {
if (position + 1 != end())
copy(position + 1, finish, position);
--finish;
destroy(finish);
return position;
}
iterator erase(iterator first, iterator last){
iterator i = copy(last, finish, first);
destroy(i, finish);
finish = finish - (last - first);
return first;
}
//調整vector大小
void resize(size_type new_size, const T& x) {
if (new_size < size())
erase(begin() + new_size, end()); //這裡的政策是隻調整finish位置，而不改變整個vector的大小
else
insert(end(), new_size - size(), x);
}
void resize(size_type new_size) { resize(new_size, T()); }
void clear() { erase(begin(), end()); }
protected:
//配置n個資料的空間并且用n個x填充
iterator allocate_and_fill(size_type n, const T& x) {
iterator result =data_allocator::allocate(n);
__STL_TRY {
uninitialized_fill_n(result, n, x); //這裡直接調用我們之前講過的函數
return result;
}
__STL_UNWIND(data_allocator::deallocate(result, n));
}
Vector的疊代器
Vector維護的是一個連續線性空間，普通指針可以作為其疊代器且滿足所有必要條件
是以 vector<int>:iterator it;
其實 it 的類型就是 int *
Veector的資料結構
Vector較為簡單，就是簡單的：
iterator start; //目前使用空間的開頭
iterator finish; //目前使用空間的尾部
iterator end_of_storage; //目前可用空間的尾部
vector的實際配置的大小可能比用戶端需求的量更大些，以備将來可能的擴充
下面我們再來看看push_back函數：
void push_back(const T& x) {
if (finish != end_of_storage) {
construct(finish, x);
++finish;
}
else
insert_aux(end(), x);
}
我們要關注的當然就是insert_aux函數了
void vector<T, Alloc>::insert_aux(iteratorposition, const T& x) {
//插入一個元素之前判斷是否有足夠的空間去插入
if (finish != end_of_storage) {
//在備用空間起始處構造一個元素，并以vector最後一個元素為其初值，因為将來是要将一些元素往後移一個的
construct(finish,*(finish - 1));
//調整finish
++finish;
T x_copy = x;
copy_backward(position, finish - 2, finish- 1); //後移一些元素
*position = x_copy;
}
else {
const size_type old_size= size();
//可以看出，容器是兩倍兩倍的增長的
const size_type len = old_size != 0 ? 2 * old_size : 1;
iterator new_start =data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
new_finish = uninitialized_copy(start,position, new_start);
construct(new_finish, x);
++new_finish;
new_finish = uninitialized_copy(position,finish, new_finish);
}
#ifdef __STL_USE_EXCEPTIONS
catch(...) {
destroy(new_start, new_finish);
data_allocator::deallocate(new_start,len);
throw;
}
#endif /*__STL_USE_EXCEPTIONS */
//最後釋放之前的空間
destroy(begin(), end());
deallocate();
//改頭換面
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
是以，這裡要注意的是，我們所謂的動态增長空間，并不是在原有基礎上接連續的新空間，而是重新申請原有空間兩倍大小的新空間
是以，是以，對于vector的操作，一旦引起空間的重新配置，指向原vector的所有疊代器就全都失效了！！！！！！！！！！！
關于Vector的元素操作
下面我們挑一個操作函數看看：
template <class T, class Alloc>
void vector<T,Alloc>::insert(iterator position, size_type n, const T& x) {
if (n != 0) { //要插入的個數為0就不需要操作了
if (size_type(end_of_storage - finish) >= n) { //是否有空間插入
T x_copy = x;
const size_type elems_after = finish - position; //有幾個元素要放在新元素後面
iterator old_finish = finish;
if (elems_after > n) {
//這裡我們發現插入點之後的現有元素個數大于新增元素個數n，這就說明我們一部分現有元素會被搬到未初始化的空間上，而一部分則隻是單純的後移
//于是我們先将n個末尾元素搬移到新的未初始化的空間上
uninitialized_copy(finish - n, finish,finish);
//立即調整finish
finish += n;
//把剩餘的未搬元素整個的 移到 之前已經搬到未初始化空間上的元素原來占據的空間上
copy_backward(position, old_finish - n,old_finish);
//加入新元素
fill(position, position + n, x_copy);
}
else {
//否則，我們發現發現插入點之後的現有元素個數小于新增元素個數n， 這種情況就說明我們會把新插入的元素在我們擁有的未初始化空間上進行構造
//是以，我們先在未初始化空間上構造n-elems_after個新元素
uninitialized_fill_n(finish, n -elems_after, x_copy);
finish += n - elems_after;
//再在新元素之後把該移的舊元素都移過來
uninitialized_copy(position,old_finish, finish);
finish += elems_after;
//最後在原來的已使用的空間上将所有舊元素改為新元素
fill(position, old_finish, x_copy);
}
}
else {
//否則，我們沒有足夠的空間了！
//就要搬到新的申請的2倍空間上去（或者不是2倍，而是 old_size+n了）
const size_type old_size = size();
const size_type len = old_size + max(old_size, n);
iterator new_start =data_allocator::allocate(len);
iterator new_finish = new_start;
__STL_TRY {
//分三段對新空間進行處理，複制+添加+複制
new_finish = uninitialized_copy(start,position, new_start);
new_finish =uninitialized_fill_n(new_finish, n, x);
new_finish =uninitialized_copy(position, finish, new_finish);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) {
destroy(new_start, new_finish);
data_allocator::deallocate(new_start,len);
throw;
}
# endif /*__STL_USE_EXCEPTIONS */
destroy(start, finish);
deallocate();
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
}
為了了解友善，書上還配了圖：
情況1、
情況2：
最後情況：