STL源码剖析之序列式容器vector

常见的数据结构：array，list，tree，stack，queue，hash table，set，map

可以将上面的数据结构按照数据组织形式分为 sequence 和 associative两种类型。

28

序列式容器，其中的元素都是“可序”的，C++语言提供了array，而STL提供了vector，list，deque( stack，queue )，priority-queue，而其中 stack和queue是在deque基础上改进，所以实际上是一种adapter。

29vector

Vector的数据安排和操作方式 和 常见的array类型很像，但是唯一的不同就在于vector的空间利用灵活度很大，而array分配的是静态空间（需要我们手动扩容等）。

Vector的源码

Template //前面提到的空间配置器

Class vector

{

Public:

Typedef T value_type; //定义自身所需要的类型，用来返回容器的实际类型

Typedef value_type *pointer;

Typedef value_type *iterator;

Typedef value_type &reference;

Typedef size_t size_type;

Typedef ptrdiff_t difference_type;

Protected:

Typedef simple_alloc data_allocator;

Iterator start;

Iterator finish;

Iterator end_of_storage;

Void insert_aux( iterator position,const T& x);

Void deallocate()

{

If( start)

Data_allocator ::deallocate(start,end_of_storage- start); //调用simple_alloc的释放内存过程

}

Void fill_initialize( size_type n, const T& value)

{

Start = allocate_and_fill( n, value); //使用空间配置器配置空间，并赋初值，见下面的函数实体

Finish = start + n;

End_of_storage = finish;

}

Iterator allocate_and_fill( size_type n, const T& x)

{

Iterator result = data_allocator::allocate(n): //调用simple_alloc分配内存

Uninitialized_fill_n(result,n,x); //初始化

Return result;

}

Public:

Iterator begin(){return start;} //返回该容器的迭代子

Iterator end(){return finish;}

Size_type size() const{return size_type(end() – begin()); } //目前长度迭代子差

Size_type capacity() const{return size_type ( end_of_storage – begin() );} //剩余容量

Bool empty() const {return begin() == end();} //是否为空

Reference operator { return *(begin()+n);} //借用迭代器完成随机访问

Vector(): start(0),finish(0),end_of_storage(0) {}

Vector( size_type n, const T& value) { fill_initialize(n,value);} //分配T型的空间

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()

{

Destroy(start, finish);

Deallocate();

}

Reference front() { return *begin();}

Reference back() { return *(end()-1);}

Void push_back ( const T& x)

{

If( finish != end_of_ storage)

{

Construct(finish,x); //未满，插入

++finish;

}

Else

Insert_aux(end(),x); //扩容

}

Void pop_back()

{

-- finish;

Destroy(finish);

}

Iterator erase ( iterator position)

{

If( position +1 !=end)

Copy( position+1,finish,position);

--finish;

Destroy(finish);

Return position;

}

Void resize(size_type new_size,const T& x)

{

If( new_size < size() )

Erase( begin()+ new_size, end() );

Else

Insert ( end(), new_size – size(), x);

}

Void resize(size_type new_size){resize(new_size,T());}

Void clear() { erase(begin(), end()); }

}

Vector容器主要完成了

1将“容器的空间请求释放”等操作 下放给 “空间配置器”代理

2 将“容器内部元素的访问”等操作 使用iterator来完成，并暴露必要的接口（比如pop等），供外界访问

3 增加扩容等操作

30Vector的迭代器

上面的vector源码中，我们看到vector的元素操作都需要一个iterator来完成，而又因为vector维护的是一个【连续的线性空间】，所以不管模板参数类型是如何，该类型的普通参数就可以作为vector的迭代器（迭代器所必须的，->等操作，普通指针本来就有），同时这也让vector可以支持随机存储，因为这是普通指针在连续线性空间所带来的便利*

Template

Class vector

{

Public:

Typedef T value_type;

Typedef value_type* iterator;

//vector的迭代器就是T类型的普通指针，不需要再额外使用其他迭代器，只需要使用这个指针来完成连续线性空间上的存取即可

};

Vector::iterator shapeIterator; //其实就等于 Shape*

31Vector的数据结构

Template

Class vector

{

Protected:

Iterator start;

Iterator finish;

Iterator end_of_storage;

};

// 为了降低空间配置时时间的开销，所以一开始vector的实际空间大小就比客户需要的更大

31最重要的地方是vector如何构造以及其内存管理，元素管理：constructor, push_back

现在来看看Vector iv(2,9);这个对象的初始化过程

1） vector使用默认alloc配置器，并定义了一个simple alloc对象来暴露简单的配置接口

Template< class T, class Alloc=alloc >

Class vector

{

Protected:

Typedef simple_alloc data_allocator;

}

2）构造函数的调用栈

Vector(size_type n, const T& value) // Vector iv(2,9);这个对象的初始化过程

{

Fill_initialize(n ,value);

}

Void fill_initialize( size_type n, const T& value)

{

Start = allocate_and_fill ( n, value );

Finish = start + n;

End_of_storage = finish; //初始化的话，容量和size一样大

}

Iterator allocate_and_fill( size_type n, const T& x)

{

Iterator result = data_allocator::allocate(n);

Uninitialized_fill_n ( result, n, x);

Return result;

}

uninitialized_fill_n会根据第一个参数result的类型的特性（是不是non-trail的构造，也就是利用我们在第三章使用的trait技巧获取必要的类型信息），来决定是使用算法fill_n(),还是使用construct()来完成任务。

32push_back所带来的扩容操作

首先是push_back 的定义

Void push_back(const T& x)

{

If ( finish != end_of_storage)

{

Construct(finish,x); //还有余量，则构造

}

Else //finish == end

Insert_aux(end(),x); //没有余量，则传入最后节点位置。

}

Template

Void vector::insert_aux (iterator position, const T& x) //扩容操作

{

If ( finish !=end_of_storage) //仅仅超出finish，没到end，插入一个元素可以负担

{

Construct(finish, *(finish-1) ); //finish为构造点的内容起始地址，构造finish-1位置的元素大小的内存空间

++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* oldsize :1;

Iterator new_start=data_allocator::allocate(len); //为新长度vector配置新空间

Iterator new_finish= new_start;

Try

{

New_finish = uninitialized_copy (start, position,new_start); //拷贝原有内容

Construct(new_finish,x); //构造新元素所在位置的空间

++ new_finish;

New_finish= uninitialized_copy( position,finish,new_finish);

}

Catch(..)

{

Destroy(new_start, new_finish); //注意失败时要销毁

Data_allocator::deallocator(new_start,len);

Throw;

}

Destroy( begin(),end() ); //销毁原来的空间

Deallocate();

Start=new_start;

Finish=new_finish;

End_of_storage= new_start+len;

}

}

因为是重新配置空间，所以在vector进行重新配置后，原来指向vector的迭代器就失效的了。（因为在扩容的过程中销毁了原有的空间

33vector的元素操作 pop_back,erase,clear,insert（支持随机访问）

Void pop_back()

{

--finish;

Destroy(finish); //temp=finish--; destroy(temp);

}

Iterator erase(iterator first, iterator last) //可能是在中间区间

{

Iterator I = copy(last, finish,first); //将 first到x 和 last后到finish 的元素交换，返回的是拷贝成功后的最后一个元素迭代器

Destroy(i,finish); //将新的i（标志first）到finish删除。

Finish = finish – ( last-first );

Return first;

}

Iterator erase(iterator position)

{

If ( position+1 !=end() )

Copy( position+1,finish,position); //将position+1到finish的东西向前移动一步，以position开头

--finish; //temp = finish--; destroy(temp);

Destroy(finish);

Return position;

}

//删除即使用后面的值覆盖将要被删除的部分，然后将剩下的擦除

Void clear() {erase( begin(), end() );}

Vector的擦除操作

将标记为将要删除的区间和其后继的节点进行交换，交换后再进行删除、

Vector的插入操作

Template

Void vector::insert(iterator position, size_type n, const T& x)

{

//在position位置上插入n个值为x的元素

If (n!=0)

{

If( size_type(end_of_storage - finish) >= n) //“备用空间” 大于等于 “新增元素”的个数

{

T x_copy = x;

Const size_type elems_afer= finish – position; //计算插入点之后的现有元素个数

Iterator old_finish = finish;

If ( elems_after > n ) //插入点之后现有元素的个数 大于 新增的元素个数

{

Uninitialize_copy(finish – n, finish, finish);

//将finish前n个元素先拷贝到备用空间

Finish += n;

Copy_backward( position, old_finish – n ,old_finish);

Fill( position,position+n,x_copy); //填充空出来的位置

}

基本思路是要插入n个元素，则把数组中最后n个元素拷贝到备用空间中，然后再往后调节剩下的未移动的位置，最后插入n个元素

Else //插入点之后现有元素的个数 小于等于新增的元素个数

{

Uninitialized_fill_n(finish, n-elems_after, x_copy);

//先将多出来的节点值插入到finish后

Finish += n – elems_after;

Uninitialized_copy ( position ,old_finish, finish);

//然后把前面剩下的节点，赋值到空闲区

Finish+=elems_after;

Fill( position,old_finish,x_copy);

//最后将value节点填充到空出来的位置

}

基本思路是先将多余的x插入到备用空间，使得插入点之后的现有元素个数>=将要插入的元素（注意已经插入了一些，所以要重新计算），然后插入点之后需要被替换的元素复制到备用空间，最后完成其他x的插入。

Else //备用空间< 新增元素个数

{

}

}

}

}
原文链接: https://www.cnblogs.com/aga-j/archive/2011/06/07/2074070.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍