C++(STL源码刨析/stack/queue/priority_queue)

一 stack

template <class T,class Sequence = deque<T>>
class stack
{// 判断 2 个 stack 是否相等/小于friend bool operator== __STL_NULL_TMPL_ARGS(const stack&,const stack&);friend bool operator< __STL_NULL_TMPL_ARGS(const stack&,const stack&);public:// stack 直接拿配接器内的类型用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_reference;protected:// 配接器Sequence c;public:// 判空/元素个数/栈顶元素/入栈/弹栈bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference top() { return c.back(); }void push(const value_type& x) { c.push_back(x); }void pop() { c.pop_back(); }
};template<class T,class Sequence>
bool operator==(const stack<T,Sequence>& x,const stack<T,Sequence>& y)
{// 配接器 == 配接器return x.c == y.c;
}template<class T,class Sequence>
bool operator<(const stack<T,Sequence>& x,const stack<T,Sequence>& y)
{// 配接器 < 配接器return x.c < y.c;
}

二 queue

template <class T,class Sequence = deque<T>>
class queue
{// 判断 2 个 stack 是否相等/小于friend bool operator== __STL_NULL_TMPL_ARGS(const queue&,const queue&);friend bool operator< __STL_NULL_TMPL_ARGS(const queue&,const queue&);public:// queue直接拿配接器内的类型用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_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 front() const { return c.front(); }reference back() { return c.back(); }const_reference back() const { return c.back(); }void push(const value_type& x) { return c.push_back(x); }void pop() { c.pop_front(); }
};template<class T,class Sequence>
bool operator==(const queue<T,Sequence>& x,const queue<T,Sequence>& y)
{// 配接器 == 配接器return x.c == y.c;
}template<class T,class Sequence>
bool operator<(const queue<T,Sequence>& x,const queue<T,Sequence>& y)
{// 配接器 < 配接器return x.c < y.c;
}

三 priority_queue

template <RandomAccessIterator>
//  堆插入
inline void push_heap(RandomAccessIterator first,RandomAccessIterator last)
{// 调用该接口时,已经有新元素插入到了末尾//             迭代器首/尾  元素距离类型          元素类型__push_heap_aux(first,last,distance_type(first),value_type(first));
}template <RandomAccessIterator,class Distance,class T>
inline void __push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*)
{//    迭代器首     指向最后一个元素的下标         下标 0       最后一个元素__push_heap(first,Distance((last - first) - 1),Distance(0),T(*(last - 1)));
}template <RandomAccessIterator,class Distance,class T>
void __push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value)
{// 根据孩子节点求父节点 (index - 1) / 2Distance parent = (holeIndex - 1) / 2;// 如果孩子节点下标至少大于 0 ,并且父节点小于新插入尾部的元素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,T*)
{__pop_heap_aux(first,last,value_type(first));
}template <class RandomAccessIterator,class T>
inline void __pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,T*)
{__pop_heap(first,last - 1,last - 1,T(*(last - 1),distance_type(first));
}template <class RandomAccessIterator,class T,class Distance>
inline void __pop_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result,T value,Distance*)
{// 尾部 = 头部元素*result = *first;__adjust_heap(first,Distance(0),Distance(last - first),value);
}template <class RandomAccessIterator,class Distance,class T>
void __adjust_heap(RandomAccessIterator first,RandomAccessIterator holeIndex,Distance len,T value)
{// 原数组尾元素不计入// 0Distance top_Index = holeIndex;// 右孩子节点    DIstance secondChild = 2 * holeIndex + 2;// 孩子节点 < 最大长度while(secondChile < 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 T,class Sequence = vector<T>,class Compare = less<typename Sequence::value_type>>
class priority_queue
{public:// priority_queue直接拿配接器内的类型用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_reference;// 配置器/比较方法protected:Sequence c;Compare comp;// 无参构造/自定义比较函数构造public:priority_queue() :c() {}explicit priority_queue(const Compare& x) :c(),comp(x) {}// 迭代器区间制造和自定义比较方法template <class InputIterator>priority_queue(InputIterator first,InputIterator last,const Compare& x):c(first,last),comp(x){ make_heap(c.begin(),c.end(),comp); }// 迭代器区间构造template <class InputIterator>priority_queue(InputIterator first,InputIterator last):c(first,last){ make_heap(c.begin(),c.end(),comp); }// 判空/元素总个数/堆顶元素/插入/删除bool empty() const { return c.empty(); }size_type size() const { return c.size(); }const_reference top() const { return c.front(); }void push(const value_type& x){// 看上面__STL_TRY{c.push_back(x);push_heap(c.begin(),c.end(),comp);}// 异常处理__STL_UNWIND(c.clear();)}void pop(){// 看上面__STL_TRY{pop_heap(c.begin(),c.end(),comp);}// 异常处理__STL_UNWIND(c.clear());}
};