工信部信息备案网站首页,厦门网站建设案例,沧州公司网站建设,本机可以做网站的服务器容器的概观和分类
array 数组 、list 链表、tree树 、stack堆栈、queue队列、hash table散列表、set集合、map映射表根据数据在容器中的排列顺序#xff0c;将上述数据结构分为序列式和关联式两种类型SGI STL使用内缩方式来表达基层和衍生层之间的关系衍生不是派生#xff0…容器的概观和分类
array 数组 、list 链表、tree树 、stack堆栈、queue队列、hash table散列表、set集合、map映射表根据数据在容器中的排列顺序将上述数据结构分为序列式和关联式两种类型SGI STL使用内缩方式来表达基层和衍生层之间的关系衍生不是派生本质上是一种内含的关系例如heap内含vectorpriority-queue内含heapstack 和 queue都内含dequeset map multiset multimap 内含一个 RB-treehash_x都内含hashtable序列式容器内部元素都可序但是未必有序。C本身提供了一个序列式容器arraySTL提供了vector、list、deque、priority_queue等stack 和 queue都是在deque的基础上改头换面形成的技术上将其归类为一种 配接器
Vector
vector类似于array二者唯一的差别在于 空间的运用的灵活性。array是静态空间一旦配置就不会改变大小如果存储空间不够需要申请空间进行元素的拷贝这些操作均需要用户自己来执行最后还需要释放先前拥有的区间。 具体操作(配置新的空间 | 数据移动 | 释放先前的内存空间 )vector是动态空间随着元素的加入内部的实现机制会自行进行内存空间的扩充从而容纳新的元素vector的实现技术关键在于其对于大小的控制和重新配置的时候对于数据的移动的效率。第二次申请的内存空间是先前的两倍SGI vector将vector实现于更加底层的stl_vector.h 具体使用的时候直接引入vector头文件即可
#include iostream
#include new //for placement new
#include cstddef //for ptrdiff_t size_t
#include cstdlib //for exit
#include climits //for UINT_MAXnamespace Chy{template class Tinline T* _allocate(ptrdiff_t size,T*){std::set_new_handler(0);T* tmp (T*)(::operator new((std::size_t)(size * sizeof (T))));if (tmp 0){std::cerr out of memory std::endl;exit(1);}return tmp;}templateclass Tinline void _deallocate(T* buffer){::operator delete (buffer);}templateclass T1,class T2inline void _construct(T1 *p,const T2 value){new(p) T1 (value); //没看懂}template class Tinline void _destroy(T* ptr){ptr-~T();}template class Tclass allocator{public:typedef T value_type;typedef T* pointer;typedef const T* const_pointer;typedef T reference;typedef const T const_reference;typedef std::size_t size_type;typedef ptrdiff_t difference_type;templateclass Ustruct rebind{typedef allocatorUother;};pointer allocate(size_type n,const void * hint 0){return _allocate((difference_type)n,(pointer)0);}void deallocate(pointer p,size_type n){_deallocate(p);}void construct(pointer p,const T value){_construct(p,value);}void destroy(pointer p){_destroy(p);}pointer address(reference x){return (pointer)x;}const_pointer const_address(const_reference x){return (const_pointer)x;}size_type max_size()const{return size_type(UINT_MAX/sizeof (T));}};
}templateclass T,class Alloc
class simple_alloc{
public:static T* allocate(std::size_t n){return 0n?0:(T*)Alloc::allocate(n * sizeof(T));}static T* allocate(void){return (T*)Alloc::allocate(sizeof (T));}static void deallocate(T* p,size_t n){if (n!0){Alloc::deallocate(p,n * sizeof(T));}}static void deallocate(T* p){Alloc::deallocate(p,sizeof(T));}
};//如果是copy construction 等同于assignment而且destructor 是 trivial以下就会有效
//如果是POD型别 执行的流程就会跳转到以下函数这个是通过function template的参数推导机制得到的
templateclass ForwardIterator,class Size,class T
inline ForwardIterator __uninitizlized_fill_n_aux(ForwardIterator first,Size n,const Tx){return fill_n(first,n,x); //交给高阶函数执行
}struct __true_type{};
struct __false_type{};templateclass T
struct __type_traits {typedef __true_type this_dummy_member_must_be_first;typedef __false_type has_trivial_default_constructor;typedef __false_type has_trivial_copy_constructor;typedef __false_type has_trivial_assignment_constructor;typedef __false_type has_trivial_destructor;typedef __false_type is_POD_type;
};//函数的逻辑是
//首先萃取出 迭代器first的value type然后判断这个型别是否是POD类型
templateclass ForwardIterator,class Size,class T,class T1
inline ForwardIterator __uninitizlized_fill_n(ForwardIterator first,Size n,const Tx,T1*){//以下使用的是__type_traitsT1::is_POD_type is _PODtypedef typename __type_traitsT1::is_POD_type is_POD;return __uninitizlized_fill_n_aux(first,n,x,is_POD());
}templateclass ForwardIterator,class Size,class T
ForwardIterator uninitialized_fill_n(ForwardIterator first,Size n,const Tx){return __uninitizlized_fill_n(first,n,x,value_type(first));//使用value_type()判断first的value type
}//alloc 是SGI STL默认的空间配置器
template class T,class Alloc
class vector{
public://vector的嵌套型别定义typedef T value_type;typedef value_type * pointer;typedef value_type * iterator;typedef value_type reference;typedef std::size_t size_type;typedef ptrdiff_t difference_type;
protected://simple_alloc 是SGI STL的空间配置器typedef simple_allocvalue_type,Allocdata_allocator;iterator start; //表示目前使用空间的头部iterator finish; //表示目前使用空间的尾部iterator end_of_storage; //表示目前可用空间的尾部void insert_aux(iterator position,const Tx);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 startn;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(){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(){Chy::allocatorT::destroy(start,finish); //全局函数deallocate(); //vector的成员函数}reference front(){return *begin();} //第一个元素reference back(){return *(end()-1);} //最后一个元素void push_back(const T x){if (finish ! end_of_storage){Chy::allocatorT::construct(finish,x);finish;} else{insert_aux(end(),x);// vector的成员函数}}void pop_back(){ //将最尾端的元素取出--finish;Chy::allocatorT::destroy(finish);}iterator erase(iterator position){ //清除某个位置上的元素if (position1 ! end()){std::copy(position1,finish,position); //后续元素向前移动 进行元素的覆盖}--finish;Chy::allocatorT::destroy(finish);return position;}void resize(size_type new_size,const T x){if (new_size size()){erase(begin()new_size,end());} else{std::inserter(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 Tx){iterator result data_allocator ::allocate(n);uninitialized_fill_n(result,n,x); //全局函数return result;}
};
vector迭代器
vector维护的是一个连续的线性空间所以不论其元素的的型别是怎样普通的指针都可以作为vector的迭代器从而满足所有的必要的条件因为vector迭代器所需要的操作比如 operator* operator- operator operator-- operator operator- operator operator- 是普通指针天生就具备的能力普通指针支持随机存取正因为普通指针具备这样的能力所以vector提供的是random Access iteratorsvector的迭代器是普通的指针例子
std::vectorint::iterator i_vite; //i_vite的型别本质上是int*
std::vectorShape::iterator s_vite; //s_vite的型别本质上是Shape*
Vector数据结构
数据结构很简单线性连续空间使用start和finish指向配置的连续空间中的已经使用的范围区间使用迭代器end_of_storage指向的是整个一块连续的空间(包含备用空间)的尾端iterator start; //表示目前使用空间的头部iterator finish; //表示目前使用空间的尾部iterator end_of_storage; //表示目前可用空间的尾部
vector分配的内存空间实际上是大于客户端申请的内存空间主要是为了防止以后内存的扩充这个便是容量的概念。即容量的概念 永远大于或者等于其大小一旦容量等于大小即是满载。使用三个迭代器完成 vector的首尾标定、使用空间的大小、容量、空容器的判断、注标[]的运算子、最前端的元素 和最末尾的元素等等Vector的构造和内存管理
//vector缺省使用alloc作为空间配置器并据此另外定义了data_allocator为的是更方便的以元素大小作为配置单位 typedef simple_allocvalue_type,Allocdata_allocator; 所以data_allocator::allocate(n) 表示配置n个元素的空间vector提供了很多的构造器uninitialized_fill_n 根据第一个参数的特性(使用type_traits 进行类型推导)决定使用fill_n() 还是通过反复调用 construct() 来完成任务使用push_back()将元素插入到vector的尾端的时候函数检查是否存在备用的空间如果有直接在备用空间进行元素的构造并且调整迭代器finish使得vector变大如果没有备用空间就需要进行元素的扩充(配置 、移动数据、释放空间)void push_back(const T x){if (finish ! end_of_storage){ //还存在备用空间Chy::allocatorT::construct(finish,x); //直接进行元素的构造finish; //调整水位高度} else{ //无备用空间insert_aux(end(),x);// vector的成员函数}}
//insert_aux 伪代码
templateclass T,class Alloc
void vectorT,Alloc::insert_aux(iterator position, const T x) {if (finish ! end_of_storage){ //还有备用空间//在备用空间起始处构造一个元素并使用vector最后一个元素数值为其初始化Chy::allocatorT::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 unintialized_copy(start,position,new_start);//为新的元素设定初始数值 xChy::allocatorT::construct(new_finish,x);//调整水位new_finish;//将原vector的备用空间中的内容也忠实拷贝过来new_finish unintialized_copy(position,finish,new_finish);}catch (){//commit or rollbackChy::allocatorT::destroy(new_start,new_finish);data_allocator::allocate(new_start,len);throw ;}//析构并且释放原有的vectorChy::allocatorT::destroy(begin(),end());deallocate();//调整迭代器 指向新的vectorstart new_start;finish new_finish;end_of_storage new_start len;}
}动态增加大小 不是在现有的内存空间后面接入新的空间 ( 无法保证原有空间之后是否还尚有可以配置的空间 )需要在背的地方申请空间因此一旦造成空间的重新配置指向原有vector的所有迭代器就会失效了void pop_back(){ //将最尾端的元素取出--finish; //将尾端标记往前移动一格表示放弃尾端元素Chy::allocatorT::destroy(finish);} void pop_back(){ //将最尾端的元素取出--finish; //将尾端标记往前移动一格表示放弃尾端元素Chy::allocatorT::destroy(finish);}//清除[first ,last内部所有元素iterator erase(iterator first,iterator last){iterator i copy(last,finish,first);Chy::allocatorT::destroy(i,finish);finish finish - (last - first);return first;}//清除某个特定位置上的元素iterator erase(iterator position){ //清除某个位置上的元素if (position1 ! end()){std::copy(position1,finish,position); //后续元素向前移动 进行元素的覆盖}--finish;Chy::allocatorT::destroy(finish);return position;}void clear(){erase(begin(),end());}这一块还不是很清晰 需要进一步完善 insert(position,n,x)
