4.7 heap（隐式表述：implicit representation）

4.7.1 heap概述

binary max heap作为priority queue的底层机制，原因是：

1. binary heap：完全二叉树的结构可以保证整棵树没有节点漏洞，用array来表示这棵树的时候，只需要从array[1]开始保存（#0元素设为无限大或无限小），那么位于array第i个的节点，其左子节点就是第2*i个，右子节点是第2*i+1个，父节点是第i/2（向下取整）个。——这种以array表述tree的方式，称为隐式表述（implicit representation）。——由于array普通数组无法满足heap动态改变大小的要求，所以不用array而用vector。【由此可见heap的所有元素都必须遵循特别的排列规则（完全二叉树），所以heap不提供遍历功能及迭代器。】
2. max-heap：STL供应的是max-heap，最大值在根节点。

4.7.2 heap算法

1. push_heap：将新元素插入在底层vector的end()处，再使用percolate up（上溯）使之满足max-heap的要求；
2. pop_heap：取走根节点（即将其设至vector的尾端节点），再使用percolate down（下溯）使之满足max-heap的要求；
3. sort_heap：假如有n个元素，那么使用n-1次pop_heap()，每次都能将根节点（最大值）放置于容器最尾端，并每次都要将操作范围从后向前缩减一个元素，最终可以得到一个升序的vector，但此时的heap已经不是一个合法的heap了。
4. make_heap：将一段现有的数据转化为一个heap，依据4.7.1所讲的隐式表述。

4.8 priority_queue

4.8.1 priority_queue概述

priority_queue是一个拥有权值观念的queue（FIFO），其内的元素不按照被推入的次序排列，而是自动依照元素的权值排列（权值高的排在前面）。

priority_queue也是container adapter（参考4.5.2小节）。

4.9 slist

4.9.1 slist概述

list是双向链表，而slist则是单向链表，slist的迭代器是Forward Iterator。

• STL的习惯是，插入操作会将新元素插入于指定位置之前，slist作为单向链表，没有方便的方法可以定出前一个位置，必须从头找起，所以slist提供了insert_after()和erase_after()来运用；
• 同样地，slist不提供push_back()，只提供push_front()，所以slist的元素次序会和元素插入进来的次序相反。

4.9.2-4.9.3 slist的节点及迭代器

slist的节点和迭代器的设计，都运用了继承关系。

节点：

//单向链表的节点基本结构struct __slist_node_base{    __slist_node_base* next;}//单向链表的节点结构template <class T>struct __slist_node : public __slist_node_base{    T data;}//全局函数：已知某一节点，插入新节点于其后inline __slist_node_base* __slist_make_link(        __slist_node_base* prev_node,        __slist_node_base* new_node ){    //令new节点的下一节点为prev节点的下一节点    new_node->next=prev_node->next;    prev_node->next=new_node;  //令prev节点的下一节点指向new节点    return new_node;}//全局函数：单向链表的大小inline size_t __slist_size( __slist_node_base* node){    size_t result=0;    for( ; node!=0; node=node->next)        ++result;    return result;}

 

迭代器：

//单向链表的迭代器基本结构struct __slist_iterator_base {    typedef size_t size_type;    typedef ptrdiff_t difference_type;    typedef forward_iterator_tag iterator_category;    __slist_node_base* node;  //指向节点基本结构                  //构造函数，初始化node为x    __slist_iterator_base(__slist_node_base* x) :node(x) { }    void incr() { node=node->next; }    bool operator==(const __slist_iterator_base& x) const{        return node==x.node;    }    bool operator!=(const __slist_iterator_base& x) const{        return node !=x,node;    }};//单向链表的迭代器结构template<class T,class Ref,class Ptr>struct __slist_iteartor : public __slist_iterator_base {    typedef __slist_iterator<T,T&,T*> iterator;    typedef __slist_iterator<T,const T&,const T*> const_iteartor;    typedef __slist_iterator<T,Ref,Ptr> self;    typedef T value_type;    typedef Ptr pointer;    typedef Ref reference;    typedef __slist_node<T> list_node;        //list_node*的类型是__slist_node*,__slist_node继承__slist_node_base    //用指针来初始化，指针类型有转换      __slist_iterator(list_node* x) : __slist_iterator_base(x) {}      // 默认构造函数       __slist_iterator() : __slist_iterator_base(0) {}        //复制构造函数        __slist_iterator(const iterator& x) : __slist_iterator_base(x.node) {}      reference operator*() const { return ((list_node*) node)->data; }    reference operator->() const { return &(operator*()); }    self& operator++(){        incr(); //前进一个节点        return *this;    }    self operator++(int){  //后置式        self tmp=*this;        incr();        return tmp;    }//没有operator--，因为slist的迭代器是Forward Iterator};

 

4.9.4 slist的数据结构

template <class T, class Alloc=alloc>class slist{public:    typedef T value_type;    typedef value_type* pointer;    typedef const value_type* const_pointer;    typedef value_type& reference;    typedef const value_type& const_reference;    typedef size_t size_type;    typedef ptrdiff_t difference_type;    typedef __slist_iterator<T,T&,T*> iterator;    typedef __slist_iterator<T,const T&,const T*> const_iterator;private:    typedef __slist_node<T> list_node;    typedef __slist_node_base list_node_base;    typedef __slist_iterator_base iteartor_base;    typedef simple_allc<list_node, Alloc> list_node_allocator;    static list_node* create_node(const value_type& x){        list_node* node=list_node_allocator::allocate();  //配置空间        __STL_TRY{            construct(&node->data, x);  //构造元素            node->next=0;        }        __STL_UNWIND(list_node_allocator::deallocate(node) );        return node;    }        static void destroy_node(list_node* node){        destroy(&node->data);  //将元素析构        list_node_allocator::deallocate(node);  //释放空间    }private:    list_node_base head;  //头部，不是指针public:    slist() { head.next=0; }    ~slist() { clear(); }public:    iterator begin() { return iterator((list_node*)head.next); }    iterator end() { return iterator(0); }    size_type size() const { return _slist_size(head.next); }    bool empty() const { return head.next == 0; }    //两个slist交换，只要将head交换互指即可    void swap(slist& L){        list_node_base* tmp=head.next;        head.next=L.head.next;        L.head.next=tmp;    }public:    //取头部元素    reference front() { return ((list_node*)head.next)->data; }        //从头部插入元素（新元素成为slist的第一个元素）    void push_front(const value_type& x){        __slist_make_link(&head, create_node(x));    }    //从头部取走元素（删除之），修改head    void pop_front(){        list_node* node=(list_node*)head.next;        head.next=node->next;        destroy_node)node);    }    ...};

Ch4 序列式容器（下）