4.顺序容器

1.vector

• 比较简单，连续的空间，不够就申请size()+max(size(), 新增的n)的内存,释放原先的内存，(所谓的vector原有迭代器可能会失效的问题)，略
• 可以直接使用指针作为迭代器
• 基本的iterator_type如下

template 
    
     class vector{	public:		typedef T value_type;		typedef value_type* pointer;		typedef value_type* iterator;  //主要是内部调用，对于iterator_traits,已经对指针做了特化		typedef value_type& reference;		typedef size_t size_type;		typedef ptrdiff_t difference_type;};复制代码
    

2. list

list实际是一个双向链表

// list_node 的实现template 
    
     struct __list_node {
        typedef void* void_pointer; //写成__list_node
     
      * 更为准确    void_pointer prev;    void_pointer next;    T data;};复制代码
     
    

• list不能像vector以普通指针作为迭代器，因为不保证在存储空间连续，需要自己实现迭代器

template
    
     struct __list_iterator {
    	public:		typedef __list_iterator
     
       iterator;  //不清楚Ref和Ptr的使用情景		typedef __list_iterator
      
        self;		typedef bidirectional_iterator_tag iterator_category; //双向迭代器		typedef T value_type;		typedef Ptr pointer;		typedef Ref reference;		typedef __list_node
       
        * link_type;		typedef size_t size_type;		typedef ptrdiff_t difference_type;		link_type node;		__list_iterator(link_type x) :node(x) {}		__list_iterator() {}		__list_iterator(const iterator& x): node(x.node) {}		bool operator == (const self& x) const {
   return node == x.node;}		bool operator != (const self& x) const {
   return node != x.node;}		reference operator*() const {
   return (*node).data;}		pointer operator->() const {
   return &(operator*());}		self& operator++() {			node = (link_type) ((*node).next);			return *this;		}		self operator++(int) {			self tmp = *this;			++*this;			return tmp;		}				self& operator--() {			node = (link_type) ((*node).prev);			return *this;		}		self operator--(int) {			self tmp = *this;			++*this;			return tmp;		}};复制代码
       
      
     
    

• 而对于list的实现，实际只需要存储一个__list_node的指针即list::node，指向为end()返回的迭代器对应的node
• 空列表的node->next==node->prev==node
• 大部分方法是基于一些基本方法的封装，如erase, insert,简单的修改node的prev和next来实现,
• 还有个比较常用的是transfer,splice等是基于transfer
• list的sort需要单独实现因为STL sort算法只接受RamdonAccessIterator

template
    
     class list{
    	protected:		typedef __list_node
     
       list_node;		typedef simple_alloc
      
        list_node_allocator;	public:		typedef list_node* link_type;		typedef __list_iterator
       
         iterator;	protected:		link_type node; //为尾端节点，next指向第一个		link_type get_node() {
   return list_node_allocator::allocate();}		void empty_initialize() {			node = get_node();			node->next = node;			node->prev = node;		}	public:		iterator begin() {
   return (link_type)(node->next);}  //因为__list_iterator有对应的非explict 构造函数		iterator end() {
   return node;}	protected:		// 移动迭代范围内的元素到position之前		void transfer (iterator position, iterator first, iterator last) {			if (position != last) {				link_type tmp = position.node->prev;				last.node->prev->next = position.node;				first.node->prev->next = last.node;				position.node->prev->next = first.node;				position.node->prev = last.node->prev;				last.node->prev = first.node->prev;				first.node->prev = tmp;			}		}};复制代码
       
      
     
    

3.deque

• deque和vector类似，只是双向开口，和支持O(1)的时间对头部进行插入移除
• deque动态的以分段连续空间组成，不存在vector上的复制元素到新空间再删除旧空间的操作
• deque需要自己实现迭代器，因为实际非连续空间，其效率较vector较低，建议尽量用vector，一些类似排序的操作可以将deque复制到vector等操作完成后再复制回来

3.1 deque的中控器

• deque最核心的部分是在分段的定量连续空间，维护其整体连续的假象，这部分通过map实现
• map是一块连续空间，每个元素指向另一段较大的连续空间即buffer，被指向的连续空间是deque的存储主体
• map满载会类似vector重新找一块空间
  deque迭代器的实现,重点是是operate+-相关方法的重载，buffer_size是缓冲区的大小

#ifndef STL_DEQUE#define STL_DEQUE#include "../allocator/stl_alloc.h"#include "../allocator/stl_construct.h"inline size_t __deque_buf_size(size_t n, size_t sz){	return n !=0 ? n:(sz < 512 ? size_t(512/sz): size_t(1));}template
    
     struct __deque_iterator{
    	typedef __deque_iterator
     
       iterator;	typedef __deque_iterator
      
        const_iterator;	static size_t buffer_size() {
   return __deque_buf_size(BufSiz, sizeof(T));}	typedef random_access_iterator_tag iterator_category;	typedef T value_type;	typedef Ptr pointer;	typedef Ref reference;	typedef size_t size_type;	typedef ptrdiff_t difference_type;	typedef T** map_pointer;	typedef __deque_iterator self;	T* cur;	T* first;	T* last;	map_pointer node;	void set_node(map_pointer new_node) {		node = new_node;		first = *new_node;		last = first + difference_type(buffer_size());	}	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;	}	self& operator--(){		if (cur==first){			set_node(node-1);			cur=last;		}		--cur;		return *this;	}	self operator--(int){		self tmp=*this;		--this;		return tmp;	}//略};#endif复制代码
      
     
    

关于deque的实现，重点在与内存的分配，即map的增减。

• 当push_front或者push_end时map有空余node时，正常操作
• 否则当map_size 大于2倍的需要的nodes数时，简单的移动map内的数据。
• 否则重新分配map。
• deque还提供了insert方法，实现的原理是比较position前后数数据那边少，如果前面少，就push_front第一个元素，然后移动前面的数据。

template
    
     class deque{
    	public:		typedef T value_type;		typedef value_type* pointer;		typedef size_t size_type;		typedef __deque_iterator
     
       iterator;	protected:		typedef pointer* map_pointer;			protected:		iterator start;		iterator finish;		map_pointer map;		size_type map_size;	protected:		typedef simple_alloc
      
        data_allocator;		typedef simple_alloc
       
         map_allocator;	public:		size_type buffer_size() {
   return __deque_buf_size(BufSiz, sizeof(value_type));}		deque(int n, const value_type& value): start(), finish(), map(0), map_size(0) {fill_initialize(n, value);}		void fill_initialize(size_type n, const value_type& value){			create_map_and_nodes(n);			map_pointer cur;			for (cur=start.node; cur
        
         map_size - (finish.node-map)) reallocate_map(nodes_to_add, false); //尾端节点不够，调整map		}		void reallocate_map(size_type nodes_to_add, bool add_at_front){			size_type old_num_nodes = finish.node-start.node+1;			size_type new_num_nodes = old_num_nodes + nodes_to_add;			map_pointer new_nstart;			if (map_size > 2*new_num_nodes) {				new_nstart=map+(map_size-new_num_nodes) / 2+(add_at_front?nodes_to_add:0);				if (new_nstart < start.node){					copy(start.node, finish.node+1, new_nstart);				} else {					copy_backward(start.node, finish.node+1, new_nstart+old_num_nodes);				}			} else {				size_type new_map_size=map_size+max(map_size, nodes_to_add) + 2;				map_pointer new_map = map_allocator::allcocate(new_map_size);				new_nstart = new_map + (new_map_size-new_num_nodes) /2 + (add_at_front?nodes_to_add:0);				copy(start.node, finish.node+1, new_nstart);				map_allocator::deallocate(map, map_size);				map = new_map;				map_size = new_map_size;			}			start.set_node(new_nstart);			finish.set_node(new_nstart+old_num_nodes-1);		}};复制代码
        
       
      
     
    

4. stack和queue

• 从实现上的方式上看实际都是adapter（配接器），如list和deque已经提供了满足操作的数据结构
• STL默认将deque作为stack和queue的底层容器
• stack和queue没有迭代器

template
    
     >class stack{
    	public:		typedef typename Sequence::value_type value_type;		typedef typename Sequence::size_type size_type;		typedef typename Sequence::reference reference;		typedef typename Sequence::const_reference const_referenc;	protected:		Sequence c;	public:		bool empty() const {
   return c.empty();}};复制代码
    

5 heap和priority_queue

• priority_queue支持以任意顺序将元素推入容器，但是取出是按照优先级取出来
• heap是priority_queue配接器一个底层的容器，是一个max_heap完全二叉树
• vector是heap的默认底层容器
• 可以用array存储树的节点，array[0]位置保留,则，a[i]的左子节点为a[2i],右子节点为a[2i+1]

//first和last必须为vector的头尾, index0没有空着template
    
     inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last){
    	__pop_heap_aux(first, last, value_type(first));}template
     
      inline void __pop_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*){
    	__pop_heap(first, Distance(last-first-1), Distance(0), T(*(last-1)));}template
      
       inline void __pop_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value){
    	Distance parent = (holeIndex -1) / 2;	while(holeIndex>topIndex && *(first+parent) < value){		*(first+holeIndex) = *(first+parent);		holeIndex = parent;		parent = (holeIndex-1)/2;	}	*(first+holeIndex)=value;}#endif// pop类似，是将最后一个元素放到第一个，然后，由根开始替换，但是会把首元素不去除而是放到vector结尾// sort方法会调用pop,每次last减1复制代码