序列式容器
vector
线性的动态分配存储空间。定义如下
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; // 内存的结束地址 // 关键函数,在某个位置插入一个数据 void insert_aux(iterator position, const T& x); // 使用配置器释放内存 void deallocate() { if (start) data_allocator::deallocate(start, end_of_storage - start); } // 申请并初始化一块大小为n的内存,并初始化为value 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 { return size_type(end_of_storage - begin()); } // 容器是否为空 bool empty() const { return begin() == end(); } // 重载[]运算符,取出对应position的数据,下标从0开始 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()) // 将position + 1到finish的数据,拷贝到position开始的地方 copy(position + 1, finish, position); --finish; destroy(finish); return position; } // 修改vector的大小,新的size比老的size小,直接删除多余的数据;新的size比老的size大,直接插入 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的迭代器是普通指针,支持随机存取,提供的是Random Access Iterators。
template<class T, class Alloc = alloc> class vector{ public: typedef T value_type; typedef value_type* iterator;//vector的迭代器是普通指针 ... };
vector的数据结构
vector采用的数据结构是线性连续空间。以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围,并以迭代器end_of_storage指向整块连续空间(含备用空间)的尾端。
template<class T,class Alloc = alloc> class vector{ ... protected : iterator start ; //表示目前使用空间的头 iterator finish ; // 表示目前使用空间的尾 iterator end_of_storage ; //表示目前可用空间的尾 };
一个vector的容量永远大于或等于其大小,当容量等于大小时,再增加新元素,便要进行重新配置,移动数据和释放原空间3个过程。
vector的内存构造与管理
用push_back插入元素到尾端时,该函数检查是否还有备用空间,如果有备用空间就在备用空间上构造元素,并调整迭代器finish,使vector变大,如果没有就扩充空间。以原大小的两倍扩充空间,然后将原内容拷贝过来,释放原空间。所以对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器都失效。
void push_back() { if (finish != end_of_storage) {//还有备用空间 construct(finish); ++finish; //调整迭代器finish } else//没有备用空间 insert_aux(end(), x); } template<class T, class Alloc> void vector<T, Alloc>::insert_aux(iterator position, const T&x){ if (finish != end_of_storage){//还有备用空间 construct(finish, *(finish - 1)); //在备用空间起始处构造一个元素,以vector最后一个元素值为其初值 ++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 new_size = old_size != 0 ? 2 * old_size : 1; iterator new_start = data_allocator::allocate(new_size); iterator new_finish = new_start; try{ new_finish = uninitialized_copy(start, position, new_start);//将原vector的内容拷贝到新vector construct(new_finish, x); ++new_finish; new_finish = uninitialzed_copy(position, finish, new_finish);//将安插点的原内容也拷贝过来 } catch (excetion e){ destroy(new_start, new_finish);//如果发生异常,析构移动的元素,释放新空间 data_allocator::deallocate(new_start, new_size); }//析构并释放原空间 destroy(begin(), end()); deallocator(); start = new_start; //调整迭代器 finish = new_finish; end_of_storage = new_start + new_size;//调整迭代器 } }
vector元素操作:pop_back,erase,clear,insert
pop_back:finish前移放弃尾端元素,然后析构。
void pop_back(){ --finish; destory(finish); }
erase:从position到finish中的元素向前移动,然后删除finish处元素。
iterator erase(iterator first,iterator last){//清除区间[first,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; }
insert:
相关推荐
jokewinl 2020-06-28
ericasadun 2020-06-03
choupiaoyi 2020-05-29
kaixinfelix 2020-05-01
jeonkc 2020-04-23
lsfreeing 2020-01-24
lsfreeing 2020-01-01
徐建岗网络管理 2019-12-24
风吹夏天 2019-12-05
Joymine 2013-07-11
qscool 2019-10-29
dxyadc 2019-10-26
Bloddy 2019-10-20
galoisgodel 2012-02-12
一亩半分地 2012-06-03
lickylin 2019-06-28
spinachcqb 2019-06-27