深入分析STL标准模板——vector
——计算机学院--马晶义
摘要：通过阅读c++的STL标准模板库中vector的源代码，分析STL 中的内部成员、接口、内存管理、封装等方面。Vector 是一种顺序性的容器，按照严格线性存储各种对象。它其实就是一种动态的数组，正如数组，vector有他们存储在存储单元相邻元素,这就意味着他们的元素可以被存取不只有使用迭代器还定期使用指针抵消元素。但是不像普通的数组,存储在向量自动处理,允许它的扩展和简约的需要。
关键字：STL、Vcector、内部成员函数、接口函数、封装
一、vector的声明及内部常用函数
1.vector的声明
vector
vector
vector
c.~vector
2.vector容器中常用的函数。(c为一个容器对象）
c.push_back(elem); 在容器最后位置添加一个元素elem
c.pop_back(); 删除容器最后位置处的元素
c.at(index); 返回指定index位置处的元素
c.begin(); 返回指向容器最开始位置数据的指针
c.end(); 返回指向容器最后一个数据单元的指针+1
c.front(); 返回容器最开始单元数据的引用
c.back(); 返回容器最后一个数据的引用
c.max_size(); 返回容器的最大容量
c.size(); 返回当前容器中实际存放元素的个数
c.capacity(); 同c.size()
c.resize(); 重新设置vector的容量
c.reserve(); 同c.resize()
c.erase(p); 删除指针p指向位置的数据，返回下指向下一个数据位置的指针（迭代器）
c.erase(begin,end) 删除begin,end区间的数据，返回指向下一个数
据位置的指针（迭代器）
c.clear(); 清除所有数据
c.rbegin(); 将vector反转后的开始指针返回(其实就是原来的end-1)
c.rend(); 将vector反转后的结束指针返回(其实就是原来的begin-1)
c.empty(); 判断容器是否为空，若为空返回true，否则返回false
c1.swap(c2); 交换两个容器中的数据
c.insert(p,elem); 在指针p指向的位置插入数据elem,返回指向elem位置的指针
c.insert(p,n,elem); 在位置p插入n个elem数据，无返回值
c.insert(p,begin,end) 在位置p插入在区间[begin,end)的数据，无返回值
二、vector接口函数实例分析
【1】vector::assign //用来构造一个vector的函数，类似于copy函数void assign( size_type _Count, const Type& _Val);
//_Count指要构造的vector成员的个数，_Val指成员的数值，他的类型必须与vector类型一致！
template
void assign( InputIterator _First, InputIterator _Last );
//两个指针，分别指向复制开始和结束的地方!
例如：
运行结果：
【2】vector::at
//指找到第N个vector成员，就跟我们再数组中找到第N个成员的a[N]类似
reference at( size_type _Pos);
const_reference at( size_type _Pos) const;
//找到第_Pos个成员
例如：
运行结果：
【3】vector::back
reference back( );
const_reference back( ) const;
返回最后一个的位置例如：
运行结果：
三、vector内存管理相关方法
vector是一种序列式容器（其中的元素可以排序，但是并未排序）。它和array一样，存储空间是一段连续的内存，因此支持随机访问，但是，和array相比，vector支持动态增加数据。
当使用new来进行动态内存分配，会有三个麻烦：（1）必须确保会用delete这个分配；如果后面没有delete，new就会产生一个资源泄露。（2）必须确保delete使用的是正确形式；对于分配一个单独的对象，必须使用“delete”。对于分配一个数组，必须使用“delete[]”。如果使用了delete的错误形式，结果会未定义。在一些平台上，程序在运行期会死掉。另一方面，它会默默的走向错误，有时候会造成资源泄露，一些内存也随之而去。（3）一个new只delete 一次，如果一个分配被删除了不止一次，结果也会未定义。
而STL中vector和string就不会这么麻烦了。当准备动态分配一个数组（也就是，要写“new T[...]”，首先应考虑使用vcetor 或string（一般来说，当T是字符类型的时候使用string，其他用vector，但vcetor
另外，由于vector是序列容器，所以可以让我们支配作用于这样的容器的整个STL算法。虽然数组也可以用于STL算法，但没有提供
像begin、end和size这样的成员函数，也没有内嵌像iterator、reverse_iterator或value_type那样的typedef。而且char*指针当然不能和提供了专用成员函数的string竞争。
容器的构造函数
1、C
2、C c(c2); 创建c2的一个副本，C和c2必须有相同的容器
类型及元素类型
3、C c(b,e); 创建c，其元素是迭代器b，e范围之间元素的副本。
对于这一条，使用迭代器的时候，不要求容器类型相同。容器内的元素类型也可以不同，只要他们相互兼容，能够将要复制的元素转化为所构建的新容器的元素类型，即可以实现复制。
4、C c(n,t); 用n个值为t的元素创建容器c。（仅适用于顺序
容器）。参数的顺序和语言相适应，n个t。
5、C c(n); 创建含n个默认值的容器c。（仅适用于顺序容器）。
1.template
2.class vector {
3....
4.protected:
5.//vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是
更方便以元素大小为配置单位
6.//专属空间配置器，每次配置一个元素大小
7.typedef simple_alloc
8....
9. vector() : start(0), finish(0), end_of_storage(0) {}
10. vector(size_type n, const T& value) { fill_initialize(n, value); }
11. vector(int n, const T& value) { fill_initialize(n, value); }
12. vector(long n, const T& value) { fill_initialize(n, value); }
13.explicit vector(size_type n) { fill_initialize(n, T()); }
14....
15.void fill_initialize(size_type n, const T& value) {
16. start = allocate_and_fill(n, value); //配置空间并设初值
17. finish = start + n; // 调整范围
18. end_of_storage = finish; // 调整范围
19. }
20.iterator allocate_and_fill(size_type n, const T& x) {
21. iterator result = data_allocator::allocate(n); //配置n个元素空间
22. __STL_TRY {
23.// 全局函数，将result所指的未初始化空间设定为n个初值为x的变量
24.// 定义于
25. uninitialized_fill_n(result, n, x); //全局函数
26.return result;
27. }
2.2 push_back()操作时vector内部的过程
push_back()操作将新元素插入容器尾部，该函数首先检查是否还有备用空间（finish！=end_of_storage），如果有那么就直接在备用空间上构造元素，并调整迭代器finish。如果没有备用空间了（finish= end_of_storage），就扩充空间（重新配置，移动数据，释放原空间）。
1.void push_back(const T& x) {
2.if (finish != end_of_storage) { // 还有备用空间
3. construct(finish, x); // 直接在备用空间中构建元素
4. ++finish; // 调整范围
5. }
6.else// 已无备用空间
7. insert_aux(end(), x);
8. }
9.
10.template
11.void vector
12.if (finish != end_of_storage) { // 还有备用空间
13.// 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值
14. construct(finish, *(finish - 1));
15. ++finish;
16.// 以下做啥用？
17. T x_copy = x;
18. copy_backward(position, finish - 2, finish - 1);
19. *position = x_copy;
20. }
21.else { // 已無備用空間
22.const size_type old_size = size();//此时的size（）等同于capacity（）
23.const size_type len = old_size != 0 ? 2 * old_size : 1;
24.// 以上配置原则：如果原大小为0，那么则配置1（个元素大小）
25.// 如果原大小不为0，那么配置原大小的2倍
26.// 前半段用来放置原数据，后半段用来放置新数据
27.
28. iterator new_start = data_allocator::allocate(len); // 实际配置
29. iterator new_finish = new_start;
30. __STL_TRY {
31.// 复制
32. new_finish = uninitialized_copy(start, position, new_start);
33. construct(new_finish, x);
34. ++new_finish;
35.// 将安插点的原内容页拷贝过来（该函数也可能被insert（p,x）调用）
36. new_finish = uninitialized_copy(position, finish, new_finish);
37. }
38.catch(...) {
39.// "commit or rollback"（如果不成功那么一个都不留）
40. destroy(new_start, new_finish);
41. data_allocator::deallocate(new_start, len);
42.throw;
43. }
44.
45.// 解构并释放原vector
46. destroy(begin(), end());
47. deallocate();
48.
49.// 调整迭代器，指向新vector
50. start = new_start;
51. finish = new_finish;
52. end_of_storage = new_start + len;
53. }
54.}
所谓的vector的大小的动态增长，并不是在原空间之后连续新空间（因为无法保证原空间之后尚有可供配置的空间）。而是以原来大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作一旦引起重新配置，指向原vector的所有迭代器就都失效了。这就是为什么《C++ Primer》中说push_back和inser可能会使迭代器失效的原因。其本质是：空间已进行重新配置。
vector 的内部实现其实就是一块连续内存，它和传统的array不同的是支持扩容，不用考虑越界。vector的迭代器就是最简单的指向容器内类型的指针。其内部有三个指针，start（指向数据存储区的首地址），finish（已使用的数据区的尾端），end_of_storage（指向容量尾端，容量一般富余），当遇到满载的情况，finish指针和
end_of_storage 指针相等，也就是容量用完的时候，如果继续插入元素，就会扩容。
需要扩容的时候，空间适配器就会从新寻找一块更大的内存空间（因为vector内部是一块连续的内存），然后start指向新内存首地址，原始数据复制，新数据插入，同时更新finish以及end_of_storage 即可。扩容的规模一般是原始容量的两倍。
下面的代码参照侯捷《STL源码剖析》第四章。意在了解vector的内存管理以及各个接口的实现。出于简单考虑，部分接口没有按照标
准做，空间适配器的部分是我自己手动实现的，也没有再做成公共接口，而是直接加在函数实现里面了，可能比较粗糙。
1.#include
https://www.doczj.com/doc/7710987160.html,ing namespace std;
3.
4.template
5.class MyVector{
6.public:
7.
8.typedef T * iterator;
9.typedef T * pointer;
10.typedef T & reference;
11.
12. MyVector():start(0),finish(0),end_of_storage(0){}
13. MyVector(int n,const reference val)//申请n单位空间，并用val初始化
14. {
15. start = new T[n];
16. finish = start;
17. end_of_storage = start + n;
18.while(n--) { *finish++=val; }
19. }
20. MyVector(int n)//申请n单位空间，初始化为0
21. {
22. start = new T[n];
23. finish = start;
24. end_of_storage = start + n;
25.while(n--) { *finish++=0; }
26. }
27.
28. ~MyVector(){
29. iterator i;
30.for(i=start;i
31. }
32.
33. iterator begin() const { return start; }
34. iterator end() const { return finish; }
35.
36.//注意size的定义，返回值是end - begin，也就是说，finish指向的是最后一个元素
后面的一个地址
37.int size() const { return int(end()-begin()); }
38.
39.//void resize(int new_size,const reference x);//重新定义空间大小，而且完成初
始化，finish指针在空间尾端
40.//void resize(int new_size);
41.//void reserve(int new_size);//重新定义空间大小，但是不改变finish指针
42.int capacity() const { return end_of_storage-begin(); }
43.
44.bool empty() const { return begin() == end(); }
45.
46. reference operator[](int n) { return *(begin()+n); }
47. reference front() { return *begin(); }
48. reference back() { return *(end()-1); }
49.
50.
51.void push_back(const reference x){
52.if(finish != end_of_storage)//未满载
53. {
54. *finish = x;
55. finish++;
56. }
57.else insert(end(),1,x);//满载，需要重新分配空间，并完成已有成员的搬移
58. }
59.
60.void pop_back()//删除尾端元素
61. {
62. finish--;
63. finish->~T();
64. }
65.
66.void erase(iterator first,iterator last)//清除[first,last)的所有元素
67. {
68.int j = end()-last;
69.for(int i=0;i 70. *(first+i) = *(last+i); 71. } 72.while(end()>first+j){ 73. pop_back(); 74. } 75. } 76. 77.void erase(iterator position)//清除指定位置元素 78. { 79. erase(position,position+1); 80. } 81. 82.void clear(){//清空vector 83. erase(begin(),end()); 84. } 85. 86.void insert(iterator position,int n,const reference x);//从position开始 插入n个元素，每个元素的初始值为x 87.//void insert_aux(iterator position, const reference x);//重新分配空间，并 完成已有成员的搬移 88. 89.private: 90. iterator start; 91. iterator finish; 92. iterator end_of_storage; 93.}; 94. 95.template 96.void MyVector position开始插入n个元素，每个元素的初始值为x 97.{ 98./* 99. STL的vector 位置插入元素，有可能引起扩容 100.当插入导致finish 指针大于 end_ofstorage 时，就需要扩容 101. */ 102. 103. iterator i = start;//old_start 104. iterator new_finish;//不扩容的话指向old_start，扩容的话指向new_start 105. iterator old_start = start,old_finish = finish; 106.bool needToDestory = false; 107.if(finish+n > end_of_storage){ 108. 109. needToDestory = true; 110. 111.const int old_size = size(); 112.const int len = old_size + n; 113. 114. start = new T[len]; 115. new_finish = start; 116. end_of_storage = start + len; 117. } 118.else { 119. new_finish = start; 120. end_of_storage = finish + n; 121. } 122. 123./*原始数据的搬移*/ 124.while(i 125./*插入部分的初始化*/ 126.while(n--) { *new_finish++ = x; } 127./*原始数据的搬移*/ 128.while(i 129. finish = new_finish; 130. 131./*这里需要释放原有空间*/ 132.if(needToDestory==true){ 133.while(old_start != old_finish){ 134. old_start->~T(); 135. old_start++; 136. } 137. } 138.} 139./* 140.template 141.void MyVector 142. insert(position,1,x);//重新分配空间，并完成已有成员的搬移 143.} 144.*/ 145.struct Node{ 146. Node(){} 147. Node(int a=0,int b=0):x(a),y(b){} 148.int x,y; 149.}; 150. 151.int main(){ 152. MyVector 153. 154. cout <<"size of vector now : "<< test.size() << "\t" <<"capacity of vect or now : "<< test.capacity() << endl; 155. 156.for(int i=0;i<3;i++){ 157. Node a(i,i*i); 158. test.push_back(a); 159./* 160. push_back()是从end()端插入，而初始化过的vector的end()是和capacity()相等的，所以会发生扩容， 161.也就是说，我们插入的三个点(0,0)，(1,1)，(2,4)的位置是在a[3],a[4],a[5]中，而a[0],a[1],a[2]中还是初始化时的值， 162.如果觉得这样浪费的话，想把点插入到最开始的位置的话，有以下几种方法： 163. 164. NODE 1：可以再申请容器的时候，不指定大小（默认为0），那么后续插入引起扩容，自然就从第一个位置（a[0]）开始了 165. NODE 2：用reserve(N)指定大小，这个函数不会修改finish指针，也就是说，finish指针指向的是begin()端 166. PS：reserve()接口这里我没有实现，留到以后有时间加上吧 167. NODE 3：用insert()在指定位置插入点，但是这样会引起扩容 168. NODE ……欢迎补充 ^_^ 169. */ 170. } 171. 172. cout <<"size of vector now : "<< test.size() << "\t" <<"capacity of vect or now : "<< test.capacity() << endl; 173. 174. MyVector 175.for(pi = test.begin();pi != test.end();pi++){ 176. cout << pi->x << " " << pi->y << endl; 177. } 178. 179./******测试insert()******/ 180. test.insert(test.begin(),7,test[5]);//在begin()端插入7个元素，容量变为 size() + 7 181. 182. cout <<"size of vector now : "<< test.size() << "\t" <<"capacity of vect or now : "<< test.capacity() << endl; 183. 184. MyVector 185.for(pj = test.begin();pj != test.end();pj++){ 186. cout << pj->x << " " << pj->y << endl; 187. } 188.return 0; 189.} 四、vector的封装技巧 Vector在接口设计时的封装技巧有： （1）迭代器接口设计。使用半开半闭区间来表征范围。 （2）类型重定义。这样就可以使用一致的类型名表达不同的实例类型。 （3）独立的分配器。让对象分配可定制。注意：对于vector来说， 除了 @vczh 提到的分离对象构造和内存分配一点之外，意义不大。但是对于list等容器来说，这个技巧至关重要。 Vector的封装特点：1.vector支持连续线性空间，支持包括指针在内的等所有无论其元素型别，都能作为vector迭代器所满足的所有条件。2.封装了空间配置和释放的相关功能，实现动态增加空间大小。 3.提供多种封装的constructors。 五、Vcector使用注意 和标准C++运行库中的绝大部分东西一样，标准容器类是用类型来参数化的：你能创建一个std::vector 但是经常会有因为容器指针，造成内存泄露；std::vector 附：vector源代码 #ifndef VEC_H_H #define VEC_H_H #include "Myexcep.h" #include #include #include #include #include using namespace std; template class Vec{ public: typedef T* iterator; typedef const T* const_iterator; typedef size_t size_type; typedef T value_type; public: Vec(); Vec(size_type,const T&); Vec(const Vec &); Vec& operator=(const Vec&); ~Vec(); T& operator[](size_type index); const T& operator[](size_type index) const; void push_back(const T&); void pop_back(); void erase(size_type); size_type size() const {return (m_finished - m_start);} iterator begin() {return m_start;} const_iterator begin() const {return m_start;} iterator end() {return m_finished;} const_iterator end() const {return m_finished;} private: void create(); void create(size_type,const T&); void create(const_iterator,const_iterator); void uncreate(); T* allocate(size_type); void init_fill(iterator,iterator,const T&); void init_copy(const_iterator,const_iterator,iterator); void grow(); void append_element(const T&); private:
相关主题
文本预览