登录后台

页面导航

本文编写于 120 天前,最后修改于 26 天前,其中某些信息可能已经过时。

基础

STL六大组件

空间配置器(allocator):分配空间存放数据,在xmemory文件中

迭代器:

容器:

算法:

仿函数:

适配器:

allocator

SGI标准空间配置器,std::allocator

SIG定义了一个符合部分标准的的配置器(alloctor),但是效果不佳,只是单纯把 ::operator new::operator delete 做了一层封装

必要接口

allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
allocator::rebind
allocator::allocator()
allocator::allocator(const allocator&)
tmplate <class U>allocator::allocator(const allocator<U>&)
allocator::~allocator()
pointer allocator::address(reference x) const)
const pointer allocator::address(const_reference x) const
pointer allocator::allocate(size_type n, void* = 0)
void allocator::deallocate(pointer p, size_type n)
size_type allocator::max_size() const
void allocator::construct(pointer p, const T& x)
void allocator::destroy(pointer p)

SGI特有的配置器,std::alloc

class Person{};
Person* P1 = new Person;    // 分配好内存,调用构造函数
delete P1;                    // 调用析构函数,释放内存

我们使用new的时候,内部实现了两个步骤,先开辟了空间,然后调用类的构造函数,在使用delete的时候也一样,使用了两个步骤,先调用类的析构函数,然后释放空间

STL alloctor将这两阶段分开操作:

  • 内存配置由 alloc::allocate() 负责
  • 内存释放由 alloc::deallocate() 负责
  • 构造函数由 ::construct() 负责
  • 析构函数由 ::destory 负责

STL规定的配置器定义在 <memory>内, <memory> 内有如下三个重要头文件

  • <stl_construct.h> 里面定义了两个全局函数 construct() destroy(),分别负责对象的构造和析构
  • <stl_alloc.h> 里面定义了一二级配置器
  • <stl_uninitialized.h> 里面定义了一些全局函数,用来填充和复制大块内存数据

image-20220410192103755

construct() 接受一个指针p和一个初值value,该函数将初值设定到指针所指的地址上

destroy() 则分为两个,第一个直接接受一个指针,然后调用该对象的析构函数,第二个则接受两个迭代器,然后将迭代器范围内的对象析构掉

SGI设置了双层级的配置器来对内存配置和释放,用来处理内存破碎的问题,第一级配置器采用了malloc()和free()两个函数,

第二级则分两种情况

  • 若分配的区块大于128bytes,则调用第一级配置器
  • 若分配的区块小于128,则采用memary pool方式整理

是否采用第二级取决于__USE_MALLOC是否被定义,无论使用的是第一级还是第二级,SGI STL都准备了一个接口,去使得配置器能够达到STL的标准,SGI STL全部使用该接口

template<class T, class Alloc>
class simple_alloc{
public:
    static T *allocate(size_t n){return 0 == n ? 0 : (T*) Alloc::allocate(n *sizeof(T));}
    static T *allocate(void){return (T*) Alloc::allocate(sizeof (T));}
    static void deallocate(T *p, size_ n){if (0 != n) Alloc::deallocate(p, n * sizeof(T));}
    static void deallocate(T *p){ Alloc::deallocate(p, sizeof(T));}
};

第一级配置器__malloc_alloc_template,使用 malloc free relloc 来实现配置、释放、重配置操作

第二级配置器__default_alloc_template,当区块足够大时,则移交给第一级配置器分配,否则使用内存池,内存池维护了一个链表

default_alloc_tmplate 拥有配置器的两个标准接口 allocate deallocate ,用于分配空间以及释放空间

allocate():当区块大小大于128bytes时,调用第一级配置器,否则就检查free_list,若里面有可用的就拿来用,否则将区块调整至8的整数倍,然后调用refill()来为free_list重新填充空间

static void * allocate(size_t n){
    obj * volatile * my_free_list;
    boj * result;
    if (n > (size_t) __MAX_BYTES){        // 如果大于128则调用第一级配置器
        return (malloc_alloc::allocate(n));
    }
    my_free_list = free_list + FREELIST_INDEX(n);        // 在free_list中寻找链表
    result = *my_free_list;
    if(result == 0){            // 若没找到,则调用refill()函数重新填充
        void *r = refill(ROUND_UP(n));
        return r;
    }
    *my_free_list = result->free_list_link;        // 调整fre list
    return (result);
}

deallocate():当区块大于128bytes时,调用第一级配置器,否则寻找对应的free list回收

static  void deallocate(void* p, size_t n){
    obj *q = (obj *)p;
    obj* volatile * my_free_list;
    if (n >(size_t) __MAX_BYTES){        // 如果大于128bytes则调用第一级配置器
        malloc_alloc::deallocate(p, n);
        return;
    }
    my_free_list = free_list + FREELIST_INDEX(n);        // 寻找对应free list
    q -> free_list_link = *my_free_list;        // 回收
    *my_free_list = q;
}

refill():当调用allocate()时发现没有可用的free list 时,调用refill()为free list 重新填充空间,该函数会从内存池中取出区块获取新节点

template <bool thread, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n){
    int nobjs = 20;
    char * chunk = chunk_alloc(n, nobjs);    // 尝试取得20个区块作为节点
    obj *volatile * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;
    if(1 == nobjs) return(chunk);        // 如果只有一个则直接返回给客端
    my_free_list = free_list + FREELIST_INDEX(n);
    result = (obj *)chunk;
    *my_free_list = next_obj = (obj *)(chunk + n);
    for(i = 1; ; i++){        // 将free list的各节点串起来
        current_obj = next_obj;
        next_obj = (obj *)((char *)next_obj + n);
        if(nobjs - 1 == i){
            current_obj -> free_list_link = 0;
            break;
        }else{
            current_obj -> free_list_link = next_obj;
        }
    }
    return (result);
}

内存基本处理工具

STL定义了5个全局函数 construct() / destory() / uninitialized_copy() / uninitialized_fill() / uninitialized_fill_n()

uninitialized_copy()
template<class InputIterator, class ForwardIterator>
ForwaldIterator
uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);

能将内存的配置和对象的构造行为分离开来

uninitialized_fill()
template<class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

能将内存的配置和对象的构造行为分离开来

uninitialized_fill_n()
template<class ForwardIterator, class Size, class T>
ForwardIterator
uninitialized_fill_n(ForwardIterator first, Size n, const T& x);    

能将内存的配置和对象的构造行为分离开来

迭代器

迭代器是容器和算法的桥梁,迭代器是一个类似指针的对象,迭代器最重要的作用就是内容访问和成员访问,即对 operator* 和 operator-> 进行重载,旧版的STL中有一个包装指针的对象 auto_ptr

auto_ptr<string> ptr(new string("HELLO"));    // 使用 new分配一块空间,然后将结果作为suto_ptr<string> 的初值

auto_ptr 的简化版本

template<class T>
class auto_ptr
{
public:
    explicit auto_ptr(T *p=0):pointer(p){}
    template<class U>
    auto_ptr(auto_ptr<U>& rhs):pointee(rhs.release()){}
    ~auto_ptr(){delete pointee;}
    template<class U>
    auto_ptr<T>& operator=(auto_ptr<U>& rhs)
    {
        if(this!=&rhs) reset(rhs.release());
        return *this;
    }
    T& operator*() const {return *pointee;}
    T* operator->() const {return pointee;}
    T* get() const {return pointee;}  
private:
    T *pointee;
}.

一个简单的迭代器

template <class Item>
struct LisIter
 {
     Item* ptr;
     ListIter(Item* p=0):ptr(p){}
     //关键操作

     Item& operator*() const {return *ptr;}
     Item* operator->() const {return ptr;}
     ListIter& operator++()
     {
        ptr=ptr->next();
        return *this;
     } 
     ListIter operator++(int)
     {
        ListIter tmp=*this;
        ++*this;
        retrun tmp;
     }
     bool operator==(const ListIter& i) const
     {
        return ptr!=i.ptr;
     }
 }; 

迭代器相应型别

是一种类似的封装行为

traits编程技法

迭代器所指的型别是迭代器的 value type ,当value作为函数的返回值时,就无法正常工作了,可以使用内嵌类型避免

template <class T>
struct MyIter
{
    //内嵌类型声明

    typedef T value_type;
    T* ptr;
    MyIter(T* p=0):ptr(p){}
    T& operator*() const {return *ptr;} 
}

template <class I>
typename I::value_type func(I ite){return *ite;}

MyIter<int> ite(new int(8));
cout<<func(ite);

使用 template<> 来对基本的数据类型进行封装

std::iterator 的保证

STL 提供了一个iterator的类,使得每个新迭代器都继承它,保证规范化

template <
      class Category,
      class T,
      class Distance=ptrdiff_t,
      class Pointer=T*,
      class Reference=T&
          >
struct iterator
{
  typedef Category iterator_category;
  typedef T value_type;
  typedef Distance difference_type;
  typedef Pointer pointer;
  typedef Reference reference;
  
};

//使用

std::iterator<std::forward_iterator_tag,Item> 

容器

容器分为序列式容器和关联式容器

image-20220412172947809

vector

可以自行分配空间,动态扩充

简单的vector实现
template<class T, class Alloc = alloc>
class vector{
public:
    typedef T   value_type;
    typedef value_type*     pointer;
    typedef value_type*     iterator;
    typedef value_type&     reference;
    typedef size_t          size_type;
    typedef ptrdiff_t       difference_type;

protected:
    typedef simple_alloc<value_type, Alloc> data_allocator;
    iterator start;
    iterator finish;
    iterator end_of_storage;

    void insert_aux(iterator position, const T& x);
    void deallocate(){
        if(start)
            data_allocator::deallocate(start, end_of_storage - start);
    }
    void fill_initialize(size_type n, const T& value){
        start = allacate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish;
    }

public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const{ return size_type(end - begin); }
    size_type capacity() const { return size_type(end_of_storage - start); }
    bool empty() const { return begin() == end(); }
    reference operator[] (size_type n) const { return *(begin() + n); }
    vector() : start(0), finish(), end_of_storage(0) {}
    vector(size_type n, comst T& value) { fill_initiialize(n, value); }
    vector(int n, const T& value) { fill_initialize(n, value); }
    vector(long n, cpnst T& value) { fill_initialize(n, value); }
    explicit vector(size_type n) { fill_initialize(n, T()); }

    ~vector(){
        destroy(start, finish);
        deallocate();
    }
    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
    void push_back(const T& x){
        if(finish != end_of_storage){
            construct(finish, x);
            ++finish;
        }
        else{
            insert_aux(end(), x);
        }
    }
    void pop_back(const T& x){
        --finish;
        destory(finish, x);
    }

    iterator erase(iterator position){
        if(position + 1 != end())
            copy(position + 1, finish, position);
        --finish;
        destroy(finish);
        return position;
    }

    iterator resize(size_type new_size){
        resize(new_size, T());
    }
    void clear() { erase(begin(), end()); }

protected:
    iterator allocate_and_fill(size_type n, const T& x){
        iterator result = data_allocator::allocate(n);
        uninitialized_fill_n(result, n, x);
        return result;
    }
};

内存结构

image-20220412223610486

数据结构

vector是一个线性连续的空间,使用两个迭代器 start 和 finish 来分配连续空间中已被使用的范围,并使用迭代器 end_of_storage

template<class T, class Alloc=alloc>
class vector{
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
}
相关元素操作

push_back

void push_back(const T& x){
    if(finish != end_of_storage){        // 判断是否有空间
        construct(finish, x);        // 有的话就插入数据
        ++finish;
    }
    else{
        insert_aux(end(), x);        // 空间不足则分配空间
    }
}

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(interator position, const T& x){
    if(finish != end_of_storage){        // 若还有备用空间
        construct(finish, *(finish - 1));        // 在备用空间的起始处构造一个函数,并以vector最后一个元素为其初值
        ++finish;
        T x_copy = x;
        copy_backward(position, finish - 2, finish - 1);
        *position = x_copy;
    }
    else{        // 若空间
        const size_type old_size = size();        // 把原来的size大小赋值给old_size
        const size_type len = old_size != 0 ? 2 * old_size : 1;        // 若原来的size大小是0则赋值为1,否则加倍
        iterator new_start = data_allocator::allocate(len);        // 实际的配置
        iterator new_finish = new_start;
        try{
            new_finish = unitialized_copy(start, position, new_start);    // 将原来的vector的内容拷贝到新的vector
            construct(new_finish, x);        // 对新元素设定初值x
            ++new_finish;
            new_finish = unintialized_copy(position, finish, new_finish);    // 将原vector的备用空间中的内容也拷贝过来
        }
        catch(...){
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }
        destroy(begin(), end());        // 析构并释放原vector
        deallocate();
        start = new_start;        // 调整迭代器指向新的vector
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

pop_back

void pop_back(){
    --finish;
    destroy(finish);
}

erase

// 删除某个区间的元素
iterator erase(iterator first, iterator last){
    iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first);
    return first;
}
// 删除某一个元素
iterator erase(iterator position){
    if(position + 1 != end()){
        copy(position + 1, finish, position);
    }
    --finish;
    destroy(finish);
    return position;
}

clear

void clear(){
    erase(begin(), end());
}

insert

template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x){
    if(n != 0){        // 插入的的元素不等于0
        if(size_type(end_of_storage - finish) >= n){    // 备用空间大于等于插入数据的数量
            T x_copy = x;
            const size_type elems_after = finish - position;
            iterator ols_finish = finish;
            if(elems_after > n){
                uninitialized_copy(finish - n, finish, finish);
                finish += n;
                copy_backward(position, old_finish - n, old_finish);
                fill(position, position + n, x_copy);
            }
        }
        else{        // 备用空间小于要插入的数据数量
            const size_type old_size = size();        // 原来的大小保存到old_size里面
            const size_type len = old_size + max(old_size, n);        // 将原来的大小和(原来的大小和要插入数据的大小中大的一个)相加
            iterator new_start = data_allocator::allocate(len);        // 利用配置器分配这么大的空间
            iterator new_finish = new_start;        // 新开辟的空间的头尾都指向分配的空间的开头
            __STL_TRY{        // 将旧的数据复制过去
                new_finish = uninitialized_copy(start, position, new_start);
                new_finish = uninitialized_fill_n(new_finish, n, x);
                new_finish = uninitialized_copy(position, finish, new_finish);
            }
            #ifdef __STL_USE_EXCEPTIONS
                catch(...){
                    destroy(new_start, new_finish);
                    data_allocator::deallocate(new_start, len);
                    throw;
                }
            #endif
            destroy(start, finish);        // 将原空间释放掉
            deallocate();
            start = new_start;
            finish = new_finish;
            end_of_storage = new_start + len;
        }
    }
}

image-20220414201235807

list

双向链表

迭代器的设计
template <class T, class Ref, class Ptr>
struct __list_iterator{
    typedef __list_iterator<T, T&, T*> iterator;
    typedef __list_iterator<T, Ref, Ptr> self;
    
    typedef bidirectional_iterator_tag iterator_category;
    typedef T type_valule;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node<T>* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
    link_type node;
    
    __list_iterator(link_type x) : node(x){}
    __list_iterator(){}
    __list_iterator(const iterator& x) : node(x.node){}
    
    bool operator==(const self& x) const { return node == x.node };
    bool operator==(const self& x) const { return node != x.node };
    
    reference operator*() const { (*node).data; }
    pointer operator->() const { &(operator*()); }
    self& operator++(){
        node = (link_type)((*node).next);
        return *this;
    }
    self operator++(){
        self tmp = *this;
        ++*this;
        return tmp;
    }
    self& operator--(){
        node = (link_type)((*node).prev);
        return *this;
    }
    self operator--(int){
        tmp = *this;
        ++*this;
        return tmp;
    }
}
数据结构

SGI 中的list是一个双向环状列表,只需一个指针即可实现整个列表

template <class T, class Alloc = alloc>
class list{
protected:
    typedef __list_node<T> list_node;
public:
    typedef list_node* link_type;

protect:
    link_type node;        // 使用一个指针表示整个环状双向链表
}

让指针指向尾端的一个空白点,node就可以符合前闭后开的要求

iterator begin() { return (link_type)(*node).next; }
iterator end() { return node; }
bool empty() { return node->next == node; }
size_type size() const {
    size_type result = 0;
    result = distance(begin(), end(), result);
    return result;
}
reference front() { return *begin(); }
reference back() { return *(--end()); }
构造与内存管理

list缺省使用alloc配置器,还定义了一个 _list_node_allocator

template <class T, class Alloc=alloc>
class list{
protect:
    typedef __list_node<T> list_node;
    typedef simple_alloc<list_node, Alloc> list_node_allocator;
    ...
}

list_node_allocator(n)表示配置n个节点

protected:
    link_type get_node() { return list_node_allocator::allocate(); }    // 配置一个节点
    void put_node(link_type) { return list_node_allocator::allocate(); }    // 释放一个节点
    link_type create_node(const T& x) {        // 构造一个节点
        link_type p = get_node();
        construct(&p->data, x);
        return p;
    }
    void destroy_node(link_type p) {        // 销毁一个节点
        destroy(&p->data);
        put_node;
    }

list内部有很多constructors,其中有一个default constructor,可以创建一个空的链表出来

public:
    list() { empty_initialize(); }

protected:
    void empty_initialize(){
        node = get_node();
        ndoe->prev = node;
        node->next = node;
    }
插入数据
void push_back(const T& x) { insert(end(), x); }    // push_back内部调用insert()

insert()有多个重载版本

iterator insert(iterator position, const T& x){
    link_type tmp = create(x);
    tmp->next = position.node;
    tmp->prev = position.node->prev;
    ((link_type)(position.node->prev))->next = tmp;
    position.node->prev = tmp;
    return tmp;
}
元素的操作

push_front

void push_front(const T& x) { insert(begin(), x); }

push_back

void push_back(const T& x) { insert(end(), x); }

erase

interator erase(iterator position){
    link_type next_node = link_type(position.node->next);
    link_type prev_node = link_type(posiiton.node->prev);
    next_node->prev = prev_node;
    prev_node->next = next_node;
    destroy_node(position.node);
    return iterator(next_node);
}

pop_front

void pop_front() { erase(begin()); }

pop_back

void pop_back() {
    iterator tmp = end();
    return(--tmp);
}

clear

template <class T, class Alloc>
void list<T, Alloc>::clear() {
    link_type cur = =(link_type) ndoe->next;
    while (cur != node){        // 遍历每一个节点
        link_type tmp = cur;
        cur = (link_type) cur->next;
        destroy_node(tmp);        // 销毁一个节点
    }
    node->next = node;        // 恢复node的原始状态
    node->prev = node;
}

remove

template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
    iterator first = begin();
    iterator last = end();
    while(first != last){        // 遍历节点
        iterator next = first;
        ++next;
        if(*first == value) { erase(first); }        // 找到就删除
        first = next;
    }
}

unique 移除连续的相同的元素

template <class T, class Alloc>
void list<T, Alloc>::unique(){
    iterator first = begin();
    iterator last = end();
    if (first == last) return;        // 若是空链表则不操作
    iterator next = first;
    while (++first != last) {        // 遍历链表
        if (*first == *next) { erase(next); }        // 如果存在连续相同的元素则删除后面的元素
        else { first = next; }        // 若两个元素不相同则头指针后移
           next = first;
    }
}

transfer 迁移(非公开接口)

protected:
    void transfer(iterator position, iterator first, iterator last) {
        if (position != last) {
            (*(link_type((*last.node).prev))).next = position.node;
            (*(link_type((*fast.node).prev))).next = last.node;
            (*(link_type((*position.node).prev))).next = first.node;
            link_type tmp = link_type((*position.node).prev);
            (*position.node).prev = (*last.node).prev;
            (*last.node).prev = (*first.node).prev;
            (*first.node).prev = tmp;
        }
    }

image-20220416002203377

splice

// 将x接合与position,x不同于*this
public:
    void splice(iterator position, list& x){
        if(!x.empty()){
            transfer(position, x.begin(), x.end());
        }
    }

// 将i指向的元素接合与position,position 和 i须指向同一个list
public:
    void splice(iterator position, list&, iterator i){
        iterator j = i;
        ++j;
        if (position == i || position == j) return;
        transfer(position, i, j);
    }

// 将first和last内的元素接合与position,
void splice(iterator position, list&, iterator first, iterator last){
    if(first != last){
        transfer(position, first, last);
    }
}

merge

// 将x合并到*this身上,两个list要先经过递增排序
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x){
    iterator first1 = begin();
    iterator last1 = end();
    iterator first2 = x.begin();
    iterator last2 = x.end();
    
    whiel(first1 != last1 && first2 != last2){
        if(*first2 < *first1) {
            iterator next = first2;
            transfer(first1, first2, ++next);
            first2 = next;
        }
        else{
            ++first1;;
        }
        if (first2 != last2){
            transfer(last1, first2, last2);
        }
    }
}

reverse

template <class T, class Alloc>
void list<T, Alloc>::reverse() {
    if (node->next == node || link_type(node->next)->next == node) { return; }
    iterator first = begin();
    ++first;
    while (first != end()) {
        iterator old = first;
        ++first;
        transfer(begin(), old, first);
    }
}

deque

双向开口的连续线性空间

中控器

deque采用了一块所谓的map(一小段连续空间)作为主控,其中每个元素都是指针,指向一段缓冲区,该缓冲区才是deque存储的主题

template <class T, class Alloc=alloc, size_t Bufsize=0>
class deque{
public:
    typedef T type_value;
    typedef value_type* pointer;
    ...
protected:
    typedef pointer* map_pointer;
protected:
    map_pointer map;        // 指向map
    size_type map_size;        // map容纳指针数量
};

deque的迭代器必须能够指出缓冲区的位置,而且还要能够判断是否到达缓冲区的边界

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_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(BufSiz, sizeof(T)); }
    
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef size_t difference_type;
    typedef T** map_pointer;
    
    typedef __deque_iterator self;
    T* cur;        // 指向现行元素
    T* first;        // 指向缓冲区的头
    T* last;        // 指向缓冲区的尾
    map_pointer node;        // 指向管控中心
    ...
}

用来决定缓冲区大小的函数 buffer_size(),调用的是 __deque_buf_size()

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));
}

image-20220420161041848

在遇到缓冲区边缘的时候,会使用set_node() 跳过缓冲区

void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + deference_type(buffer_size());
}

重载运算

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 = n + (cur - 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(node + node_offset);        // 切换至正确节点
        cur = first + (offset - node_offset * difference_type(buffer_size()))
    }
    return *this;
}

self operator+(difference_type n) const {
    self tmp = *this;
    return tmp += n;        //调用operator+=
}

self operator-=(difference_type n) { return *this += -n; }    // 利用operator+=来完成

self operator-(difference_type n) const {
    self tmp = *this;
    return tmp -= n;        // 调用operator-=
}

reference operator[](difference_type n) const { return *(*this + n); }
bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
    return (node == x.node) ? (cur < x.cur) : (node < x.node);
}
数据结构

deque维护了一个map还维护了start指向第一个缓冲区的第一个元素的位置和finish指向最后一个缓冲区的最后一个元素的下一个位置,以及当前map的大小以便扩容

template <class T, class Alloc=alloc, class BufSiz=0>
class deque{
public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef size_t size_type;
public:
    typedef __deque_iterator<T, T&,T*, BufSiz> iterator;
protected:
    typedef pointer* map_pointer;
protected:
    iterator start;
    iterator finish;
    map_pointer map;
    size_type map_size;
ppublic:
    iterator begin() { return start; }
    iterator end() { return finish; }
    reference operator[](size_type n) {
        return start[difference_type (n)];
    }
    reference front() { return *start; }
    reference back() {
        iterator tmp = finish;
        --tmp;
        return *tmp;
    }
    size_type size() const { return finish - start;; }
    size_type max_size() const { return size_type(-1); }
    bool empty const { return start == finish; }
};
构造和内存管理

deque定义了两个专属的空间配置器

protected:
    typedef simple_alloc<value_type, Alloc> data_allocator        // 每次配置一个一个元素大小
    typedef simple_alloc<pointer, Alloc> map_allocator        //每次配置一个指针大小

deque提供了一个专属的constructor

deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0){
    fill_initialize(n, value);
}

fill_initialize() 用来产生并安排deque的结构

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(finish.first, finish.cur, value);
        }
        uninitialized_fill(finish.first, finish.cur, value);        // 最后一个节点不必设初值,因为尾端可能有空间
    }
    catch(...){
        ...
    }
}

create_map_and_nodes() 产生结构并安排

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_element){
    size_type num_nodes = num_elements / buffer_size() + 1;        // 需要的节点数
    map_size = max(initial_map_size(), num_nodes + 2);        // 一个map最少管理8个节点
    map = map_allocator::allocate(map_size);
    map_pointer nstart = map + (map_size - num_nodes) / 2;        // 令nstart和nfinish指向所有节点的中央区段
    map_pointer nfinish = nstart + num_nodes - 1;
    map_pointer cur;
    __STL_TRY{        // 为map内的现有节点分配缓冲区
        for(cur = nstart; cur <= nfinish; ++cur) { *cur = allocate_node(); }
    }
    catch(...){
        ...
    }
    start.set_node(nstart);
    finish.set_node(nfinish);
    start.cur = start.first;
    finish.cur = finish.first + num_elements % nuffer_size();
}

push_back

void push_back(const value_type& t){
    if(finish.cur != finish.last - 1){        // 如果缓冲区还有空间
        construct(finish.cur, t);        // 直接在备用空间上构造元素
        ++finish.cur;        // 调整缓冲区状态
    }
    else{        // 如果缓冲区没有空间了就转向下一个缓冲区
        push_back_aux(t);
    }
}

push_back_aux

template <class T, class Alloc, size_t BufSize>
voif deque<T, Alloc, BufSize>::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)));
}

push_front

public:
    void push_front(const value_type& t){
        if(start.cur != start.first){        //第一缓冲区有备用空间
            construct(start.cur - 1, t);        // 在当前备用空间上构造元素
            --start.cur;        // 调整第一缓冲区的状态
        }
        else{
            push_front_aux(t);        // 无备用空间则开辟
        }
    }

当第一缓冲区中没有备用空间调用 push_front_aux

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& 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(...){        // 若失败则全删除
        start.set_node(starrt.node + 1);
        start.cur = start.first;
        deallocate_node(*(start.node - 1));
        throw;
    }
}

map的重新整治,由 reserve_map_at_back() 和 reserve_map_at_front() 进行判断,实际由 reallocate_map()

void reserve_map_at_back(size_type nodes_to_add = 1){
    if(nodes_to_add + 1 > map_size - (finish.node - map)){        // map尾节点备用空间不足
        reallocate_map(nodes_to_add, false);        // 重新换一个map
    }
}

void reverse_map_at_front(size_type nodes_to_add = 1){
    if(nodes_to_add > start.node - map){        // map前端节点备用空间不足
        reallocate_map(nodes_to_add, true);        // 重新换一个map
    }
}

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add, bool add_at_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_mode){
        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 + ole_num_nodes); }
    }
    else{
        size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
        map_pointer new_map = map_allocator::allocate(new_map_size);        // 重新分配一块map
        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_nstart);        // 把原map拷贝过来
        map_allocator::deallocate(map, map_size);        // 释放原map
        map = new_map;        // 重新设置map的起始地址和大小
        map_size = new_map_size;
    }
    start.set_node(new_nstart);        // 重新设置迭代器start
    s=finish.set_node(new_nstart + old_num_nodes - 1);        // 重新设置迭代器finish
}
元素的操作

pop_back

void pop_bak() {
    if(finish != finish.first) {
        --finish.cur;        // 调整指针
        destroy(finish.cur);        // 析构元素
    }else{
        pop_back_aux();        // 释放缓冲区
    }
}

pop_back_aux

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_back_aux() {
    deallocate_node(finish.first);
    finish.set_node(finish.node - 1);
    finish.cur = finish.last - 1;
    destroy(finish.cur);
}

pop_front

void pop_front() {
    if(start.cur != start.last - 1){        // 如果第一缓冲区有元素
        destroy(start.cur);        // 将第一个元素析构掉
        ++start.cur;        // 调整指针
    }else{
        pop_print_aux();        // 如果第一缓冲区只有一个元素,把第一缓冲区释放
    }
}

pop_front_aux

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_front_aux() {
    destroy(start.cur);        // 将第一缓冲区的第一个元素析构
    deallocate_node(start.first);        // 将第一缓冲区释放
    start.set_node(start.node + 1);        // 调整start的状态
    start.cur = start.first;        //指向下一个缓冲区的第一个元素
}

clear

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::clear(){
    for(map_pointer node = start.node + 1; node < finish.node; ++node) {
        destroy(*node, *node + nuffer_size());        // 将元素析构
        data_allocator::deallocate(*node, buffer_size());        // 释放缓冲区
    }
    if(start.node != 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;        // 调整状态
}

erase

// 清除pos所指的元素
iterator 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 BufSize>
deque<T, Alloc, BufSize>::iterator deque<T, Alloc, BufSize>::erase(iterator first, iterator last){
    if(first == start && last == finish){        // 如果要清除的区间就是整个deque
        clear();        // 调用 clear
        return finish;
    }else{
        difference_type n = last -first;        // 清除区间的元素个数
        difference_typr 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 = finsh - 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;
    }
}

insert

iterator insert(iterator positoin, const value_type& x) {
    if(position.cur == staart.cur) {        // 如果插入的是deque的最前端
        push_front (x);        // 直接调用push_fornt
        return start;
    }else if(position.cur == finish.cur) {        // 如果插入在deque的最后端
        push_back(x);        // 直接调用push_back(x)
        iterator tmp = finish;
        --tmp;
        return tmp;
    }else{
        return insert_aux(positoin, x);        // 调用insert_aux
    }
}

template <class T, class Alloc, size_t BufSize>
typename deque<>T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::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 back2 = finish;        // 表示
        --back1;
        iterator back2 = back1;
        --back2;
        pos = start + index;
        copy_backward(pos, back2, back1);        // 移动元素
    }
    *pos = x_copy;        // 在插入点设置新值
    return pos;
}

stack

stack是一个先进后出的数据结构,只有一个口子

SGI STL以deque缺省或者list缺省来做为stack的底部实现,像stack这种底部使用别的容器来实现的被称为配接器(adapter)

stack没有迭代器

使用deque
template <class T, class Sequence = deque<T>>
class stack {
    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(); }
};

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 Sqquence>
bool operator<(const stack<T, Sequence>& x, cont stack<T, Sequence>& y){
    return x.c < y.c;
}

queue

queue是一种先进先出的数据结构,有两个出口,不允许遍历,和stack类似也是一种配接器,也没有迭代器

使用deque
template <class T, class Sequence = deque<T>>
class queue {
    friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue);
    friend bool operator< __STL_NULL_TMP_ARGS (const queue& x, const queue);
public:
    typedef typename Sequence::value_type value_type;
    typedef typename Sequence::size_typr size_typr;
    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) { 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 queu<T, Sequence>& x, const queue<T, Sequence>& y){
    return x.c < y.c;
}

heap

max_heap:每一个节点的值都大于等于子节点的值

min_heap:每一个节点的值都小于等于子节点的值

没有迭代器

算法

push_heap

template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
    __push_heap_aux(first, last, distance_type(first), value_type(first));
}

template <class RandomAccessIterator, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*) {
    __push_heap(first, Distance((last - first) - 1), Distance((last - first) -1), Distance(0), T(*(last - 1)));
}

template <calss RandomAccessIterator, class Distance, calss Distance, class T>
inline void __push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value){
    Distance parent = (holeIndex - 1) / 2;        // 找出父节点
    while (holeIndex > topIndex && *(first + parent) < value) {    // 如果没有达到顶端,且父节点比新的值小
        *(first + holeIndex) = *(first + parent);        // 将新的位置的值赋值为父节点的值
        holeIndex = parent;        // 调整新插入的位置为父节点
        parent = (holeIndex - 1) / 2;        // 插入位置的新父节点
    }
    *(first + holeIndex) = value;        // 将插入的值赋给插入的地方
}

image-20220425175707069

pop_heap

template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last){
    __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);        // 调整heap
}

template <class RandomAccessIterator, class Distance, class T>
void __adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value) {
    Distance topIndex = holeIndex;
    Distance topIndex = holeIndex;
    Distance seconChild = 2 * holeIndex + 2;        // 洞节点的右节点
    while (secondChild < len) {
        // 比较洞节点的左右两节点,然后以secondChild代表较大的节点
        if(*(first + secondChild) < *(first + (secondChild - 1))) { secondChild--; }
        *(first + holeIndex) = *(first + secondChile);
        // 令较大值为洞值,再令洞号下移至较大的节点处
        holeIndex = secondChile;
        secondChild = 2 * (secondChile + 1);
    }
    if(secondChile == len) {        // 如果只有左子节点
        *(fist + holeIndex) = *(first + (secondChild - 1));        // 将左子值赋给洞值
        holeIndex = secondChild - 1;        // 洞号下移至左子节点处
    }
    __push_heap(dirst, holeIndex, topIndex, value);
}

sort_heap

每次pop_heap都能获取最大的值,只要不断pop_heap就能得到一个排序好的

tamplate <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator) {
    while(last - first > 1){
        pop_heap(first, last--);
    }
}

make_heap: 将现有的数据转换为一个heap

template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
    __make_heap(first, last, value_type(first), distance_type(first));
}

template <class RandomAccessIterator>
void __make_heap(RandomAccessIterator first,
                 RandomAccessIterator last,
                 T*, Distance*){
    if(last - first < 2) return;        // 如果长度小于2,不用排列
    Distance len = last - first;
    Distance parent = (len - 2)/2;
    while(true) {
        __adjust_heap(first, parent, len, T(*(first + parent)));        // 重新排列以parent为首的子树
        if(parent == 0) return;        // 走完节点
        parent--;
    }
}

priority_queue

有一个权值的概念,元素被推入后按照权值排列,priority也是一种配接器,没有迭代器

template <calss 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 refrence;
    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);}
    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);
            c.pop_back();
        }
        __STL_UNWIND(c.clear());
    }
};

slist

slist提供了 insert_after 和 erase_after

slist不提供 push_back 只提供 push_back

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节点的下一个节点赋给new节点的下一个节点
    prev_node->next = new_node;        // 将new节点赋给prev节点的下一个节点
    return new_node;        // 返回new节点
}
// 单向链表的大小
inline size_type __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;
    __slist_iterator_base(__slist_node_base* x) : node(x) {}
    coid 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 __silist_iterator<T, T&, T*> iterator;
    typedef __slist_iterator<T, const T&, const T*> const_iterator;
    typedef __slist_iterator<T, 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->() consy { return &(operator*()); }
    
    self& operator++() {
        incr();
        return *this;
    }
    self operator++(int) {
        self tmp = *this;
        incr();
        return tmp;
    }
};
数据结构
template <class T, class Alloc = alloc>
class slist
{
public:
    typedef T value_type;
    typedef value* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;
    stpedef ptrdiff_t difference_type;
    
    typedef __slist_iterator<T, T&, T*> iterator;
    typedef __slist_iterator<T, const  T&, const T*> coonst_iterator;
private:
    typedef __slist_node<T> list_node;
    typedef __slizt_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);        // 清除空间
    }
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; }
    
    void swap(slist& L){        // 交换slist
        list_node_base* tmp = head.next;
        head.next = L.head.next;
        L.head.next = tmp;
    }
public:
    reference front() { return ((list_node*) head.next)->data; }
    void push_front(const value_type& x) {
        __slist_make_link(&head, create_node(x));
    }
    void pop_front() {
        list_node* node = (list_node*) head.next;
        head.next = node->next;
        destroy_node(node);
    }
};

RB-tree

是一个二叉搜索树且满足下面几个条件

  • 每个节点不是红色就是黑色
  • 根节点是黑色
  • 如果节点是红色则其子节点是黑色
  • 任何一个节点到树的尾端的任何一个路径,所包含的黑节点数必须相同
RB-tree的节点设置
typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false;        // 用0表示红
const __rb_tree_color_type __rb_tree_black = true;        // 用1表示黑

struct __rb_tree_node_base {
    typedef __rb_tree_color_type color_type;
    typedef __rb_tree_node_base* base_ptr;
    
    color_type color;        // 颜色
    base_ptr parent;        // 父节点
    base_ptr left;        // 左节点
    base_ptr right;        // 右节点
    
    static base_ptr minimum(base_ptr x) {
        while (x->left != 0) x = x->left;        // 一直往左走找到最小的
        return x;
    }
    
    static base_ptr maximum(base_ptr x) {        // 一直往右走找到最小的
        while (x->right = 0) x = x->right;
        return x;
    }
};
template <class Value>
struct __rb_true_node : __rb_true_node_base {
    typedef __rb_true_node<Value>* link_type;
    Value value_field;
}
RB-tree迭代器设置
// 基层迭代器
struct __rb_tree_base_iterator {
    typedef __rb_tree_node_base::base_ptr base_ptr;
    typedef bidirectional_iterator_tag iterator_category;
    typedef ptrdiff_t difference_type;
    base_ptr node;
    
    void increment() {
        if (node->right != 0) {
            node = node->right;        // 如果有右节点就走到右节点
            while (node->left != 0) { node = node->left; }        // 若左节点不为空,一直往左走下去
        }else {
            base_ptr y = node->parent;        // 如果没有右节点回溯到父节点
            while (node == y->right) {
                node = y;        // 如果本身是一个右节点就一直回溯父节点知道自身不是右节点
                y = y->parent;
            }
            if (node->right != y) { node = y; }
        }
    }
    
    void decrement() {
        // 如果是红节点并且父节点的父节点是本身,那么右节点就是答案
        if(node->clor == __rb_tree_red && node->parent->parent == node) { node = node->right; }
        else if(node->left != 0) {        // 如果有左节点
            base_ptr y = node->left;        // 把左节点赋给y
            while (y->right != 0) { y = y->right; }        // 如果右节点不为0就一直向右遍历
            node = y;        // 最后的就是答案
        }else {
            base_ptr y = node->parent;        // 把父节点给y
            while(node == y->left) {        // 如果y的左节点是node的话
                node = y;            // 往上走
                y = y->parent;
            }
            node = y;        // 此时的父节点就是答案
        }
    }
};
// 正规迭代器
template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator ; public __rb_tree_base_iterator {
    typedef Vlue value_type;
    typedef Ref reference;
    typedef Ptr pointer;
    typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
    typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
    typedef __rb_tree_iterator<Value, Ref, Ptr> self;
    typedef __rb_tree_node<Value>* link_type;
    
    __rb_tree_iterator() {}
    __rb_tree_iterator(link_type x) { node = x; }
    __rb_tree_iterator(const iterator& it) { node = it.node; }
    
    reference operator*() const { return link_type(node)->value_field; }
    #ifndef __SGI_STL_NO_ARROW_OPERATOR
        pointer operator-> const { return &(operator*()); }
    #endif
    
    self& operator++() { increment(); return *this; }
    self operator++(int) {
        self tmp = *this;
        increment();
        return tmp;
    }
    
    self& operator--() { decrement(); return *this; }
    self operator--() {
        self tmp = *this;
        decrement();
        return tmp;
    }
}
RB-tree的数据结构
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
protected:
    typedef void* void_pointer;
    typedef __rb_tree_node_base* base_ptr;
    typedef __rb_tree_node<Value> rb_tree_node;
    typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
    typedef __rb_tree_color_type color_type;
public:
    typedef Key Key_value;
    typedef Value value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef rb_tree_node* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
protected:
    link_type get_node() { return rb_tree_node_allocator::allocate(); }
    void put_node(link_type) { return rb_tree_node_allocator::deallocate(p); }
    
    link_type create_node(const value_type& x) {
        link_type tmp = get_node();        // 配置空间
        __STL_TRY {
            construct(&tmp->value_field, x);        // 构造内容
        }
        __STL_UNWIND(put_node(tmp));
        return tmp;
    }
    
    link_type clone_node(link_type x) {        // 复制节点
        link_type tmp = create_node(x->value_field);
        tmp->color = x->color;
        tmp->left = 0;
        tmp->right = 0;
        return tmp;
    }
    
    void destroy_node(link_type p) {
        destroy(&p->value_field);        // 析构内容
        put_node(p);        // 释放内存
    }
protected:
    size_type node_count;        // 节点数量
    link_type header;
    Compare key_compare;        // 键值大小比较准则
    
    // 取得header的成员
    link_type& root() const { return (link_type&) header->parent; }
    link_type& leftmost() const { return (link_type&) header->left; }
    link_type& rightmost() const { return (link_type&) header->right; }
    
    // 取得节点x的成员
    static link_type& left(link_type x) { return (link_type&)(x->left); }
    static link_type& right(link_type x) { return (link_type&)(x->right); }
    static link_type& parent(link_type x) { return (link_type&)(x->parent); }
    static reference value(link_type x) { return x->value_field; }
    static const Key& key(link_type x) { return KeyOfValue()(value(x)); }
    static color_type& color(link_type x) { return (color_type&)(x->color); }
    
    // 取得节点x的成员
    static link_type& left(base_ptr x) { return (link_type&)(x->left); }
    static link_type& right(base_ptr x) { return (link_type&)(x->right); }
    static link_type& parent(base_ptr x) { return (link_type&)(x->parent); }
    static reference value(base_ptr x) { return ((link_type)x)->value_field; }
    static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x))); }
    static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); }
    
    static link_type minimum(link_type x) {        // 取得最小值
        return (link_type) __rb_tree_node_base::minimum(x);
    }
    static link_type maximum(link_type x) {        // 取得最大值
        return (link_type) __rb_node_base::maximum(x);
    }
public:
    typedef __rb_tree_iterator<value_type, reference, pointer> iterator;
private:
    iteartor __insert(base_ptr x, base_ptr y, const value_type& v);
    link_type __copy(link_type x, link_type p);
    void __erase(link_type x);
    void init() {
        header = get_node();        // 产生一个节点
        color(header) = __rb_tree_red;        // 使得产生的节点为红色
        root() = 0;
        leftmost() = header;        // 令header的左节点为自己
        rightmost() = header;             // 令header的右节点为自己
    }
public:
    rb_tree(const Compare& comp = Compare()) : node_count(0), key_compare(comp) { init(); }
    ~rb_tree() { clear(); put_node(header);}
    rb_tree<Key, Value, KeyOfValue, Compare, Alloc>&
    operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x);
public:
    Compare key_comp() const { return key_compare; }
    iterator begin() { return leftmost(); }        // 起点为最左边节点
    iterator end() { return header; }        // 终点为header所指处
    bool empty() const { return node_count; }
    size_type size() const { return node_count; }
    size_type max_size() const { return size_type(-1); }
public:
    pair<iterator, bool> insert_unique(const value_type& x);    // 插入节点不允许重复
    iterator insert_equal(const value_type& x);        // 插入节点允许节点重复
};
RB-tree的构造和内存管理
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
protected:
    typedef __rb_tree_node<Value> rb_tree_node;
    typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
}

RB-tree的构造有两种方式,一种是

用现有的RB-tree复制,另一种是产生一棵空的

rb_tree(const Compare& comp = Compare()) : node_count(0), key_compare(comp) { init(); }

private:
    void init() {
        header = get_node();        // 产生一个节点空间
        color(header) = __rb_tree_red;        // 令header为红色
        root() = 0;
        leftmost() = header;        // header的左节点为自己
        rightmost() = header;        // header的右节点为自己
    }
RB-tree的元素操作

元素插入操作 insert_equal()

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const Value)
{
    link_type y = header;
    link_type x = root();        // 从根节点开始向下遍历
    while(x != 0) {
        y = x;
        x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);    // 遇大往左,遇小于等于往右
    }
    return __insert(x, y, v);        // 然后插入数据,x是插入点,y是父节点,v是插入数据
}

元素插入操作 insert_unique() 节点键值不允许重复

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v) {
    link_type y = header;
    link_type x = root();        // 从根节点开始
    bool comp = true;
    while (x != 0) {        // 从根节点开始向下寻找插入点
        y = x;
        comp = key_compare(KeyOfValue()(v), key(x));
        x = comp ? left(x) : right(x);        // 遇大向左,遇小于等于向右
    }
    iterator j = iterator(y);        // 令迭代器j指向插入点的父节点y
    if (comp) {        // 如果comp为真,表示遇到大的,插入左侧
        if (j == begin()) { return pair<iterator, bool>(__insert(x, y, v), true); }        // 如果左侧是最左节点
        else { --j; }        // 调整j
    }
    if (key_compare(key(j.node), KeyOfValue()(v))) {        // 遇到小的插入右侧
        return pair<iterator, bool>(__insert(x, y, v), true);
    }
    return pair<iterator, bool>(j, false);        // 重复不插入
}

真正的插入操作 __insert()

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iteartor
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__insert(base_ptr x_, base_ptr y_, const Value& v) {
    link_type x = (link_type) x_;
    link_type y = (link_type) y_;
    link_type z;
    if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) {
        z = create_node(v);        // 产生一个新的节点
        left(y) = z;
        if (y == header) {        // 使得当y为header时,leftmost()是z
            root() = x;
            rightmost() = z;
        }
        else if (y == leftmost()) { leftmost() = z; }        // 确保leftmost()永远指向最左节点
    }
    else {
        z = create_node(v);        // 产生一个新节点
        right(y) = z;        // 让新节点成为插入点的父节点y的右子节点
        if (y == rightmost()) { rightmost() = z; }        // rightmost()永远指向最右节点
    }
    parent(z) = y;        // 设置新节点的父节点
    left(z) = 0;        // 设置新节点的左子节点
    right(z) = 0;        // 设置新节点的有子节点
    __rb_tree_rebalance(z, header->parent);        // 设置新节点的颜色
    ++node_count;        // 节点数加一
    return iterator(z);        // 返回指向新节点的迭代器
}
调整RB-tree(旋转和改变颜色)

插入操作之后需要把RB-tree调整到符合RB-tree的状况