开发成长之路（7）-- C++从入门到开发（C++知名库：STL入门·容器（二））

template <class T,class Alloc = alloc,size_t BufSiz = 0>
class deque{
public:
	typedef T value_type;
	typedef value_type* pointer;
	···
protected:
	//元素的指针的指针
	typedef pointer* map_pointer;

protected:
	map_pointer map;	
	//指向map，map是块连续空间，其内的每个元素都是一个指针，指向一块缓冲区
	
	size_type map_size;
	//map内可容纳多少指针
}

//该函数接受两个迭代器，用来表现一个heap底部容器的头尾，并且新元素已经插入到底部容器的最尾端。

template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__push_heap_aux(first,last,distance_type(first),value_type(first));/*这俩type在上一篇提到了，不知道也就算了吧，毕竟上一篇也不短*/
}

template <class RandomAccessIterator,class Distance,class T>
inline void __push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
	__push_heap(first,Distance((last-first)-1),Distance(0),T(*(last - 1)));	//(last-first)-1，容器最尾端
}

template <class RandomAccessIterator,class Distance,class T>
void __push_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;	//令洞值为新值，完成插入操作
}

template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__pop_heap_aux(first,last,value_type(first));
}

template <class RandomAccessIterator,class T>
inline void __pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
	__pop_heap(first,last-1,last-1,T(*(last - 1)),diatance_type(first));
}

template <class RandomAccessIterator,class Distance,class T>
void __push_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,T value,Distance*)
{
	*result = *first;	//设定尾值为首值，客端稍后可以pop_back()将值取出
	__adjust_heap(first,Distance(0),Distance(last - first),value);
}

template <class RandomAccessIterator,class Distance,class T>
void __adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value)
{
	Distance topIndex = holeIndex;
	Distance secondChild = 2 * 	holeIndex+2;	//右节点
	while(secondChild < len)
	{
		if(*(first + secondChild) < *(first +(secondChild -1)))
			secondChild --;
		*(first + holeIndex) = *(first + secondChild);
		holeIndex = secondChild;

		secondChild = 2*(secondChild+1);	//找出新洞节点的有子节点
	}
	if(secondChild == len)	//没有右子节点了
	{
		*(first + holeIndex) = *(first + secondChild -1);	//令左子值为键值
		holeIndex = secondChild - 1;	//再把洞的位置下移
	}
	__push_heap(first,holeIndex,topIndex,value);
}

template<class RandomAccessIterator>
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first,RandomAccessIterator last)
{
	__make_heap(first,last,distance_type(first),value_type(first));
}

//不允许指定比较方法
template <class RandomAccessIterator,class Distance,class T>
void __make_heap(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{
	if(last - first <2)	return;
	Distance len = last - first;
	Distance parent = (len - 1)/2;	//找出临时父节点
	while(true)	//尚未到达顶端，且父节点小于新值，这个循环将父值不断下调
	{
		__adjust_heap(first,parent,len,T(*(first+parent)));
		if(parent == 0)	return;	
		parent--;
	}
}