56网站可以做电子相册,蔬菜类网站建设规划书,网络营销和电子商务的区别,林州网站建设服务⛅️一 vector概述
vector的使用语法可以参考文章#xff1a; 总的来说#xff1a;vector是可变大小数组 特点#xff1a; 支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢 元素保存在连续的内存空间中#xff0c;因此通过下标取值非常快 在容器中间位置添加…
⛅️一 vector概述
vector的使用语法可以参考文章 总的来说vector是可变大小数组 特点 支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢 元素保存在连续的内存空间中因此通过下标取值非常快 在容器中间位置添加或删除元素非常耗时 一旦vector内存不足重新申请内存之后和原vector相关的指针引用迭代器都失效。内存重分配耗时很长 通常使用vector是最好的选择如果没有什么特殊要求最好使用vector 与其他容器的比较 ⛅️二、vector定义摘要
vector定于与stl_vector.h头文件中
//alloc是SGI STL的空间配置器
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_allocvalue_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_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(); }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 Tvalue) { fill_initialize(n,value); } explicit vector(size_type n) { fill_initialize(n,T()); }~vector()destroy(start, finish); //全局函式见前面文章destroy函数的介绍deallocate(); //这是 vector的㆒个 member function}reference front() { return *begin(); } // 第一个元素reference back() { return *(end() - 1); } // 最后一个元素void push_back(const T x) { // 将元素安插至最尾端if (finish ! end_of_storage) {construct(finish, x); //全局函式见前面文章construct函数的介绍finish;}elseinsert_aux(end(), x); //这是 vector的一个member function}void pop_back() { // 将最尾端元素取出--finish;destroy(finish); // 全局函式见前面文章destroy函数的介绍}iterator erase(iterator position) { // 清除某位置上的元素if (position 1 ! end())copy(position 1, finish, position); // 后续元素往前搬移--finish;destroy(finish); // 全局函式见前面文章destroy函数的介绍return position;}void resize(size_type new_size, const T x) {if (new_size size())erase(begin() new_size, end());elseinsert(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); // 全局函式见前面uninitialized_fill_n函数的介绍return result;}⛅️三、vector的迭代器
vector维护的是一个连续线性空间所以不论其元素类别是什么普通指针都可以作为vector的迭代器而满足所有必要条件 vector迭代器支持有操作有普通指针也具备 operator*、operator-、operator、operator–、operator、operator-、operator、operator- vector支持随机存取而普通指针正有着这样的能力所以vector提供的是随机访问迭代器Random Access iterators vector的迭代器定义如下
template class T, class Alloc alloc
class vector {
public:typedef T value_type;typedef value_type* iterator; //vector的迭代器是原生指标...
};例如
vectorint::iterator ivite; //等同于int* ivite;
vectorShape::iterator svite; //等同于Shape* svite;⛅️四、vector的数据结构
vector的数据结构非常简单一个线性连续空间 下面介绍vector的3个数据结构 start表示目前使用空间的头 finish表示目前使用空间的尾 end_of_storage表示目前可用空间的尾
template class T, class Alloc alloc
class vector {
...
protected:iterator start; //表示目前使用空间的头iterator finish; //表示目前使用空间的尾iterator end_of_storage; //表示目前可用空间的尾...
};说明为了降低空间配置时的速度成本vector实际配置的大小可能比客户端需求量更大一些以备将来可能的扩充。这便是容量的概念。也就是说一个vector的容量永远大于或等于其大小。一旦容量等于大小下次再新增元素时就需要新开辟一块空间。如下图所示 运用start、finish、end_of_storage三个迭代器vector提供了首尾标示、大小、容量、空容器判断、注标[]运算符、最前端元素值、最后端元素值…等机能如下
template class T, class Alloc alloc
class vector {
...
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); }reference front() { return *begin(); }reference back() { return *(end() - 1); }...
};⛅️五、vector的构造与内存管理constructor、push_back
vector的内存管理vector默认使用alloc做为空间配置器并据此另外定义了一个data_allocator为的是更方便以元素大小为配置单位
template class T, class Alloc alloc
class vector {
protected:// simple_alloc见前面文章介绍typedef simple_allocvalue_type, Alloc data_allocator;...
};于是data_allocator::allocate(n) 表示配置n个元素空间 构造函数vector提供许多构造函数其中一个允许我们指定空间大小及初值
//构造函数允许指定vector大小n和初值value
vector(size_type n, const T value) { 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;
}// 配置而后充填
iterator allocate_and_fill(size_type n, const T x) {iterator result data_allocator::allocate(n); //配置n个元素空间uninitialized_fill_n(result, n, x); //全局函式会根据第1个参数类型特性决定使用算法fill_n()或反复调用construct()来完成任务return result;
}push_back()函数当我们以push_back() 将新元素安插入于vector尾端时该函式首先检查是否还有备用空间如果有就直接在备用空间上建构元素并调整迭代器finish使vector变大。如果没有备用空间了就扩充空间重新配置、搬移数据、释放原空间。push_back()原型如下
void push_back(const T x) {if (finish ! end_of_storage) { //还有备用空间construct(finish, x); //全局函式finish; //调整水位高度}else //已无备用空间insert_aux(end(), x); // vector member function见下
}template class T, class Alloc
void vectorT, 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 {// 将原 vector 的内容拷贝到新vectornew_finish uninitialized_copy(start, position, new_start);// 为新元素设定初值 xconstruct(new_finish, x);// 调整水位new_finish;// 将原vector的备用空间中的内容也忠实拷贝过来new_finish uninitialized_copy(position, finish, new_finish);}catch(...) {// commit or rollback semantics.destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}//析构并释放原vectordestroy(begin(), end());deallocate();// 调整迭代器指向新vectorvector start new_start;finish new_finish;end_of_storage new_start len;}
}⛅️六、vector内存重分配策略
vector的内存重分配策略 vector是以数组的形式存储的当往vector中增加元素时如果vector的容量不足那么vector就会进行扩容 扩容的规则是并不是在原空间之后接续新空间因为无法保证原空间之后尚有可供配置的空间而是申请一块比现在大的新的内存空间gcc和vc申请规则不同见下面介绍然后原来内存中的内容拷贝到新内存中然后释放原来的内存 重点在gcc和vc的环境下vector的扩容规则是不一样的 注意重点对vector 的任何操作一旦引起空间重新配置指向原vector的所有迭代器就都失效了。这是程序员易犯的一个错误务需小心
#include iostream
#include vectorusing namespace std;int main()
{std::vectorint iv;iv.push_back(1);cout iv.capacity() endl; //1iv.push_back(1);cout iv.capacity() endl; //2iv.push_back(1);cout iv.capacity() endl; //3iv.push_back(1);cout iv.capacity() endl; //4iv.push_back(1);cout iv.capacity() endl; //6iv.push_back(1);iv.push_back(1);cout iv.capacity() endl; //9return 0;
}⛅️七、vector的元素操作pop_back、erase、clear、insert
所提供的元素操作动作很多不就在此文章中一一说明 pop_back
//将尾端元素拿掉并调整大小
void pop_back() {--finish; //将尾端标记往前移一格表示将放弃尾端元素destroy(finish); // destroy是全局函式
}erase
// 清除[first,last)中的所有元素
iterator erase(iterator first, iterator last) {iterator i copy(last, finish, first); //copy是全局函式destroy(i, finish); //destroy是全局函式finish finish - (last - first);return first;
}下图是上面这个erase函数的版本
// 清除某个位置上的元素
iterator erase(iterator position) {if (position 1 ! end())copy(position 1, finish, position); //copy是全局函式--finish;destroy(finish); //destroy是全局函式return position;
}clear
//清除容器内所有元素
void clear() { erase(begin(), end()); }insert
//从position开始插入n个元素元素初值为x
templateclass T,class Alloc
void vectorT, Alloc::insert(iterator position, size_type n, const T x)
{if (n ! 0) { //当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; // 将vector尾端标记后移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);// 以下配置新的vector空间iterator new_start data_allocator::allocate(len);iterator new_finish new_start;STL_TRY {// 以下首先将旧vector的安插点之前的元素复制到新空间new_finish uninitialized_copy(start, position, new_start);// 以下再将新增元素初值皆为n填入新空间new_finish uninitialized_fill_n(new_finish, n, x);// 以下再将旧 vector 的插入点之后的元素复制到新空间new_finish uninitialized_copy(position, finish, new_finish);}
# ifdef STL_USE_EXCEPTIONScatch(...) {// 如有异常发生实现commit or rollback semantics.destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
# endif /* STL_USE_EXCEPTIONS */// 以下清除并释放旧的vectordestroy(start, finish);deallocate();// 以下调整水位标记start new_start; finish new_finish; end_of_storage new_start len;}
}注意插入完成后新节点将位于哨兵迭代器即上缪按的position标示出插入点 所指之节点的前方——这是STL对于“插入操作”的标准规范。下面的图片展示了insert(position,n,x)的操作 备用空间新增元素个数的情况 ①备用空间2新增元素个数2 ②插入点之后的现有元素个数3新增元素个数2 ③插入点之后的现有元素个数2新增元素个数3 备用空间新增元素个数的情况例如下面备用空间2新增元素个数n3
