区别
- array是静态空间，一旦配置了就不能改变。
- 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 |
template <class T,class Alloc = alloc> class vector { public: //vector嵌套型别定义 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: //simple_alloc是SGI STL的空间配置器 typedef simple_alloc<value_type,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); } void fill_initialize(size_type n,const T& value) { start = allocate_end_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 { return size_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() { 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());} protected: //配置空间并填满内容 iterator allocate_and_fill(size_type n,const T& x) { iterator result = data_allocator::allocate(n); uninitialized_fill_n(result,n,x);//全局函数 return result; } } |
迭代器
vector维护的是一个连续线性空间，所以不论其元素型别为何，普通指针都可以作为vector的迭代器而满足所有必要条件
因为vector所需要的操作行为，如
operator*,operator->,operator++,operator--,operator+,operator-,operator+=,operator-=,普通指针天生就具备。vector支持随机存取，而普通指针正是有着这样的能力。
|
1 2 |
vector<int>::iterator ivite;//ivite类型：int* vector<Shape>::iterator svite;//svit类型：Shape* |
数据结构
vector所采用的数据结构非常简单：线性连续空间【顺序表】
为了降低空间配置时的速度成本，vector实际分配的空间大小可能比客户端需求量更大一些，这个实际分配的空间大小是
capacity()的概念增加新元素时，如果超过当时的容量了，则容量会扩充到两倍，如果两倍还不够用，就扩充到足够大的容量。
关于vector的capacity增长规则，根据我实际的测试结果，以及查阅资料来看，这个视平台而不同。
比如STL源码剖析这本书里，这里写的是以两倍的方式增长，我的测试结果显示是以1.5倍增长（向下取整）。另外，查阅资料发现，有的平台下，别人测试显示又是以两倍的方式增长。
|
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 |
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; iterator new_start = data_allocator::allocate(len); 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::deallocate(new_start,len); throw; } //释放原vector destroy(begin(),end()); deallocate(); //调整迭代器，指向新vector start = new_start; finish = new_finish; end_of_storage = new_start + len; } } |
操作
|
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 |
void pop_back() { --finish; destroy(finish); } iterator erase(iterator first,iterator last) { iterator i = copy(last,finish,first); destroy(i,finish); finish = finish - (last - first); return first; } //清除某个位置上的元素 iterator erase(iterator position) { if(position + 1 != end) copy(position + 1, finish,position); --finish; destroy(finish); return position; } void clear() {erase(begin(),end());} void vector<T,Alloc>::insert(iterator position,size_type n,const T& x) { 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 += 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,postion,new_start); new_finish = uninitialized_fill_n(new_finish,n,x); new_finish = uninitialized_copy(position,finish,new_finish); } # ifdef __STL_USR_EXCEPTIONS catch(...) { destroy(new_start,new_finish); data_allocator::deallocate(new_start,len); throw; } # endif /*__STL_USR_EXCEPTIONS*/ destroy(start,finish); deallocate(); start = new_start; finish = new_finish; end_of_storage = new_start + len; } } } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ C++_可以重载的运算符12/22
- ♥ Soui四05/23
- ♥ Spdlog记述：二07/09
- ♥ breakpad记述：Windows下静态库的编译使用03/15
- ♥ CLion：配置C++下Nasm开发环境（debian）08/06
- ♥ C++标准库_cfenv02/14