C++ STL 序列式容器(二)

系列文章目录

C++ STL 序列式容器(一 vector, list)

---

---

deque

deque概述

vector是单向开口的连续线性空间，deque是一种双向开口的连续线性空间。和vector一样支持随机访问。

成员函数接口

//将pos位置于元素清除，后续元素向前移动，返回pos位置的元素指针
iterator erase(iterator pos);
//清除[first, last)位置的元素，返回first位置元素的指针
iterator erase(iterator first, iterator last);
//在元素*pos位置前方插入，返回pos位置的元素，即返回插入元素的迭代器
iterator insert(iterator position, const value_type& x);

deque的结构

deque的内部维护一个map，它本质是一个二级指针，解引用后得到一级指针，每个一级指针指向一块缓冲区（如图中所示），缓冲区用于存储deque的元素。

此外deque内部还维护两个迭代器start和finish，start迭代器用于维护第一缓冲区，finish用于维护最后缓冲区。

deque的迭代器内有四个数据成员：cur，first，last，node
first指向缓冲区的头部，last指向缓冲区的尾后，它们都是一级指针，通过[first, last)可确定一个缓冲区；
node指向map所指空间，所以node也是二级指针，对他解引用后得到指向缓冲区的指针；
cur：(1)从迭代器的角度看，cur严格指向缓冲区的内部(cur != last)，可以指示当前迭代器对象的状态，对迭代器解引用就是对cur解引用. (2)从deque的角度看，start.cur指向容器的首元素，finish.cur指向容器的尾后元素

iterator

// 全局函数
inline size_t __deque_buf_size(size_t n, size_t sz)
{
    return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}
// iterator
template<class T, class Ref, class Ptr, size_t BufSiz>  
struct __deque_iterator // 未继承std::iterator
{
    typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;
    typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
    // 指示一个缓冲区可以容纳多少个元素
    static size_t buffer_size()
    {
        return __deque_buf_size(BufSize, sizeof(T));
    }
    // 未继承std::iterator，所以必须自行撰写五个必要的迭代器相应型别
    typedef random_access_iterator_tag  iterator_category;
    typedef T                           value_type;
    typedef Ptr                         pointer;
    typedef Ref                         reference;
    typedef size_t                      size_type;
    typedef ptrdiff_t                   difference_type;
    typedef T**                         map_pointer; 

    typedef __deque_iterator            self;

    // 保持与容器的联结
    T* cur;            // 此迭代器所指之 缓冲区中 的现行current元素
                       // cur必须在缓冲区的内部
    T* first;          // 此迭代器所指之缓冲区的头
    T* last;           // 此迭代器所指之缓冲区的尾后（含备用空间）
    map_pointer node;  // 指向 管控中心
...
    
    void set_node(map_pointer new_node)
    {
        node = new_node;
        first = *new_node;
        last = first + difference_type(buffer_size());
    }
    // 以下各个重载是__deque_iterator<>成功运作的关键
    reference operator*() const 
    {
        return *cur;
    }
    pointer operator->() const
    {
        return &(operator*());
    }
    difference_type operator-(const self& x) const
    {
        return  difference_type(buffer_size()) * (node - x.node - 1) +
                (cur - first) + (x.last - x.cur);
    }
    self& operator++()
    {
        ++cur;                   // 切换至下一个元素
        if (cur == last){        // 如果已达到所在缓冲区的尾端
            set_node(node + 1);  // 就切换至下一节点（亦即缓冲区）
            cur = first;         //   的第一个元素
        }
        return *this;
    }
    self operator++(int)         // 后置式标准写法
    {
        self tmp = *this;
        ++*this;
        return tmp;
    }
    self& operator--()
    {
        if (cur == first){
            set_node(node - 1);
            cur = last;
        }
        --cur;
        return *this;
    }
    self operator--(int)        // 后置式标准写法
    {
        self tmp = *this;
        --*this;
        return tmp;
    }
    
    // 以下实现随机存取
    self& operator+=(difference_type n)
    {
        difference_type offset = cur + n - first;
        if (offset >= 0 && offset < difference_type(buffer_size())){
            // 目标位置在同一缓冲区内
            cur += n;
        } else {
            // 目标位置不在同一缓冲区
            difference_type node_offset = 
                offset > 0 ?
                offset / difference_type(buffer_size()) :
                -difference_type((-offset - 1) / buffer_size()) - 1;
            // 切换至正确的缓冲区
            set_node(ndoe + node_offset) ;
            // 切换至正确的元素
            cur = first + (offset - node_offset*difference_type(buffer_size()));
        }
        return *this;
    }
    // 利用operator+= 来完成operator-=
    self& operator-=(difference_type n)
    {
        return operator+=(-n);
    }
    self operator+(difference_type n)
    {
        self tmp = *this;
        tmp += n;                      //调用operator+=
        return tmp;
    }
    self operator-(difference_type n)
    {
        self tmp = *this;
        return tmp -= n;               //调用operator-=
    }
    //以下实现随机存取，迭代器可以直接跳跃n个距离
    reference operator[](difference_type n) const
    {
        return *(*this + n);           //调用operator*, operator+
    }
    bool operator==(const self& x) const
    {
        return cur == x.cur;
    }
    bool operator!=(cosnt self& x) const
    {
        return !(*this == x);
    }
    bool operator<(cosnt self& x) const
    {
        return (node == x.node) ?
               cur < x.cur :
               node < x.node ;
    }
};

deque 部分接口

//将pos位置于元素清除，后续元素向前移动，返回pos位置的元素指针
iterator erase(iterator pos);
//清除[first, last)位置的元素，返回first位置元素的指针
iterator erase(iterator first, iterator last);
//在元素*pos位置前方插入，返回pos位置的元素，即返回插入元素的迭代器
iterator insert(iterator position, const value_type& x);

主体结构

template<class T, class Alloc = alloc, size_t BufSiz = 0>
class deque
{
public:
    typedef T            value_type;
    typedef value_type*  pointer;
    typedef size_t       size_type;
    
public:         // Iterators
    typedef __deque_iterator<T, T&, T*, BufSiz> iterator;

protected:      // Internal typedefs
    // 元素的指针的指针(pointer of pointer of T)
    typedef pointer* map_pointer;

protected:     // Data members
    iterator start;      // 表现第一个节点
    iterator finish;     // 表现最后一个节点
    map_pointer map;     // 指向map， map是块连续空间，
                         // 其每个元素都是个指针，指向一个节点(缓冲区)
    size_type map_size;  // map内有多少个指针
    ...
    // 空间配置器，每次配置一个元素大小
    typedef simple_alloca<value_type, Alloc> data_allocator;
    // 空间配置器，每次配置一个指针大小
    typedef simple_alloc<pointer, Alloc> map_allocator;
    void fill_initialize(size_type n, const value_type& value);
    void create_map_and_nodes(size_type);
    void initial_map_size();
    void allocate_node();
    void push_back_aux(const value_type&);
    void reserve_map_at_back();
    void push_front_aux(const value_type&);
    void reserve_map_at_front();
    void reallocate_map(size_type);
    void pop_back_aux();
    void pop_front_aux();
    iterator insert_aux(iteratpr, const value_type&);
public:  // constructor deconstructor
    deque(int n, const value_type& value) :
        start(), finish(), map(0), map_size(0)
    {
        fill_initialize(n, value);
    }
    deque();
    ~deque();

public:
    iterator begin()
    {
        return start;
    }
    iterator end()
    {
        return finish;
    }
    reference operator[](size_type n)
    {
        // return start[n]; //调用__deque_iterator<>::operator[]
        return *(start + n);
    }
    reference front()
    {
        return *start;
    }
    reference back()
    {
        // 严重错误，finish始终应指向尾置元素。return *(--finish); ❌
        iterator tmp = finish;
        --tmp;
        return *tmp;
        // return *(finish - 1) 也行吧
    }
    size_type size() const
    {
        return finish - start;
    }
    size_type max_size() const
    {
        return size_type(-1);
    }
    bool empty() const
    {
        return finish == start;
    }
    void push_back(const value_type& t)
    {
        if (finish.cur != finish.last-1){
            // 最有缓冲区尚有一个以上的备用空间
            construct(finish.cur, t); //直接在备用空间上构造元素
            ++finish.cur;             //调整最后缓冲区的使用状态
        } else { //最后缓冲区只剩一个元素备用空间
            push_back_aux(t);
        }
    }
    void push_front(const value_type& t)
    {
        if (start.cur != start.first) { //第一缓冲区上有备用空间
            --start.cur;
            construct(start.cur, t);
        } else {                        //无备用空间
            push_front_aux(t);
        }
    }
    void pop_back()
	{
	    if (finish.cur != finish.first){
	        //最后缓冲区有一个(或更多)元素
	        --finish.cur;              //调整指针，相当于排除了最后元素
	        destroy(finish.cur);       //将最后元素析构
	    } else {
	        //最后缓冲区没有任何元素
	        pop_back_aux();            //这里进行缓冲区的释放工作
	    }
	}
	void pop_front()
	{
	    if (start.cur != start.last - 1){
	        //第一个缓冲区有一个(或更多)元素
	        destroy(start.cur);           //将第一元素析构
	        ++start.cur;                  //调整指针，相当于排除了第一元素
	    } else {
	        pop_front_aux();              //这里将进行缓冲区的释放工作
	    }
	}
	void clear();
	iterator erase(iterator pos);
	iterator erase(iterator, iterator);
	iterator insert(iterator, const value_type&);
};
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::
fill_initialize(size_type n, const value_type& value)
{
    create_map_and_nodes(n);  //把deque的结构都产生并安排好
    map_pointer cur;

    __STL_TRY {
        // 为每个节点的缓冲区设定初值
        for (cur = start.node; cur < finish.node; ++cur){
            uninitialized_fill(*cur, *cur + buffer_size(), value);
        }
        // 最后一个节点的设定稍有不同，尾端可能有备用空间
        uninitialized_fill(finish.first, finish.cur, value);
    } catch (...) {
        ...
    }
}
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::create_map_and_nodes(size_type num_elements)
{
    // 需要节点数=元素个数/每个缓冲区可容纳的元素个数 + 1
    // 如果刚好整除，会多一个节点
    size_type num_nodes = num_elements / buffer_size() + 1;
    // 一个map要管理几个节点，最少8个，最多是所需节点数+2
    // 前后各预留一个，扩充时可用
    map_size = max(initial_map_size(), num_nodes + 2);
    //配置出一个具有map_size各节点的map
    map = map_allocator::allocate(map_size);
    //令nstart和nfinish指向map所拥有至全部节点的最中央区段
    //保持在最中央，可使头尾两端的扩充能量一样大，每个节点可对应一个缓冲区
    map_pointer nstart = map + (map_size - num_nodes) / 2;
    map_pointer nfinish = nstart + num_nodes - 1;
    
    map_pointer cur;
    __STL_TRY {
        // 为map内的每个现用节点配置缓冲区，所有缓冲区加起来就是deque的
        // 可用空间，最有一个缓冲区可能有一些余留
        for (cur = nstart; cur <= nfinish; ++cur){
            *cur = allocate_node();
        }
    } catch (...) {
        // commit or rollback: 若非全部成功，就一个不留
        ...
    }
    // 为deque内的两个迭代器start和finish设置正确内容
    // start指向第一个节点，finish指向最后一个节点
    // start.cur指向deque的第一个元素，finish.cur指向deque的尾后元素
    start.set_node(nstart);
    finish.set_node(nfinish);
    start.cur = start.first;
    // 前面说过，如果刚好整除，会多配置一个节点，此时令cur指向这多
    // 配置的一个节点(所对应之缓冲区)的起始位置
    finish.cur = finish.first + num_elements % buffer_size(); 
}
//只有当finish.cur == finish.last-1时才会被调用
//也就是说只有当最后一个缓冲区只剩一个备用元素空间时才会被调用
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::push_back_aux(const value_type& t)
{
    value_type t_copy = t;
    reserve_map_at_back(); //若符合某种条件则必须重换一个map
    *(finish.node + 1) = allocate_node();  //配置一个新节点(缓冲区)
    __STL_TRY {
        construct(finish.cur, t_copy);     //针对标的元素设值
        finish.set_node(finish.node + 1);  //改变finish令其指向新节点
        finish.cur = finish.first;         //设定finish的状态
    }
    __STL_UNWIND( deallocate_node( *(finish.node+1) ) );
}
//只有当start.cur == start.first时才会被调用
//当第一个缓冲区没有元素备用空间时才会被调用
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::push_front_aux(const value& t)
{
    value_type t_copy = t;
    reserve_map_at_front(); //符合某种条件则必须重换一个map
    *(start.node - 1) = allocate_node(); //配置一个新节点
    __STL_TRY {
        start.set_node(start.node - 1);  //改变start，令其指向新节点
        start.cur = start.last - 1;      //设定start的状态
        construct(start.cur, t_copy);    //针对标的元素设值
    } catch (...) {
        // commit or rollback : 若非全部成功，就一个不留
        start.set_node(start.node + 1);
        start.cur = start.first;
        deallocate_node(*(start.node - 1));
        throw;
    }
}
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::reserve_map_at_back(size_type nodes_to_add = 1)
{
    if (nodes_to_add > map_size - (finish.node - map + 1)){
        // 如果map尾端的节点备用空间不足，必须重换一个map，配置更大的，拷贝原来的，释放原来的
        reallocate_map(nodes_to_add, false);
    }
}
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::reserve_map_at_front(size_type nodes_to_add = 1)
{
    if (nodes_to_add > start.node - map){
        // 如果map尾端的节点备用空间不足，必须重换一个map，配置更大的，拷贝原来的，释放原来的
        reallocate_map(nodes_to_add, true);
    }
}
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::reallocate_map(size_type nodes_to_add, bool add_to_front)
{
    size_type old_num_nodes = finish.node - start.node + 1;
    size_type new_num_nodes = old_num_nodes + nodes_to_add;
    map_pointer new_nstart;
    if (map_size > 2*new_num_nodes){
        new_nstart = map + (map_size - new_num_nodes) / 2
                     + (add_at_front ? nodes_to_add : 0);
        if (new_nstart < start.node){
            copy(start.node, finish.node + 1, new_nstart);
        } else {
            copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
        }
    } else {
        size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
        // 配置一块空间准备给新map使用
        map_pointer new_map = map_allocator::allocate(new_map_size);
        new_nstart = new_map + (new_map_size - new_num_nodes) / 2
                             + (add_at_front ? nodes_to_add : 0);
        copy(start.node, finish.node + 1, new_start);
        map_allocator::deallocatr(map, map_size);
        map = new_map;
        map_size = new_map_size;
    }
    start.set_node(new_nstart);
    finish.set_node(new_nstart + old_num_nodes - 1);
}
// 只有finish.cur == finish.first时才会被调用
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::pop_back_aux()
{
    deallocate_node(finish.first);    //释放最后一个缓冲区
    finish.set_node(finish.node - 1); //调整finish的状态，使指向
    finish.cur = finish.last - 1;     //  上一个缓冲区的最后一个元素 
    destroy(finish.cur);              //将该元素析构
}
//只有当start.cur == start.last - 1时才会被调用
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::pop_front_aux()
{
    destroy(start.cur);               //将第一缓冲区的第一个元素析构
    deallocate_node(first.first);     //释放第一缓冲区
    start.set_node(finish.node + 1);  //调整start的状态，使指向
    start.cur = start.first;          //  下一个缓冲区的第一个元素
}
//最终需要保留一个缓冲区，这是deque的策略，也是deque的初始状态
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::clear()
{
    //针对头尾以外的每一个缓冲区(他们一定时饱满的)
    for (map_pointer node = first.ndoe+1; ndoe < finish.node; ++node){
        destroy(*node, *node + buffer_size());
        data_allocator::deallocate(*node, buffer_size());
    }
    if (start.ndoe != finish.node){        //有头尾两个缓冲区
        destroy(start.cur, start.last);    //将头缓冲区的目前所有元素析构
        destroy(finish.first, finish.cur); //将尾缓冲区目前所有元素析构
        // 释放尾缓冲区，头部缓冲区保留
        data_allocator::deallocate(finish.first, buffer_size());
    } else { // 只有一个缓冲区
        destroy(start.cur, finish.cur);    //将此唯一缓冲区内的所有元素析构
        // 保留该缓冲区
    }
    finish = start;  //调整状态
}
//清楚pos所指的元素，pos为清除点
template<class T, class Alloc, size_t BufSiz>
deque<T, Alloc, BufSiz>::iterator deque<T, Alloc, BufSiz>::erase(iterator pos)
{
    iterator next = pos;
    ++next;
    difference_type index = pos - start;  //清除点之前的元素个数
    if (index < (size() >> 1)){           //如果清除点之前的元素较少
        copy_backward(start, pos, next);  //  就移动清除点之前的元素
        pop_front();
    } else {                              //清除点之后的元素比较少
        copy(next, finish, pos);          //  就移动清除点之后的元素
        pop_back();
    }
    return start + index;
}
//清除[first, last)区间内的所有元素
template<class T, class Alloc, size_t BufSiz>
deque<T, Alloc, BufSiz>::iterator
deque<T, Alloc, BufSiz>::erase(iterator first, iterator last)
{
    if (first == start && last == finish){
        clear();
        return finish;
    } else {
        difference_type n = last - first;
        difference_type elems_before = first - start;
        if (elems_before < (size() - n) / 2){          // 前方元素比较少
            copy_backward(start, first, last);
            iterator new_start = start + n;
            destroy(start, new_start);
            // 将缓冲区释放
            for (map_pointer cur = start.node; cur < new_start.node; ++cur){
                data_allocator::deallocate(*cur, buffer_size());
            }
            start = new_start;
        } 
        else {                                       // 后方元素比较多
            copy(last, finish, first);
            iterator new_finish = finish - n;
            destroy(new_finish, finish);
            // 释放缓冲区
            for (map_pointer cur = new_finish.node+1; cur<=finish.node; ++cur){
                data_allocator::deallocate(*cur, buffer_size());
            }
            finish = new_finish;
        }
        return start + elems_before;
    }
}
iterator insert(iterator position, const value_type& x)
{
    if (position.cur == start.cur) {
        // 也可吧 position == start
        push_front(x);
        return start;
    } else if (position == finish) {
        push_back(x);
        iterator tmp = finish;
        --tmp;
        return tmp;
    } else {
        return insert_aux(position, x);            //交给insert_aux去做
    }
}
template<class T, class Alloc, size_t BufSiz>
typename deque<T, Alloc, BufSiz>::iterator
deque<T, Alloc, BufSiz>::insert_aux(iterator pos, const value_type& x)
{
    difference_type index = pos - start; //插入点之前的元素个数
    value_type x_copy = x;
    if (index < size() / 2){
        push_front(front());
        iterator front1 = start;
        ++front1;
        iterator front2 = front1;
        ++front2;
        pos = start + index;
        iterator pos1  = pos;
        ++pos1;
        copy(front2, pos1, front1);
    } else {
        push_back(back());
        iterator back1 = finish;
        --back1;
        iterator back2 = back1;
        --back2;
        pos = start + index;
        copy_backward(pos, back2, back1);
    }
    *pos = x_copy();
    return pos;
}

stack 并非容器而是容器适配器，本质上就是把容器再进行包装
First In Last Out, FILO

stack标准操作为top, push, pop, size, empty
不支持随机访问

template<class T, class Sequence = deque<T>>
class stack
{
    // 以下的__STL_NULL_TMPL_ARGS会展开为<>
    friend bool operator==__STL_NULL_TMPL_ARGS(const stack&, const stack&);
    friend bool operator<__STL_NULL_TMPL_ARGS(const stack&, const stack&);
private:
    // 以下的__STL_NULL_TMPL_ARGS会展开为<>
    friend bool operator==__STL_NULL_TMPL_ARGS(const stack&, const stack&);
    friend bool operator<__STL_NULL_TMPL_ARGS(const stack&, const stack&);
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:
    bool empty() const
    {
        return c.empty();
    }
    size_type size() const
    {
        return c.size();
    }
    reference top()
    {
        return c.back();
    }
    const_reference top() const
    {
        return c.back();
    }
    void push(const value_type& x)
    {
        c.push_back(x);
    }
    void pop()
    {
        c.pop_back();
    }
    stack(/* args */);
    ~stack();
};
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;
}
// stack没有迭代器

queue并非容器而是容器适配器，本质上就是把容器再进行包装
First In First Out, FIFO

queue标准操作为empty, size, front, back, push, pop
不支持随机访问

template<class T, class Sequence = deque<T>>
class queue
{
    // 以下的__STL_NULL_TMPL_ARGS会展开为<>
    friend bool operator==__STL_NULL_TMPL_ARGS(const queue&, const queue&);
    friend bool operator<__STL_NULL_TMPL_ARGS(const queue&, const 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; //底层容器
public:
    // 完全利用Sequence c的操作，完成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();
    }
    queue(/* args */);
    ~queue();
};
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;
}
// queue没有迭代器

priority_queue 优先级队列

priority_queue内部的元素按照一定的优先级进行排列，本质上就是把容器再进行包装

提供的接口：empty, size, top, push, pop
不支持遍历也不支持随机访问

最后一个元素之前的满足堆条件，push_heap将最后的元素插入堆中，插入之后整个数组又都满足堆条件了。
,整个数组满足堆条件，pop_heap将堆顶元素放到最后，此时该数组不满足堆条件，但最后一个元素之前的满足堆条件。

// 优先级队列 priority_queue
template<class T, class Sequence = vector<T>,
         class Compare = less<typename Sequence::value_type> >
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) {}
    // 下述make_heap(), push_heap(), pop_heap()为泛型算法
    // 任一个构造函数都立刻于底层容器内产生一个implicit representation heap
    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); }
public:
    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是泛型算法
            push_heap(c.begin(), c.end(), comp); 
        }
        __STL_UNWIND(c.clear());
    }
    void pop()
    {
        __STL_TRY {
            // 这里pop_heap是泛型算法
            pop_heap(c.begin(), c.end(), comp);
            c.pop_back();
        }
        __STL_UNWIND(c.clear());
    }
};

单向链表 slist

slist内部是一个单项链表，内部只有一个数据成员，为链表头部节点对象，head.next指向第一个元素所在的节点。

接口

begin, end, size, empty, front, push_front, pop_front, swap

迭代器

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_node->next = prev_node->next;
    prev_node->next = new_node;
    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;
}

// iterator
struct __slist_iterator_base
{
    typedef size_t                 size_type;
    typedef ptrdiff_t              difference_type;
    typedef forward_iterator_tag   iterator_category;

    __slist_node_base*             node; //指向节点基本结构

    __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_iterator : public __slist_iterator_base
{
    typedef __slist_iterator<T, T&, T*>              iterator;
    typedef __slist_iterator<T, const T&, const T*>  const_iterator;
    typedef __slist_iterator<R, Ref, Ptr>            self;

    typedef T                value_type;
    typedef Ptr              pointer;
    typedef Ref              reference;
    typedef __slist_node<T>  list_node;

    __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;
    }
    pointer operator->() const
    {
        return & (operator*());
    }
    self& operator++()
    {
        incr();
        return *this;
    }
    self operator++(int)
    {
        self tmp = *this;
        incr();
        return tmp;
    }
};

疑问？

为何该迭代器采用这种继承体系

slist 数据结构

// 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, cosnt T&, const T*>  const_iterator;
private:
    typedef __slist_node<T>                 list_node;
    typedef __slist_node_base               list_node_base;
    typedef __slist_iterator_base           iterator_base;

    typedef simple_alloc<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;
    }
    // 取头部元素
    reference front()
    {
        return ((list_node*)head.next)->data;
    }
    // 从头部插入元素
    void push_front(cosnt value_type& x)
    {
        __slist_make_link(&head, create_node(x));
    }
    //从头部取走元素
    void pop_front()
    {
        list_node* node = (list_node*) head.next;
        head.next = node;
        destroy_node(node);
    }
    ...
};

---

总结

总结：