CONTENTS
备注:
本读书笔记基于侯捷先生的《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_TEMPLATES template <class T, class Sequence = deque<T> >//默认使用deque来实现。 #else template <class T, class Sequence> #endif class queue { friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y); friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y); 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_reference; protected: Sequence c;//内部真正存储数据的容器。 public: //对内部容器的方法的二次封装,以实现queue的先进先出功能。 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) { 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:
#ifndef __STL_LIMITED_DEFAULT_TEMPLATES //优先级队列,默认采用vector作为内部存储容器,采用默认比较大小函数作为优先级判断条件 template <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> > #else template <class T, class Sequence, class Compare> #endif class priority_queue { 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_reference; protected: Sequence c;//内部的存储容器。 Compare comp;//比较函数。 public: priority_queue() : c() {} explicit priority_queue(const Compare& x) : c(), comp(x) {} #ifdef __STL_MEMBER_TEMPLATES template <class InputIterator> priority_queue(InputIterator first, InputIterator last, const Compare& x) : c(first, last), comp(x) //首先调用构造函数将vector(c)构造出来。 {//然后调用make_heap方法,让vector成为一棵完全二叉树 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); } #else /* __STL_MEMBER_TEMPLATES */ priority_queue(const value_type* first, const value_type* last, const Compare& x) : c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); } priority_queue(const value_type* first, const value_type* last) : c(first, last) { make_heap(c.begin(), c.end(), comp); } #endif /* __STL_MEMBER_TEMPLATES */ 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 { //当加入时,现在容器中最后加入一个元素,然后调用push_heap将最后一个元素加入二叉树。 c.push_back(x); push_heap(c.begin(), c.end(), comp); } __STL_UNWIND(c.clear()); } void pop() { __STL_TRY { //当弹出时,先调用pop_heap将最大的元素放到容器的尾部,然后调用容器的pop_back方法弹出来。 pop_heap(c.begin(), c.end(), comp); c.pop_back(); } __STL_UNWIND(c.clear()); } };
发表评论