南宁手机网站设计策划,昆明软件公司有哪些,电商产品开发员有前景吗,聊城网站建设动态目录 1.序列式容器和关联式容器 2.vector的定义和结构 3.vector的构造函数和析构函数的实现 4.vector的数据结构以及实现源码 5.vector的元素操作 前言 本系列将重点对STL中的容器进行讲解#xff0c;而在容器的分类中#xff0c;我们将容器分为序列式容器和关联式容器。本章…目录 1.序列式容器和关联式容器 2.vector的定义和结构 3.vector的构造函数和析构函数的实现 4.vector的数据结构以及实现源码 5.vector的元素操作 前言 本系列将重点对STL中的容器进行讲解而在容器的分类中我们将容器分为序列式容器和关联式容器。本章作为容器的实现源码的讲解将简单介绍这两种类型的容器的区别再对每一个类型所含的容器的实现源码进行讲解。 序列式容器和关联式容器 序列式容器按照元素的添加顺序来组织元素。提供了一种线性的数据结构可以快速何位置的元素插入和删除操作可能需要移动其他元素 关联式容器通过键值对来存储元素并且通常使用某种形式的平衡树或哈希表来组织元素。特别是对于大量数据关联式容器在查找、插入和删除操作上通常具有较高的效率 序列式容器和关联式容器的区别
序列式容器关联式容器存储方式 元素添加顺序存储 按键的顺序或哈希值存储访问速度支持快速随机访问不支持快速随机访问插入和删除在插入和删除时要移动元素可能较慢能提供快速的插入和删除操作元素唯一性不保证元素的唯一性保证元素的唯一性迭代器类型随机访问迭代器双向迭代器或正向迭代器 表1.序列式容器和关联式容器的区别 vector的定义和结构 vector属于序列式容器定义在头文件vector中但是SGI STL将其实现放在更底层的stl_vector.h头文件中。vector和数组很像但是vector属于动态存储空间能自动随着元素的插入而自行扩充空间以容纳新的元素数组只能通过new或者malloc重新分配更大的空间并将元素移动到新的空间。 在阅读过《STL源码刨析迭代器概念与Traits编程方法》后我们应该清楚以下几点 1.每一个容器和具体的实现算法是分开定义的而为了将容器和算法串联在一起我们要为其定义迭代器(PS:vector的迭代器类型为随机迭代器因为使用vector容器时支持下标操作) 2.针对迭代器的类型我们还需要对其封装并判断传入模板的类型(Traits编程方法) 3.每一个容器都需要为其分配内存空间所以我们还需要一个空间配置器 在以上三点的基础上我们还需要对容器定义三个迭代器分别指向使用空间的头使用空间的尾和空闲空间的尾。所以我们的vector容器的结构应该大体如下
//vector容器的大体结构
templateclass T, class Alloc 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; //传入的元素之间的距离
protector:typedef simple_allocvalue_type, Alloc data_allocator; //配置器的定义iterator start; //表示可用空间的头iterator finish; //表示可用空间的尾iterator end_od_storage;//表示空闲空间的尾
}//simple_alloc配置器的实现
templateclass T, class Alloc alloc
class simple_alloc{
public://分配空间static T* allocate(size_t n){ return 0 n ? (T*)Alloc:: allocate(n * sizeof(n)); }static T* allocate(void){ return (T*)Alloc :: allocate(sizeof(T)); }//释放空间statice T* deallocate(T* p, size_t n){if(0 ! n){ Alloc::deallocate(p,n * sizeof(T));}}statice T* deallocate(T* p){ Alloc::deallocate(p,sizeof(n));}
} vector的构造函数和析构函数的实现 vector作为常用的容器类型无论是在项目中还是在算法题中常常出现所以我们对其构造函数并不陌生以下便是的构造函数和析构函数的实现PS千万不要在容器中存放指针指针如果是使用new进行分配的并不能直接通过调用vector的析构函数对其元素进行释放必须得遍历整个容器依次释放否则会存在内存泄漏
/* 针对代码中的uninitalized_fill_n()和destroy函数请参见《STL源码刨析空间配置器(allocator)》中内存基本处理函数 *///vector容器的构造函数
vecotr() : start(0), finish(0), end_of_storage(0){} //列表初始化
vector(int n, const T value){ fill_initialize(n,value); }
vector(long n,const T value){ fill_initialize(n,value); }
explicit vector(szie_type n){ fill_initialize(n,T()); } //explicit用于禁止隐式转换
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 new_size, const T x){iterator result data_allocator::allocate(n); //分配空间uninitalized_fill_n(result,n,x); return result;
}//vector容器的析构函数
~vector(){destroy(start,finish);deallocate();
}void deallocate(){if(start){data_allocator::deallocate(start, end_of_storage - start); //释放空间}
} vector的数据结构以及实现源码 vector容器的数据结构采用的是线性连续空间以定义的迭代器start和finish分别指向以及使用的空间的头部和尾部(范围)并以迭代器end_of_storage指向分配的空间的尾部PSstart和finish指向的是使用的空间end_of_storage指向的分配的全部空间的尾部使用这三个迭代器我们将可以使用首尾元素容器大小整体容量空容器的判断下标运算符[]头元素和尾元素的值的接口函数整体实现如下
//返回头元素指针
iterator begin(){ return start; }
//返回尾元素指针
iterator end() { return finish; }
//返回容器使用的空间大小
size_type size() const { return szie_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); } 阅读本段可能会产生疑问。全部空间是什么已经使用的空间是什么为什么back返回的值是尾指针-1后的值针对这些疑问获取阅读下图便会清晰 图1.vector的数据结构 参考上图可知迭代器finish指向的并不是最后一个元素的地址而是指向最后一个元素的地址的下一个地址。而且size()函数返回的是已经使用的空间大小capacity()函数返回的是系统分配的整体空间的大小 vector的元素操作 关于vactor容器的元素操作我们常用的便是push_back()pop-back()clear()和insert()在此基础上还要有一个用于清除元素的操作erase()其中clear()函数也是调用的erase()函数。针对以上的四个函数实现如下。 1.push_back()函数实现源码
//push_back函数主要用于在容器的尾部插入元素
void push_back()(const T x){if(finish ! end_of_storage){ //存在多余空间construct(finish,x); //参见《STL源码刨析空间配置器(allocator)》配置器初始化finish;}elseinsert_aux(end(),x);
}template class T, class Alloc
void vectorT,Alloc::insert_aux(iterator position, const T x){if(finish ! end_of_storage){ //存在多余空间construct(finish,*(finish - 1));finish; //调整尾指针T x_copy x;copy_bcakward(position,finish - 2,finish - 1);*position x_copy;}else{ //无多余空间const size_type old_size size(); //当前使用空间const size_type len ild_size ! 0 ? 2 * old_size : 1;//当前空间为0则分配一个内存大小当前空间不为0则分配2倍的当前空间的大小iterator new_start data_allocator::allocate(len);iterator new_finish new_statr;try{ //尝试将先前的元素拷贝到新申请的空间new_finish uninitialized_copy(start,positon,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;}destory(begin(),end()); //释放原来容器的空间deallocate();//更新迭代器start new_start;finish new_finish;end_of_storage new_start len; }
} 2.pop_back()函数实现源码
//pop_back()函数主要用于将容器尾部的元素删除
void pop_back(){--finish;destroy(finish); //使用配置器释放空间
} 3.erase()函数实现源码
//erase()函数主要用于清除容器中的指定范围的元素或指定元素
iterator erase(iterator first, iterator last){ //清除容器中[first,last)范围中的元素iterator i copy(last,finish,first); //将last后的元素复制到firstdestroy(i,finish); //释放空间finish finish - (last - first);return finish;
}iterator erase(iterator position){ //清除指定位置的元素if(position 1 ! end())copy(position 1, finish, position);--finish;destory(finish);return position;
} 针对erase()函数可参考下图直观了解其实现过程 图2.erase()函数的调用过程 4.clear()函数实现源码
//clear()函数主要用于将容器的元素删除
void clear() { erase(begin(),end()); } 5.insert()函数实现源码
//insert()函数主要用于将容器的元素插入
templateclass T, class Alloc
void vectorT, Alloc::insert(iterator position, size_type n, const T x){if(n ! 0){ //插入的元素个数不为0if(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(finih, n - elems_after, x_copy);//将多出的插入元素填充到空闲内存中finish n;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 mew_start;_STL_TRY{ //尝试将元素移动至新的空间new_finish uninitialized_copy(start,position,new_stars);//将插入点前的当前容器的元素复制到新的空间new_finish uninitialized_fill_n(new_finish,n,x);//将插入的元素填充至新的空间new_finish uninitialized_copy(position,finish,new_finish);//将插入点后的当前容器的元素复制到新的空间}#ifdef _STL_USE_EXCEPTIONScatch(...){ //捕获异常destroy(new_stzrt,new_finish);data_allocator::deallocate(ner_start,len);throw;}#endif /*_STLUSE_EXCEPTIONS*/ //无异常destroy(start,finish);deallocate();start new_start;finish new_finish;end_of_atorage new_start len;}}
} 以上便是本章的内容针对insert()函数个人觉得关键点在于插入的元素的个数如果插入的元素个数大于当前插入点到尾指针的元素个数则向把旧元素分配至新的空间内再插入新的元素。如果插入的元素个数小于等于当前插入点到尾指针的元素个数则先将要插入的多出来的元素填充至尾指针后多余的空间内再将旧元素复制到新的空间内最后吧插入的元素再填充进去
