──────────────────────────────────── ┌————————————┐
│▉▉♥♥♥♥♥♥♥♥ 99

这里写目录标题

• List
• Vector
• Array
• Deque
• Deque
• Stack

malloc分配的内存远比请求的内存要大的多，需要的越大额外的开销(overhead)占比也就越小。
G2.9所属的标准准，容器没必要记录每一个元素的大小，因为大小都是一样的，想办法不要cookie。1个元素省去8字节，100万个元素就是800万个自己，想想就开心。
链表迭代器

List

//G2.9template<typename T>struct __list_node{typedef void * void_pointer;void_pointer prev;void_pointer next;T data;};template<typename T,class Ref,class Ptr>struct __list_iterator{typedef __list_iterator<T,Ref,Ptr> self;typedef biderctional_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __list_node<T>* list_type;typedef ptridff_t difference_type;link_type node;reference operator*() const {return (*node).data;}pointer operator() const {return &(operator *());}self &operator++(){node = (link_tupe)((*node).next);return *this;}self operator++(int){self tmp=*this;++*this;return tmp;}};templata<typename T,typename Alloc=alloc>class list{protected:typedef __list_node<T> list_node;public:typedef _list_node* link_type;typedef __list_iterator<T,T&,T*> iterator;protected:link_type node;};//G4.9template<typename _Tp>struct _List_iterator{typedef _Tp* pointer;typedef _Tp& reference;...};struct _List_node_base{_List_node_base* _M_next;_List_node_base * _M_prex;};template<typename _Tp>struct _List_node:public _List_node_base{_Tp _M_data;}; 

操作步骤:

• 记录原值
• 进行操作
• 返回原值

iint i(3);++++i;->++(++i);i++++;->(i++)++;//错，c++不允许前++两次

所有的容器的迭代器都有两大部分，一部分是一大堆的typedef，有五个是一定要的；另一部分是operator运算符重载。
为了实现前闭后开区间，所以最后一个节点刻意制造出虚的。iterator是容器和算法之间的桥梁。

iterators必须有能力回答出algorithms的提问：

• iterator_category
• difference_type
• value_type
• reference
• pointer
  后面两种从来没有被使用，没有任何一种算法会去问那两个问题，这就叫做iterator associated type。
  萃取技术主要是为了区分退化的迭代器(指针)和泛化的指针(迭代器)，当算法问一些问题时，指针是无法回答问题的，只有class才能回答，所以要通过萃取技术这个中间层。

Vector

template<typename T,typename Alloc=alloc>class vector{public:typedef T value_type;typedef value_type* iterator;typedef value_type & reference;typedef size_t size_type;protected:iterator start;iterator finish;iterator end_of_storage;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);}} void push_back(const T&x){if(finish != end_of_storage){construct(finish,x);++finish;}elseinsert_aux(end(),x);}template<typename T,typename Alloc>void vector<T,Alloc>::insert_aux(iterator position,const T &x){if(finis !=end_of_storage){construct(finish,*(finish -1));++finishlT 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::alocate(len);iterator new_finised=new_start;try{new_finish=uninitialized_copy(start,position,new_start);construc(new_finish,x);new_finish=uninitialized_copy(position,finish,new_finish);}catch(...){desroy(new_start,new_finish);data_allocator::deallocate(new_start,len);}destroy(begin(),end());deallocate();start=new_start;finish_new_finish;end_of_storage=new_start+len;throw;}}

Array

template<typename _Tp,stdLLsize_t Nm>struct __arrary_traits{typedef _Tp Type[_Nm];static constexpt _Tp&;_S_ref(const _Type& __std::size_t __n)noexcept{return cpmst_cast<_Tp&>(_t[_n]);}};template<typename _Tp,std::size_t _Nm>struct array{typedef _Tp value_type;typedef value_type* pointer;typedef value_type& reference;typedef value_type* iterator;typedef std::size_t size_type;}

Deque

非常好用的容器，但是古典书籍却没有介绍这么好的东西。
deque的迭代器是一个class，所有的迭代器都有两个迭代器两个函数，就是指向头和尾。

template<typename T,typename Alloc=alloc,size_t BufSiz=0>class deque{public:typedef T value_type;typedef __deque_iterator<T,T*,BufSiz> iterator;protected:typedef pointer* map_pointer;//T **protected:iterator start;iterator finish;map_pointer map;size_type map_size;public:iterator begin(){return start;}iterator end(){return finish;}size_type size() const {return finish-start;};...};template<typename T,typename Ref,typename Ptr,size_t BufSiz>struct __deque_iterator{typedef reandom_access_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef size_t size_type;typedef ptrdiff_t dirrerence_type;typedef T** map_pointer;typedef __deque_iterator self;T* cur;T* first;T* last;map_pointer node;};inline size_t_deque_buf_size(size_t n,size_t sz){retunrn !=0?n:(sz<512? size_t(512/sz):size_t(1));}template<typename T,typename Ref,typename Ptr,size_t BufSiz>struct __deque_iterator{typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef T** map_pointerltypedef __deque_iterator self;};iterator insert(iterator position,const value_type & x){if(position.cur==start.cur)push_front(x);return start;}else if(position.cur==finish.cur){push_back(x);iterartor tmp=finish;--tmp;return tmp;}else{return insert_aux(position,x);}}template<typename T,typename Alloc,size_t BufSize>typename deque<T,Alloc,BufSize>::iterator deque<T,Alloc,BufSize>::insert_aux(iterator pos,const value_type &x){difference_type index=pos-start;value_type x_copy=x;if(index<size()/2){push_front(front());...copy(front2,pos,front1);}else{push_back(back());...copt_backward(pos,back2,back1);}*pos=x_copy;return pos;}}reference operator[](size_type n){return start[difference_type(n)];}refeeence front(){return *start;}reference back(){iterator tmp=finish;--tmp;return *tmp;}size)type size() const{return finish-start;}bool empty const{return finish==start;}reference operator* () const{return *cur;}pointer operator->() const{return &(operator*));}difference_type operator-(const self& x)const{return difference_type(buffer_size()*(node-x.node-1)+(cur-first)+(x.last-x.cur);}self& operator++(){+=cur;if(cur==last){set_node(node+1);cur=first;}return *this;}self operator++(int){self tmp=*this;++*this;return tmp;}void set_node(map_pointer new_node){node=new_node;first=*new_node;lase=first+difference_type(buffer_size());}self& operator+=(difference_type n){difference_type offset=n+(cur-first);if(offset >=0 && offset <difference_type(buffer_size()))cur +=n;else{difference_type node_offset=offset>0? offset /diffence_type(buffer_size()): -difference_type((-offset -1))/buffer_size())-1;set_node(node+node_offset);cir=first+(offset-node_offset * difference_type(buffer_size)));}return *this;}self operator+(difference_type n)const{self tmp=*this;return tmp +=n;}self& operator-=(difference_type n){return *this +=-n;}self operator-(difference_type n){self tmp=*this;return tmp -=n;}reference operator[](difference_type n) const{return *(*this+n);}

当你创建一个deque容器时，他本身创建40个字节，想想真的有点多诶。
如果超过512字节，那一个缓冲区就放一个；如果小于512,字节，会放512/4个数。
迭代器对减做了操作符重载，这边需要仔细思考一下。

Deque

template<typename T,typename Sequence =deque<T>>class queue{public:typedef typename Sequence::value_type value_type;typedef typename Sequence::value_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;protected:Sequence c;public:bool empty()const {return c.empty();};size_type size() const{return c.size()};reference front(){return c.front;}const_reference back(){return c.back();}void push(const value_type & x){c.push_back(x);}void pop(){c.pop_front();}};

Stack

template<typename T,typename Sequence=deque<T>>ckass stack{public:typedef typename Sequence::value value_type;typedef typename Sequence::size size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;protected:Sequence c;public:bool emptu() const {return c.empty();}size_type size()const {return c.size();}reference top(){return c.back();}const_reference top() const {return c.back();}void push(const value_type &x ){c.push_back(x);}void pop(){c.pop_back();}};

stack和queue都可以选择list或者deque做为底层结构，也根本不提供迭代器。
stack可以选择vector做底层结构，queue不可选择vector做底层结构，vector没有pop_front。
stack 和queue都不可选择set和map做底层结构。

钢筋混凝土切割网