动态数组…
以下是Vector定义的源代码摘录。(函数部分我就不写了)
用它来作为引子…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
template <class T, class Alloc = alloc> 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<value_type, Alloc> data_allocator; iterator start; //表示目前使用空间的头 iterator finish; //表示目前使用空间的尾 iterator end_of_storage; //表示目前可用空间的尾 //... }; |
可以看到定义了很多类型，而真正的数据只有三个：
使用空间头尾和容量的尾…
Vector的迭代器：
Vector维护的是一个连续的线性空间，所以不论其元素型别是什么，普通指针都可以作为Vector的迭代器并满足所以的必要条件，因为Vector迭代器所需要进行的操作，普通指针天生就具备。
Vector支持随机存取，普通指针也有着这样的能力。
所以vector提供的是 Random Access Iterator.
可以看到上文的迭代器定义：
|
1 |
typedef value_type* iterator; //迭代器 |
根据上述的定义，如果程序猿or媛们写出这样的代码：
|
1 2 |
vector<int>::iterator ivite; vector<Shape>::iterator svite; |
实际上定义的是 int* ivite; 和 Shape* svite;…
Vector的数据结构：
Vector的数据结构非常简单：线性连续空间。
它以两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已被使用的范围，
用迭代器 end_of_storage 指向整块连续空间(包括备用空间)的尾端。
|
1 2 3 |
iterator start; //表示目前使用空间的头 iterator finish; //表示目前使用空间的尾 iterator end_of_storage; //表示目前可用空间的尾 |
为了降低空间配置时的速度成本，vector实际配置的大小可能比需求量更大一些，以备将来可能扩充。
这便是容量(capacity)的概念。
运用start、finish、end_of_storage 三个迭代器，便可以轻易地提供首位标示，大小，容量，空容器判断，等等函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public: iterator begin() { return start; } iterator end() { return end; } 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[](size_type n) { return *(begin()+n); } reference front() { return *begin(); } reference back() { return *(end()-1); } //... |
Vector的构造与内存管理：constructor、push_back
以代码为引导(认真看，相比侯捷的还多加了几个用例)：
展示了一个vector从定义到增加减少元素等情况下的容量变化。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v; //V-Size = 0 cout << "V-Size = " << v.size() << endl; //V-Capacity = 0 cout << "V-Capacity = " << v.capacity() << endl << endl; v.push_back(0); //V-Size = 1 cout << "V-Size = " << v.size() << endl; //V-Capacity = 1 cout << "V-Capacity = " << v.capacity() << endl << endl; v.push_back(0); //V-Size = 2 cout << "V-Size = " << v.size() << endl; //V-Capacity = 2 cout << "V-Capacity = " << v.capacity() << endl << endl; vector<int> iv(2,9); //Size = 2 cout << "Size = " << iv.size() << endl; //Capacity = 2 cout << "Capacity = " << iv.capacity() << endl << endl; iv.push_back(1); //Size = 3 cout << "Size= " << iv.size() << endl; //Capacity = 4 cout << "Capacity= " << iv.capacity() << endl << endl; iv.push_back(2); //Size = 4 cout << "Size= " << iv.size() << endl; //Capacity = 4; cout << "Capacity= " << iv.capacity() << endl << endl; iv.push_back(3); //Size = 5 cout << "Size= " << iv.size() << endl; //Capacity = 8 cout << "Capacity= " << iv.capacity() << endl << endl; iv.push_back(4); //Size = 6 cout << "Size= " << iv.size() << endl; //Capacity = 8 cout << "Capacity= " << iv.capacity() << endl << endl; //9 9 1 2 3 4 for(int i=0;i<iv.size();i++) cout << iv[i] << " "; cout << endl << endl; iv.push_back(5); //Size = 7 cout << "Size= " << iv.size() << endl; //Capacity = 8 cout << "Capacity= " << iv.capacity() << endl << endl; //9 9 1 2 3 4 5 for(int i=0;i<iv.size();i++) cout << iv[i] << " "; cout << endl << endl; iv.pop_back(); iv.pop_back(); //Size= 5 cout << "Size= " << iv.size() << endl; //Capacity = 8 cout << "Capacity= " << iv.capacity() << endl << endl; iv.pop_back(); //Size = 4 cout << "Size= " << iv.size() << endl; //Capacity = 8 cout << "Capacity= " << iv.capacity() << endl << endl; vector<int>::iterator ivite = find(iv.begin(),iv.end(),1); if(ivite != iv.end()) iv.erase(ivite); //Size = 3 cout << "Size= " << iv.size() << endl; //Capacity = 8; cout << "Capacity= " << iv.capacity() << endl << endl; //9 9 2 for(int i=0;i<iv.size();i++) cout << iv[i] << " "; cout << endl << endl; ivite = find(iv.begin(),iv.end(),2); if(ivite != iv.end()) iv.insert(ivite,3,7); //Size = 6 cout << "Size= " << iv.size() << endl; //Capacity = 8 cout << "Capacity= " << iv.capacity() << endl << endl; //9 9 7 7 7 2 for(int i=0;i<iv.size();i++) cout << iv[i] << " "; cout << endl << endl; iv.clear(); //Size = 0 cout << "Size= " << iv.size() << endl; //Capacity = 8 cout << "Capacity= " << iv.capacity() << endl << endl; iv.insert(iv.begin(),9,7); //Size = 9 cout << "Size= " << iv.size() << endl; //Capacity = 9 cout << "Capacity= " << iv.capacity() << endl << endl; } |
相信，如果认真看了这个代码的人，已经理解了Vector的内存增长规律了。
接下来是它的空间配置：
vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位。
|
1 |
typedef simple_alloc<value_type, Alloc> data_allocator; |
于是，data_allocator:allocate(n) 表示配置n个元素空间。
vector 提供了很多 constructs ，其中一个允许我们指定空间大小及初值：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
protected: //... //填充并初始化 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, cosnt T& x) { iterator result = data_allocator::allocate(n); uninitialized_fill_n(result, n, x); return result; } public: //... //默认初始化，全为0(NULL) 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); } explict vector(size_type n) { fill_initialize(n,T()); } //析构函数 ~vector() { destroy(start,finish); deallocate(); } //... |
uninitialized_fill_n()会根据第一参数的型别特征决定使用算法fill_n或者反复调用construct()来完成任务。
当我们以 push_back()将新元素插入于vector尾端时，该函数先检查是否有备用空间，如果有备用空间就直接构造元素，并调整finish，如果没有备用空间就扩充空间(重新配置空间，移动数据，释放原空间)。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void push_back(const T& x) { if(finfish != end_of_storage) { construct(finish,x); ++finish; } else { insert_aux(end(),x);//vector的一个成员函数 } } |
insert_aux 是vector 的一个成员函数，其具体实现如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
template<class T, class Alloc> void vector<T, Alloc>::insert_aux(iterator position, const T& x) { //如果还有空间 if(finish != end_of_storage) { //在备用空间起始处构造一个元素，并以vector最后一个元素为其初值 construct(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*old_size : 1; //如果原大小为0，则配置为 1 //如果原大小不为0，则配置为原大小的两倍 //前半段放置旧数据，后半段放置新数据 //实际配置 iterator new_start = data_allocator::allocate(len); iterator new_finish = new_start; try { //原数据拷贝过来 new_finish = uninitialized_copy(start,position,new_start); //新元素初值设为 x construct(new_finish,x); //调整 ++new_finish; //将安插点的原内容也拷贝过来 new_finish = uninitialized_copy(position,finish,new_finish); } catch(...) { destroy(new_start,new_finish); data_allocator::deallocate(new_start,len); throw; } //析构释放 原vector destroy(begin(),end()); deallocate(); //调整迭代器，指向新 vector start = new_start; finfish = new_finish; end_of_storage = new_start + len; } } |
所以可以看到：
动态增加大小，是以原大小的两倍去配置另一块空间，然后将原数据拷贝过来。
所以，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。
vector 的元素操作：
pop_back, erase, clear, insert
vector提供的元素操作很多，这里选部分常用的讲。
pop_back 将尾端元素拿掉，并调整大小。
|
1 2 3 4 5 |
void pop_back() { --finish; destroy(finish); } |
erase清除元素：
|
1 2 3 4 5 6 7 8 9 10 11 |
iterator erase(iterator first, iterator last) { //将last到finish的内容拷贝到first位置 iterator i = copy(last, finish, first); //删除 最后几个不需要的元素 destroy(i,finish); //调整finish的值 finish = finish - (last - first); //返回删除部分头部 return first; } |
下图可以很清楚的表达：
如果 erase是清除某个位置上的元素：
|
1 2 3 4 5 6 7 8 9 10 |
iterator erase(iterator position) { if(position + 1 != end()) { copy(position + 1, finish, position); } --finish; destroy(finfish); return position; } |
上面这段代码比较清楚，就是把后面的元素往前覆盖了一位，然后清除最后一个元素。
insert插入元素：
insert有三种情况：
- 备用空间>=新增元素个数；插入点之后的现有元素>新增元素个数
- 备用空间>=新增元素个数；插入点之后的现有元素<=新增元素个数
- 备用空间<新增元素个数
以上三种情况的处理方法不相同，可以用三张图来说明：
1. 将前三个元素拷贝过去，然后插入新元素。
2. 先插入一部分元素，然后将前面的元素放到后面，再插入一部分元素。
3. 流程清晰，不讲解了。
它的源代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
template <class T, class Alloc> void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) { //如果插入的元素不为 0~ if(n != 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) { uninitialized_copy(finish - n, finish, finish); finish += n; copy_backward(position, old_finish - n, old_finish); fill(position, position + n, x_copy); } //插入点后元素个数 小于 新增元素个数 else { 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 { //获取原空间大小与新空间大小 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 = start + len; } } } |
好像这里就结束了…Vector一些比较重要的操作。
【STL】Vector
大神啊！！！！！
小渣一枚罢了…