[历史归档]本文原发布于 cstriker1407.info 个人博客内容为历史存档仅供参考。发布时间2014-07-15 标题C STL读书笔记stl_queue.h分类编程 / C C / C STL 标签CC·stl·heap·queueC STL读书笔记stl_queue.h备注stl\_queue.h:queue:priority\_queue备注本读书笔记基于侯捷先生的《STL源码剖析》截图和注释版权均属于原作者所有。本读书笔记中的源码部分直接拷贝自SGI-STL部分代码删除了头部的版权注释但代码版权属于原作者。小弟初看stl很多代码都不是太懂注释可能有很多错误还请路过的各位大牛多多给予指导。为了降低学习难度作者这里换到了SGI-STL-2.91.57的源码来学习代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】队列queue是一种特殊的线性表它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作。最先插入在元素将是最先被删除反之最后插入的元素将最后被删除因此队列又称为“先进先出”FIFO—first in first out的线性表。由于STL中已经实现了很多比较通用的数据结构因此queue可以直接在这些数据结构上套个壳。这里笔记下源码比较简单stl_queue.h:queue:#ifndef__STL_LIMITED_DEFAULT_TEMPLATEStemplateclassT,classSequencedequeT//默认使用deque来实现。#elsetemplateclassT,classSequence#endifclassqueue{friendbooloperator__STL_NULL_TMPL_ARGS(constqueuex,constqueuey);friendbooloperator__STL_NULL_TMPL_ARGS(constqueuex,constqueuey);public:typedeftypenameSequence::value_type value_type;typedeftypenameSequence::size_type size_type;typedeftypenameSequence::reference reference;typedeftypenameSequence::const_reference const_reference;protected:Sequence c;//内部真正存储数据的容器。public://对内部容器的方法的二次封装以实现queue的先进先出功能。boolempty()const{returnc.empty();}size_typesize()const{returnc.size();}referencefront(){returnc.front();}const_referencefront()const{returnc.front();}referenceback(){returnc.back();}const_referenceback()const{returnc.back();}voidpush(constvalue_typex){c.push_back(x);}voidpop(){c.pop_front();}};templateclassT,classSequencebooloperator(constqueueT,Sequencex,constqueueT,Sequencey){returnx.cy.c;}templateclassT,classSequencebooloperator(constqueueT,Sequencex,constqueueT,Sequencey){returnx.cy.c;}priority_queue#ifndef__STL_LIMITED_DEFAULT_TEMPLATES//优先级队列默认采用vector作为内部存储容器采用默认比较大小函数作为优先级判断条件templateclassT,classSequencevectorT,classComparelesstypenameSequence::value_type#elsetemplateclassT,classSequence,classCompare#endifclasspriority_queue{public:typedeftypenameSequence::value_type value_type;typedeftypenameSequence::size_type size_type;typedeftypenameSequence::reference reference;typedeftypenameSequence::const_reference const_reference;protected:Sequence c;//内部的存储容器。Compare comp;//比较函数。public:priority_queue():c(){}explicitpriority_queue(constComparex):c(),comp(x){}#ifdef__STL_MEMBER_TEMPLATEStemplateclassInputIteratorpriority_queue(InputIterator first,InputIterator last,constComparex):c(first,last),comp(x)//首先调用构造函数将vectorc构造出来。{//然后调用make_heap方法让vector成为一棵完全二叉树make_heap(c.begin(),c.end(),comp);}templateclassInputIteratorpriority_queue(InputIterator first,InputIterator last):c(first,last){make_heap(c.begin(),c.end(),comp);}#else/* __STL_MEMBER_TEMPLATES */priority_queue(constvalue_type*first,constvalue_type*last,constComparex):c(first,last),comp(x){make_heap(c.begin(),c.end(),comp);}priority_queue(constvalue_type*first,constvalue_type*last):c(first,last){make_heap(c.begin(),c.end(),comp);}#endif/* __STL_MEMBER_TEMPLATES */boolempty()const{returnc.empty();}size_typesize()const{returnc.size();}const_referencetop()const{returnc.front();}voidpush(constvalue_typex){__STL_TRY{//当加入时现在容器中最后加入一个元素然后调用push_heap将最后一个元素加入二叉树。c.push_back(x);push_heap(c.begin(),c.end(),comp);}__STL_UNWIND(c.clear());}voidpop(){__STL_TRY{//当弹出时先调用pop_heap将最大的元素放到容器的尾部然后调用容器的pop_back方法弹出来。pop_heap(c.begin(),c.end(),comp);c.pop_back();}__STL_UNWIND(c.clear());}};