SGI stl

2019-11-07  本文已影响0人  镜中无我

第一章

1.9 令人困惑的语法

1.9.1 stl_config.h中的各种组态（configurations）

1.9.2 临时对象的产生与运用

template<class T>
class print{
public:
  void operator()(const T& elem){ cout<<elem<<' ';}
};
int main(){
  int ia[6]={0,1,2,3,4,5};
  vector<int> iv(ia,ia+6);
  //临时对象
  for_each(iv.begin(),iv.end(),print<int>());
}

1.9.3 静态常量整数成员在class内部直接初始化

1.9.4 ++/--/*操作符

1.9.5 前闭后开区间

template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f){
  for(;first!=last;++first)
     f(*first)
  return f;
}

1.9.6 function call操作符（operator（））

2 空间配置器

注意：这里的空间配置器包含内存和其他存储介质

2.1空间配置器的标准接口

数据成员：
成员函数

2.2 具备次配置力的SGI空间配置器

SGI STL的配置器是alloc而不是allocator，不接受任何参数。

2.2.1 SGI标准的空间配置器
2.2.2 SGI特殊的空间配置器（使用）std::alloc
2.2.3 构造和析构工具：construct()和destroy()
image.png

c++本身不支持对“指针所指之物”的类型判断，也不支持“对象的析构函数是否trivial”的判断，所以上述的两个接口很值得考究

2.2.4 空间的配置与释放 std::alloc
2.2.5 第一级配置器__malloc_alloc_template剖析

new-handler机制：

  1. 让更多内存可以被使用
  2. 安装另一个new-handler
  3. 卸除new-handler
  4. 抛出bad_alloc
  5. 不返回，调用abort或者exit
2.2.6 第二级配置器__default_alloc_template
image.png 
union obj{
  union obj* free_list_link;
  char client_data[1];//the client sees this
}
  • 使用union可以让指针和数据复用同一块内存区块，这种技巧在强类型语言中行不通,这种技巧的实质内涵是：当内存区块空闲时，我们用其保存指针变量，当区块被返回给用户时，区块的地址被用户态维护，区块改为存储数据。即在用户态和内核态分别维护不同的内容
  • 将bytes上调至8的倍数
    (((bytes)+7)&~7)
  • 将bytes计算空闲链表索引值
    (((bytes)+7)/7)
2.2.7 空间配置器
static void* allocate(size_t n){
    obj* volatile* my_free_list;
    obj* result;
    if(n>(size_t)__MAX_BYTES){
        return(malloc_alloc::allocate(n));//一级配置选项
        
    }
    my_free_list=free_list+FREELIST_INDEX(n);
    result=*my_free_list;
    if(result==0){
        void *r=refill(ROUND_UP(n));
        return r;
    }
    *my_free_list=result->free_list_link;
    return(result);
}

static void deallocate(void* p,size_t n){
    obj* q=(obj*)p;
    obj* volatile *my_free_list;
    if(n>(size_t)__MAX_BYTES){
        malloc_alloc::deallocate(p,n);
        return;
    }
    my_free_list=free_list+FREELIST_INDEX(n);
    q->free_list_link=*my_free_list;
    *my_free_list=q;
    
}
2.2.8 内存补充
template<bool threads,int inst>
void* __default_alloc_template<threads,inst>::refill(size_t n){
    int nobjs=20;//一次性分配20个对象的内存
    char* chunk=chunk_alloc(size_t n,nobjs);
    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++){
        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_link_list=next_obj;
        }
    }
    return (result);
    
}
2.2.9 内存池
template<bool threads,int inst>
char*
__default_alloc_template<threads,inst>::
chunk_alloc(size_t size,int& nobjs){//对象大小、对象个数
    char* result;
    size_t total_bytes=size*nobjs;
    size_t bytes_left=end_free-start_free;//left memory
    if(bytes_left>=total_bytes){//内存池足够分配20个对象
        result=start_free;
        start_free+=total_bytes;
        return (result);
    }else if(bytes_left>=size){//内存池足够分配一个以上的对象
        nobjs=bytes_left/size;
        total_bytes=size*nobjs;
        result=start_free;
        start_free+=total_bytes;
        return (result);
    }else{//内存池资源不足
        size_t bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4);//新水量的大小为需求的两倍再加上一个随着配置次数增加愈来愈大的附加量
        if(bytes_left>0){
            obj* volatile* my_free_list=free_list+FREELIST_INDEX(bytes_left);
            ((obj*)start_free)->free_list_link=*my_free_list;
            *my_free_list=(obj*)start_free;
        }
        start_free=(char*)malloc(bytes_to_get);
        if(0==start_free){
            int i;
            obj *volatile* my_free_list,*p;
//系统堆资源不够，需要从freelists较大的对象中检索，看有没有内存可用 for(i=size;i<=__MAX_BYTES;i+=__ALIGN){
                my_free_list=free_list+FREELIST_INDEX(i);
                p=*my_free_list;
                if(0!=p){
                    *my_free_list=p->free_list_link;
                    start_free=(char*)p;
                    end_free=start_free+i;
                    return (chunk_alloc(size,nobjs))
                }
            }
            end_free=0;
//调用第一级配置器，第一级处理器有out-of-memory处理机制
            start_free=(char*)malloc_alloc::allocate(bytes_to_get);
        }
        heap_size+=bytes_to_get;
        end_free=start_free_bytes_to_get;
        return (chunk_alloc(size,obj));
    }
}

2.3 内存基本处理工具

stl定义了5个全局函数作用于未初始化的空间上，前两个对应于构造和析构函数、另外三个函数unintialized_copy()、uninitialized_fill()、uninitialized_fill_n(()分别对应于高层次函数copy()、fill()、fill_n().

2.3.1 函数语义简介
  1. 配置内存区块，足以包含范围内的所有元素；
  2. 使用这个函数构造元素。
2.3.2 函数实现
\\uninitialized_fill_n
template <class ForwardIterator,class Size,class T>
inline ForwordIterator uninitialized_fill_n(ForwordIterator first,size n,const T&x){
    return __uninitialized_fill_n(first,n,x,value_type(first));
}
template <class ForwardIterator,class Size,class T,class T1>
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first,Size n,const T&x,T1*){
    typedef typename __type_traits<T1>::is_POD_type is_POD;
    return __uninitialized_fill_n_aux(first,n,x,is_POD());
    
}

template <class ForwardIterator,class Size,class T>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first,Size n,const T& x,__true_type){
    return fill_n(first,n,x);//高阶库,这个是处理c struct以及简单数据类型用的，也就是POD数据类型
}

template <class ForwardIterator,class Size,class T>
ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n, const T & x, __false_type){
    ForwardIterator cur=first;
    for(;n>0;--n,++cur) 
        construct(&*cur,x);
    return cur;
}
\\uninitialized_copy和uninitialized_fill;
\\大部分和上述做法一样，不过处理char*和wchar_t*两种类型时，采用了最具效率的memmove内存直接存取
\\注意返回的是end
\\memmove的特殊性在于其可以用来处理处理内存重叠的问题 ，而memcpy不可以\ \ end \ \ mem void * memmove(void * dest, const void * src, size_t count)
void *memmove(void *dest,const void *src,size_t count)
{
    char *ret=(char *)dest;
    char *dest_t=dest;
    char *src_t=(char *)src;
    assert( NULL !=src && NULL !=dest);
    //或者改为dest-src>=count
    if (dest_t<=src_t || dest_t>=src_t+count)
    {
        while(count--)
        {
            *dest_t++ = *src_t++;
        }
    }
    else
    {
        dest_t+=count-1;
        src_t+=count-1;
        while(count--)
        {
            *dest_t--=*src_t--;
        }
    }
    return ret;
}
\\“新的指针指向已经分配的内存”就会出现内存重叠问题，有时候这会出现

第三章 迭代器的概念与traits的编程技巧

3.1 迭代器设计思维——stl关键所在

迭代器模式定义：提供一种方法，使之能够寻访某个聚合物所含的各个元素，而又无需暴露该聚合物的内部表达式。在stl中，它将容器和算法分开，彼此独立设计，容器和算法的泛型化并不难，关键是如何设计良好的胶着剂，也就是设计出可以泛用而又能反映容器自身特性的迭代器，不能过于依赖，又不能过于平庸。

3.2 迭代器是一种smart pointer

3.3 迭代器相应类型

Traits编程技巧—STL源代码门钥

template <class T>
struct MyIter{
    typedef T value_type;
    T* ptr;
    MyIter(T* p=nullptr):ptr(p){}
    T& operator*()const{
        return *ptr;
    }
}

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

存在问题：原生指针不是class type，所以无法定义其内嵌型

template<class I>
struct iterator_traits{
  typedef typename I::value_type value_type;
}
template <class I>
typename iterator_traits<I>::value_type
func(I ite){return *ite;}
//进一步
template<class I>
struct iterator_traits<I*>{
  typedef I value_type;//特化为原生指针
}
//引用
iterator_traits<const int*>::value_type
//进一步：从pointer-to-const中萃取出non-const
template<class T>
struct iterator_traits<const T*>{
  typedef T value_type;
}

template<class T>
struct iterator_traits{
  typedef typename I::iterator_category iterator_category;
  typedef typename I::value_type value_type;  //迭代器所指对象的类型
  typedef typename I::difference_type difference_type;//迭代器之间的距离
  typedef typename I::pointer pointer;//
  typedef typename I::reference reference;
};
//设计举例，对于每一个iterator都应该设置它的萃取机，迭代器类型为I，对于原生指针需要做一些偏特化
//以difference_type型别，count算法为例
template <class I,class T>
typename iterator_traits<I>::difference_type   count(I first,I last,const T& value){
  typename iterator_traits<I>::difference_type n=0;
for(;first!=last;++first)
  if(*first==value) ++n;
return n;
}
//以referenc_type和pointer_type这两个的完整设计为例
template <class I>
struct iterator_traits{//普通iterator版本
  ...
  typedef typename I::pointer pointer;
  typedef typename I::reference reference;
  ...
};
template<class T>
struct iterator_traits<T*>{//原生指针的偏特化
  ...
  typedef T* pointer;
  typedef T& reference;  
  ...
};
struct iterator_traits<const T*>{
  ...
  typedef const T* pointer;
  typedef const T& referencde;
  ...
 };

3.5 std::iterator的保证

为了符合规范，任何迭代器都应该提供五个内嵌相应型别。STL提供一个iterators class如下，如果每个设计的迭代器都继承自它：

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;
};
//iterator class不含任何成员，所以继承不会带来额外的开销

template<class Item>
struct ListIter: public std::iterator<std::forward_iterator_tag,Item>
{...}

3.6 iterator源代码完整重列：

//<stl_iterator.h>
struct input_iterator_tag {};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct random_access_iterator_tag:public bidirectional_iterator_tag{};
//自己开发的迭代器应该继承这个类
template <class Category,class T,class Distance=ptrdiff_t,class Pointer=T*,class Reference=T&>
struct iterator{
        ...
}
//traits
template<class Iterator>
struct iterator_traits{
    ...
    内嵌声明
}
//原生指针的traits
template<class T>
struct iterator_traits<T*>{
    ...
}
//pointer-to-cosnt
template<class T>
struct iterator_traits<const T*>{
    ...
}
//函数，决定迭代器的类型
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&){
    typedef typename iterator_traits<Iterator>::iterator_category category;
    return category();
}
//...还有其他四种型别
/**********省略*********/
//distance函数
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
__distance(InputIterator first,InputIterator last,input_iterator_tag){
    iterator_traits<InputIterator>::difference_type n=0;
    while(first!=last){
        ++first;
        ++n;
    }
    return n;
}

template <class RandomAcessIterator>
inline iterator_traits<RandomAcessIterator>::difference_type
__distance(RandomAcessIterator first,RandomAcessIterator last,random_access_iterator_tag){
    return last-first;
}
//distance(InputIterator first,InputIterator last){... return __distance(first,last,category());}
//可见最后一个参数是用来重载的
//advance函数

3.7 SGI STL的私房菜：__type_traits

traits被进一步运用在迭代器以外的世界里面，于是就有了所谓的__type_traits。

双底线前缀词意指这是SGI STL内部所用的东西，不在STL之内
iterator_traits负责萃取迭代器的特性，__type_traits则负责萃取型别的特性。此时我们关注的型别特性是指是否具备non-trivial default ctor、copy ctor、assignment operator、dtor？如果答案是否定的，我们在对这个型别执行上述操作时就可以采用最有效率的措施，如malloc、memmove等。对于大规模而操作频繁的容器有着显著的效率提升

__type_traits<T>::has_trivial_default_constructor
__type_traits<T>::has_trivial_copy_constructor
__type_traits<T>::has_trivial_assignment_operator
__type_traits<T>::has_trivial_destructor
__type_traits<T>::is_POD_type
//使用真假性质的对象来标志他们
struct __true_type{};
struct __false_type{};
//template <class type>
struct __type_traits{
  typedef __true_type this_dummy_member_must_be_first;
  typedef __false_type ...;
  ...
  1. 一般具体化，保守值
  2. 经过声明的特化版本
  3. 某些编译器会自动为所有型别提供适当的特化版本

4 容器

image.png

4.1 vector

所谓序列式容器，其中元素可序，但是未必有序。

4.1.1 vector概述
4.1.2 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 diffrence_type;
protected:
  typedef simple_alloc<vlaue_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=allocate_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-begin());
  }
  bool empty()const {
    return begin()==end();
  }
  reference operator[](size_type n){
     return *(begin()+n);
  }
        vector():start(0),finish(0),end_of_storage(0){}
  vector(size_type n,const T& value){
     fill_initialisze(n,value);  
}
  vector(long n,const T& value){
     fill_initialisze(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(){
    if(finish!=end_of_storage){
      construct(finish,x);
      finish++;
    } else{
      insert_aux(end(),x);
    }
}
  void pop_back();
  iterator erase(iterator position){
    if(position+1!=end())
      copy(position+1,finish,position);
    --finish;
    destroy(finish);
    return position;
  }
  void resize(size_type new_size,const T& x){
    if(new_size<size())
      erase(begin()+new_size(),end());
     else
      insert(end(),new_size-size(),x);
  }
  void 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){
    uninitialized_fill_n(result,n,x);
    return result;
  }
4.1.3 vector的迭代器
4.1.4 vector的构造与内存管理：constructor，push_back
4.1.5 vector的元素操作：pop_back(),erase,clear,insert
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);//,这是一个全局函数，为什么不能直接用最后一个元素与当前元素交换？为了保护顺序性
}

insert操作

image.png
image.png
image.png
代码 
template<class T,class Alloc>
void vector<T,Alloc>::insert(iterator position,size_type n,const T& x)
{
  if(n!=0){
    if(size_type(end_of_storage-finish)>=n){
      T x_copy=x;
      const size_type elems_after=finish-position;
      iterator old_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{
        uninitialized_fill_n(finish,n-elems_after,x_copy);
        finish+=elems-after;
        uninitialized_copy(position,old_finish,finish);
        finish+=elems_after;
        fill(position,old_finish,x_copy);
      }
     }else{
        const size_type old_size=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_copy(position,finish,new_finish);

        }
        #ifdef __STL_USE_EXCEPTIONS
        catch(...){
            destroy(new_start,new_finish);
            data_allocator::deallocate(new_start,len);
        throw;
        }
        #endif
        destroy(new_start,new_finish);
        deallocate();
        start=new_start;
        finish=new_finish;
        end_of_storage=new_start+len;
      }
   }
 }

4.2 list概述

4.2.1 list概述
4.2.2 list的节点
template<class T>
struct __list_node{
  typedef void* void_pointer;
  void_pointer prev;
  void_pointer next;
  T data;
};
4.2.3 list的迭代器
4.2.4 list的数据结构
4.2.5 list的构造和内存管理constructor、push_back、insert
iterator insert(iterator position, const T& x){
   //插入的元素是构造在当前位置的前面
   tmp->next=position.node;
   tmp->prev=position.node->prev;
   (link_type(position.node->prev))->next=tmp;
  position.node->prev=tmp;
  return tmp;
}

插入完成之后新节点位于哨兵迭代器所指节点的前方，这是对于插入操作的标准规范

void transfer(iterator position, iterator first,iterator last){
  if(position!=last){
    (*link_type((*last.node).prev))).next=position.node;
    (*link_type((*first.node).prev))).next=last.node;
    link_type tmp=link_type((*position.node).prev);
    (*position.node).prev=(*last.node).prev;
    (*first.node).prev=tmp;
   }
}
  • void splice(iterator,list&);
  • void splice(iterator,list&,iterator);
  • void splice(iterator,list&,iterator,iterator);
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();
    while(first1!=last1&&frist2!=last2){
        if(*first2<*first1){
            iterator next=first2;
            transfer(first1,first2,++next);
        first2=next;
        }else{
            ++first1;
        }
        if(first2!=last2) 
            transfer(last1,first2,last2);
        
    }
}
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);
    }
}
//本函数采用归并排序，为了避免每次寻找分割点，使用中间链表来保存有序元素，其中每一个链表保存归并相应下标层数的所有有序元素，有效的实现用空间换时间的效果
template<class T,class Alloc>
void list<T,Alloc>::sort(){
    if(node->next==node||link_type(node->next)->next==node){
        return;
    }
    list<T,Alloc> carry;
    list<T,Alloc> counter[64];//用于存放中间元素，存放元素的数量和下标有关
    int fill=0;
    while(!empty()){
        carry.splice(carry.begin(),*this,begin()));//每一次取一个元素
        int i=0;
        //一步一步合并直至合并完成
        while(i<fill&&!counter[i].empty()){
            //必须递增排序
            counter[i].merge(carry);//counter用于存储归
            carry.swap(counter[i++]);//完全置换，置换过后，counter[i]为空，carry为前n个元素
        }
        carry.swap(counter[i]);//这一步过后，carry为空，counter[fill]保存有序元素
        if(i==fill) ++fill;
        
    }
    for(int i=1;i<fill;++i){
        counter[i].merge(counter[i-1])；
    }
    swap(counter[fill-1]);
}

list不能使用STL算法的sort，必须使用自己的member function，因为STL只接受RandomAccessIterator
注意这里的sort的实现，使用归并的方法实现排序，由于swap是直接操作指针，不存在复制元素的代价，所以时间复杂度为O(1),算法总的时间复杂度为O(nlogn)。该算法是链表排序的一个经典实现，思想是使用二进制进位

4.3 deque

4.3.1 deque的概述

个人理解：这里的连续指的是逻辑连续，即可以使用random access iterator

deque是动态的组织分段连续空间，随时可以增加一段新的空间并链接起来，所以不会像vector那样更新复制原始空间。
references：
{STL源码剖析简体中文完整版](https://www.linuxidc.com/Linux/2016-04/129761.htm)

4.3.2 deque的中控器（map）
template<class T, class Alloc=alloc,size_t BufSiz=0>
class deque{
public:
  typedef T value_type'
  typedef value_type* pointer;
...
protected:
  typedef pointer* map_pointer;
protected:
  map_pointer map;
  size_type map_size;
...
}
4.3.3 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));}
  //未继承自std::iterator，所以必须撰写五个必要的迭代器型别
  typedef random_access_iterator_tag iterator_category;//(1)
  typedef T value_type;//(2)
  typedef Ptr pointer;//(3);
  typedef Ref reference;//(4);
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;//(5)
  typedef __deque_iterator self;
  //保持与容器的连接
  T* cur;//当前元素
  T* first;//迭代器所指缓冲区的头
  T* last;//迭代器所指缓冲区的尾,注意这里和vector的last是一样的，都是最后一个空元素
  map_pointer node;//指向管控中心中当前缓冲区的地址存放的地方
}

void set_node(map_pointer new_node){
  node=new_node;
  first=*new_node;
  last=first+difference_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+=(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;
}
self& operator-=(difference_type n){return *this+=-n;}
self operator-(difference_type n) const{
  self tmp=*this;
  return tmp-=n;
}
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);
}
4.3.4 deque的数据结构
4.3.5 deque的构造和内存管理
deque(int n, const value_type& value): start(), finish(), map(0), map_size(0)
{
  fill_initialize(n, value);
}
// the definition of fill_initialize
template<class T, class Alloc, size_t BufSiz>
void deque<T, Alloc, BufSiz>::fill_initialize(size_type n, const value_type& value){
  create_map_and_nodes(n);
  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(...){
    ...
  }
  start.set_node(nstart);
  finish.set_node(nfinish);
  start.cur=start.first;
  finish.cur=finish.first+num_elements%buffer_size();
}
4.3.6 deque的元素操作
if(finish.cur!=finish.first){
  --finish.cur;
  destroy(finish.cur);
}else
  pop_back_aux();

//释放最后一个缓冲区
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.cur=finish.last-1;
  destroy(finish.cur);
}

//根据当前节点前后元素的多少决定向前移动还是往后移
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;
}
iterator 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;//标记deque的新起点
      destroy(start,new_start);//移动完毕，将冗余的元素析构
      //释放冗余的缓冲区
      for(map_iterator cur=start.node;cur<new_start.node;++cur)
        data_allocator::deallocate(*cur, before_size());
      start=new_start;
    }else{//前移后方元素
      ...
    }
  }
}

4.5 stack和queue

stack以底部容器完成所有工作，并且封装相关接口，实现新的存取机制，这是一种适配器。

4.6 heap

4.6.1 heap概述

小技巧：为了使得父节点和子节点之间有较为简单的对应关系，我们保留第一个元素，就是#0，这样父节点的下标就等于子节点下标左移一位

4.6.2 heap算法

4.7 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;
...
protected:
  Sequence c;
  Compare comp;
public:
  priority_queue():c(){}
  explicit priority_queue(const Compare& x): c(), comp(x){}
  priority_queue(InputIterator first, InputIterator last, const Compare& x)
    :c(first,last) { make_heap(c.begin(),c.end(),comp);}
  ...
}

4.8 slist（单向链表）

略

5. 关联式容器

关联式容器主要包括基于红黑树的有序set和map，以及基于hashtable的unordered_set和unordered_map.

5.1 树的概览

树在计算机科学里面是一种别广泛运行的数据结构。其中操作系统会将文件的索引节点和内容存放在树状结构里面；进程的内存区被维护在树状结构里面，用于快速定位；编译器会使用树来构建语法结构；文件压缩使用的huffman算法也需要维护一棵编码树；数据库的索引也是基于一种特殊的多节点B/B+树。在本章中主要介绍一种特殊的平衡树——红黑树，这是一种高度不超过2log(n+1)，折衷的平衡树方案。

5.2 红黑树

5.2.1红黑树的性质

满足上述四条规则的树就是一棵高度不大于2log(n+1)的平衡树，所以任何对该树的操作都必须维护这四条规则。

5.2.2 红黑树的插入

根据规则4，新增节点必须为红色；根据规则3，新增节点的父节点必须为黑色。新节点的插入未能满足这两条规则时，就必须调整颜色并旋转树形。
假设：
新节点X；
父节点P；
祖父节点G；
叔节点S；
曾祖父节点GG；

根据X的插入位置和外围节点S，GG的颜色，有以下四种情况：

5.2.3 一个自上而下的程序

为了避免遇到状况4中持续向上形成处理时效上的瓶颈，我们可以施行一个自上而下的的程序：
新增节点为A，延着A的路径，将所有子节点都为红色的节点改为红色，子节点改为黑色。如果当前的父节点P也为红色，就像状况1一样做一次单旋转并修改颜色，或者像状况2一样做一次双旋转并修改颜色
在此之后，新节点的插入就简单了：要么直接插入，要么插入后做一次单旋转

5.2.4 RB-tree的迭代器
image.png
5.2.5 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_type;
    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 p){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(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;
    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;}
    ...
    static link_type minimum(link_type x){return (link_type)__rb_tree_node_base::minimum(x);}
    ...

public:
    typedef __rb_tree_iterator<value_type,reference,pointer> iterator;
private:
    iterator __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;
        rightmost()=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:
    pair<iterator,bool> insert_unique(const value_type&x);
    iterator insert_equal(const value_type& x);
    ...
};
5.2.6 RB_tree的构造和内存管理
5.2.7 RB_tree的操作（插入）

本节涉及红黑树的插入操作，在第一节中已经介绍 ，在这里不做赘述

5.3 set

5.4 map

5.5 hashtable

如何在一定场景下实现常数时间的插入，删除，搜寻等操作，关于这个问题，哈希给出了较好的回答

5.5.1 为什么用hash？
5.5.2 hashtable的桶子和节点
typedef struct __hashtable_node{
  __hashtable_node* next;
  Value val;
}node;

vector<node* ,Alloc> buckets;
5.5.7 hash functions

6. 算法

6.1 STL算法简述

每一个STL算法都需要传入一个由迭代器控制的容器区间。传入迭代器的类型由算法本身对于元素操作方式所决定，高级别的迭代器可以被传入要求低级别迭代器的算法，反之则无效，然而即时无效该错误也无法在编译器检测出来，因为在泛型函数中，迭代器类型是一种型别参数，而不是真实的类型可以被编译期类型检查机制检测出来。
另外算法本身有时候对一些微小的变化实行更加细粒度的动态控制，比如算法中比较函数的行为控制，它会允许用户传入一个自定义仿函数，以便采用其他控制策略。所有的数值算法在包含在头文件<numeric>中，其他的算法包含在<algorithm>

6.2 算法的泛化过程

算法泛化的一个重要目标是：如何在原算法框架基础上，毫无压力的加入新的算法得以操作的类型，而不会出现兼容性问题，也就是隔离数据结构本身。
STL采取的方法：将算法操作的实体抽象出来，即用不同的迭代器来表示容器对象的型别差异，然而这种差异又尽在掌握之中，因为我们往往只需要以某种方式操作容器的元素以及对操作行为本身的行为加以控制即可，而不需要真正去洞察容器内部的结构和底层 的实现，这样的泛化就于是只关注迭代器的型别以及定义在迭代器上共通的一组操作。

注意按值传递、按引用转递、按常引用传递三者的开销和使用场景

  • 按值传递：整体拷贝一份临时对象用于函数内部使用，对实参没有影响，内置类型参数传递且不该变参数本身的情况下使用
  • 按引用传递：传递一个对象的别名，对用户而言等同于对象本身，内部是使用地址引用工作的，适用于大对象且需要改变对象本身的时候
  • 按常引用传递：大对象且不需要改变内容的时候，可以避免临时对象拷贝造成的开销

6.3 序列容器算法实例

6.3.1 power
template <class T, class Integer, class MonoidOperation>
T power(T x, Integer n, MonoidOperation op){
  if(n==0)
    return identity_element();
  else{
    while((n&1)==0){
      n>>=1;
      x=op(x,x);
    }
    T result=x;
    n>>=1;
    while(n!=0){
      x=op(x,x);
      if((n&1)==0)
        result=op(result,x);
      n>>=1;
    }
    return result;
  }
}
iter_swap

iter_swap使用了迭代器的value type，使用以下语句即可定义一个临时变量
typename iterator_traits<ForwardIterator1>::value_type tmp=*a

copy
STL的copy算法的完整脉络

如果输入区间和输出区间重叠，赋值顺序需要多加讨论，result位于[first,last）之内时，我们需要使用copy_backward()，反之我们不用在意。

__STL_TEMPLATE_NULL struct __type_traits<C>{
  typedef __false_type has_trivial_default_constructor;
  typedef __true_type  has_trivial_copy_contructor;
  typedef __true_type   has_trivial_assignment_operator;
  typedef __true_type has_trivial_destructor;
  typedef __false_type is_POD_type;
}

6.4 set 相关算法

set在stl里面默认是使用红黑树实现，是有序的。本节介绍的四个算法是在有序基础上实现的

6.4.1 set_union并集
  1. 比较当前元素，谁小谁赋给输出集，并前进一个，知道其中一个为空
  2. 将两个区间分别往结果集中复制（空集自然不会复制）
6.4.2 set_intersection

具体实现和并集很像，只要在相等时赋值即可

6.4.3 set_difference差集

具体实现和上述算法很像，只需要在小于时赋值即可

6.4.4. symmetric_difference

具体实现和上述算法很像，只是在非等于的时候赋值即可

6.5 其他算法

merge
template<class InputIterator1, class InputIterator2,class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator results,Compare cmp ){
  while(first!=last1&&first2!=last2){
    if(cmp(*first2,*first1){
      *result=*first2;
      ++first2;
    }else{
      *result=*first1;
      first1++;
    }      
     ++result;
  }
return copy(first2,last2,copy(first1,last1,result));
}
partition
template <class BidirectionalIterator,class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
                                    BidirectionalIterator last,
                                    Predicate pred){
    while(true){
        while(true)
            if(first==last)
                return first;
            else if (pred(*first))//判断数值是否为偶数
                ++first;
            else
                break;
        --last;
        while(true)
            if(first==last)
                return first;
            else if(!pred(*first))
                --last;
            else
                break;
        iter_swap(first,last)
        ++first;
    }
}
reverse_hsy和rotate——针对forward的算法
template<class ForwardIterator>
inline void reverse_hsy(ForwardIterator first,ForwardIteraor last){
    ForwardIterator ret=first;
    first++;
    while(first!=last){
        ret->next=first->next;
        first->next=ret;
        ret=first++;
    }
    first=ret;
}

template<class ForwardIterator>
inline void rotate(ForwardIterator first,ForwardIterator middle,ForwardIterator last){
    if(first==middle||middle==last) return;
    __rotate(ForwardIterator first,ForwardIterator middle,ForwardIterator last,distance_type(first),iterator_category(first));

}
template <class ForwardIterator,class Distance>
void __rotate(ForwardIterator first,ForwardIterator middle,ForwardIterator last,Distance*,forward_iterator_tag){
    for(ForwardIterator i=middle;;){
        iter_swap(first++,i++);
        if(first==middle){
            if(i==last) return;
            middle=i;
        }else if(i==last)
            i=middle;
    }
}

template <class BidirectionalIterator,class Distance>
void __rotate(BidirectionalIterator first,
            BidirectionalIterator middle,
            BidirectionalIterator last,
            Distance*,
            bidirectional_iterator_tag){
        reverse(first,middle);
        reverse(middle,last);
        reverse(first,last);
}

template <class RandomAccessIterator,class Distance>
void __rotate(RandomAccessIterator first,
            RandomAccessIterator middle,
            RandomAccessIterator last,
            Distance*,
            random_access_iterator_tag){
    Distance n=__gcd(last-first,middle-first);
    while(n--)
        __rotate_cycle(first,last,first+n,middle-first,value_type(first));
}

template <class EuclideanRingElement>
EuclideanRingElement __gcd(EuclideanRingElement m,EuclideanRIngElement n){
    while(n){
        EuclideanRingElement t=m%n;
        m=n;
        n=t;
    }
    return m;
}
lower_bound(运用于有序区间)

作用：从左到右返回第一个“不小于value”的元素，如果value大于[first，last]内的任意一个元素，则返回last。

template <class ForwardIterator,class T,class Distance>
ForwardIterator __lower_bound(ForwardIterator first,
                            ForwardIterator last,
                            const T& value,
                            Distance*,
                            forward_iterator_tag){

    Distance len=0;
    distance(first,last,len);
    Distance half;
    ForwardIterator middle;
    while(len>0){
        half = len>>1;
        middle=first;
        advance(middle,half);
        if(*middle<value){//对于upper_bound这里改为小于或等于
            first=middle;
            ++first;
        l   len=len-half-1;
        
        }else
            len=half;
    }
    return first;
}

template<class RandomAccessIterator,class T,class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,
                                RandomAccessIterator last,
                                const T& value,
                                Distance*,
                                random_access_iterator_tag){
    Distance len=last-first;
    Distance half;
    RandomAccessIterator middle;
    while(len>0){
        half=len>>1;
        middle=first+half;
        if(*middle<value){//对于upper_bound这里改为大于或等于
            first=middle+1;
            len=len-half-1;
            
        }else{
            len=half;
        }
    }
    return first;
}
二分查找

这里的二分查找是基于lower_bound的
关键判断

ForwardIterator i=lower_bound(first,last,value);
return i!=last&&!(value<*i);//或者改为return i!=last&&!comp(value, *i);
next_permulation
template<class BidirectionalIterator>
    inline bool next_permutation(BidirectionalIterator first,BidirectionalIterator last){
        if(first==last) return false;
        BidirectionalIterator i=last,j=last;
        i--;
        if(i==first) return false;
        while(*--i>=*--j){//从后往前,找到递增的两个数，如果是prev_permulation 这里改为大于或等于
            if(i==first) {//当前为最大排列
                reverse(first,last);//获取最小排列
                return false;
            }
        }
        reverse(j,last);//翻转当前位置往后的所有元素
        iter_swap(i,lower_bound(j,last,*i+1));
        return true;
    }

排序

template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first,
                    RandomAccessIterator last){

    if(first==last) return;
    for(RandomAccessIterator i=first+1;i!=last;++i){
        __linear_insert(first,i,value_type(first));//子区间插入
    }
}

template<class RandomAccessIterator,class T>
inline void __linear_insert(RandomAccessIterator first,
                            RandomAccessIterator last,T*){
    T value=*last;
    if(value<*first){
        copy_backward(first,last,last+1);//如果要插入的元素比当前元素小，则直接将所有元素后移一个单位，并在头部插入该元素
        
        *first=value;
    }else{
        __unguarded_linear_insert(last,value);//子区间检索并插入
    }
}

template<class RandomAccessIterator,class T>
inline void __unguard_linear_insert(RandomAccessIterator last,T value){
    RandomAccessIterator next=last;
    --next;
    while(value<next*){//从后往前检索，第一个元素已经比较过，所有不用再考虑边界问题
        *last=*next;
        last=next--;
    }
    *last=value;
}

//SGI STL sort
template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first,RandomAccessIterator last){
    if(first!=last){
        __introsort_loop(first,last,value_type(first),__lg(last-first)*2);
        __final_insertion_sort(first,last);//对于快速排序分割出来的元素进行排序
    }
}

template <class Size>
inline Size __lg(Size n){
    Size k;
    for(k=0;n>1;n>>=1)
        ++k;
    return k;
    
}
const int __stl_threshold=16;

template <class RandomAccessIterator,class T>

RandomAccessIterator __unguard_partition(RandomAccessIterator first,
                                                RandomAccessIterator last,T pivot){

    while(true){
        while(*first<pivot) --first;
        last--;
        while(*last>=pivot) --last;
        if(first>=last) return first;
        iter_swap(first,last);
        ++first;
    }
}


template <class RandomAccessIterator,class T,class Size>
void __introsort_loop(RandomAccessIterator first,
                    RandomAccessIterator last, T*,Size depth_limit){
    while(last-first>_stl_threshold){
        if(depth_limit==0){
            partial_sort(first,last,last);//这里防止分割恶化，当分割次数过多时采用堆排序改善情况
            return;
        }
        --depth_limit;
        RandomAccessIterator cut=__unguard_partition(first,last,T(__median(*first,*(first+(last-first)>>1),*(last-1))));
        __introsort_loop(cut,last,value_type(first),depth_limit);
        last=cut;//右边处理完了再来处理左边
    }
}

template<class RandomAccessIterator>
void __unguard_insertion_sort(RandomAccessIterator first,RandomAccessIterator last){
    __unguard_insertion_sort_aux(first, last, value_type(first));
}

template<class RandomAccessIterator,class T>
void __unguard_insertion_sort_aux(RandomAccessIterator first,RandomAccessIterator last,T*){
    for(RandomAccessIterator it=first;it!=last;++it)
        __unguard_linear_insert(it, T(*it));
}

template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first,RandomAccessIterator last){
    if(last-first>__stl_threshold){
        __insertion_sort(first,first+__stl_threshold);//insertion sort
        __unguard_insertion_sort(first+__stl_threshold,last);//后续元素一个一个插入即可，注意这里是将这个区间内的每一个元素针对整个大区间做一次插入排序

    }else{
        __insertion_sort(first,last);
    }
}

以上排序过程分为三个步骤

equal_range（找到某个值可插入的区间）
emplate <class RandomAccessIterator,class T,class Distance>
pair<RandomAccessIterator,RandomAccessIterator>
__equal_range(RandomAccessIterator first,
            RandomAccessIterator last,
            const T& value,
            Distance*,
            random_access_iterator_tag){
    Distance len=last-first;
    Distance half;
    RandomAccessIterator middle,left,right;
    while(len>0){
        half=len>>1;//1. 获取数量的一半
        middle=first+half;//2. 获取中间位置的值
        if(*middle<value){寻找value值所在的区间，和常规二分法思路一致
            first=middle+1;
            len=len-half-1;
        }else if(value<*middle)
            len=half;
        else{
            left=lower_bound(first,middle,value);//获取左边界，lower_bound包含相等的值
            right=upper_bound(++middle,first+len,value);//获取右边界，upper_bound不包含相等的值
            return pair<RandomAccessIterator,RandomAccessIterator>(left,right);
        }
    }
    return pair<RandomAccessIterator,RandomAccessIterator>(first,first);
}
inplace_merge
template <class BidirectionalIterator>
inline void inplace_merge(BidrectionalIterator first,
                        BidirectionalIterator middle,
                        BidirectionalIterator last){
    if(first==middle||middle==last) return ;
    __inplace_merge_aux(first,middle,last,value_type(first),distance_type(first));
}

template <class BidirectionalIterator,class T,class Distance>
inline void __inplace_merge_aux(BidirectionalIterator first,
                                BidirectionalIterator middle,
                                BidirectionalIterator last,
                                T*,Distance*){
    Distance len1=0;
    distance(first,middle,len1);//序列1的长度
    Distance len2=0;
    distance(middle,last,len2);//序列2的长度
    temporary_buffer<BidirectionalIterator ,T> buf(first,last);//临时缓冲区，
    if(buf.begin()==0)
        __merge_without_buffer(first,middle,last,len1,len2);//缓存区分配失败，使用原址归并，原址归并采取的是比较互换算法，算法的时间复杂度为O(n*n)
    else
        __merge_adaptive(first,middle,last,len1,len2,buf.begin(),Distance(buf.size()));//缓存区分配成功也可能是部分成功，具体请况在下面讨论

}

template <class BidirectionalIterator,class Distance,class Pointer>
void __merge_adaptive(BidirectionalIterator first,
                    BidirectionalIterator middle,
                    BidirectionalIterator last,
                    Distance len1.Distance len2,
                    Pointer buffer,Distance buffer_size){
    if(len1<=len2&&len1<=buffer_size){//缓冲区可以容纳序列1
        Pointer end_buffer=copy(first,middle,buffer);//直接使用外归并算法
        merge(buffer,end_buffer,middle,last,first);
    }else if(len2<=buffer_size){//缓冲区只能容纳序列2
        Pointer end_buffer=copy(middle,last,buffer);//使用外归并算法
        __merge_backward(first,middle,buffer,end_buffer,last);
    }else{//缓冲区既不能容纳序列1也不能容纳序列2，此时就是考虑如何减小归并的长度，使得缓冲区可以被用上
        BidirectionalIterator first_cut=first;
        BidirectionalIterator second_cut=middle;
        Distance len11=0;
        Distance len22=0;
        if(len1>len2){  
            len11=len1/2;//缩短序列1的长度，为切割点1
            advance(first_cut,len11);
            second_cut=lower_bound(middle,last,*first_cut);//即序列2中第一个比切割点1大的元素，为切割点2
            distance(middle,second_cut,len22);
        }else{
            len22=len2/2;
            advance(second_cut,len22);
            first_cut=lower_bound(first,middle,*second_cut);
            distance(first,first_cut,len11);
        }
        BidirectionalIterator new_middle=__rotate_adaptive(first,first_cut,middle,len11,len22,buffer,buffer_size);
        __merge_adaptive(first,first_cut,new_middle,len11,len22,buffer,buffer_size);
        __merge_adaptive(new_middle,second_cut,last,len1-len11,len2-len22,buffer,buffer_size);
    }
}

template <class BidirectionalIterator1,class BidirectionalIterator2,class Distance>
BidirectionalIterator1 __rotate_adaptive(BidirectonalIterator1 first,
                                        BidirectionalIterator1 middle,
                                        BidirectionalIterator1 last,
                                        Distance len1,Distance len2,
                                        BidirectionalIterator2 buffer,
                                        Distance buffer_size){
    BidirectionalIterator2 buffer_end;
    if(len1>len2&&len2<=buffer_size){
        buffer_end=copy(middle,last,buffer);
        copy_backward(first,middle,last);
        return copy(buffer,buffer_end,first);
    }else if(len1<=buffer_size){
        buffer_end=copy(first,middle,buffer);
        copy(middle,last,first);
        return copy_backward(buffer,buffer_end,middle);
    }else{
        rotate(first,middle,last);//使用原址旋转方式
        advance(first,len2);
        return first;
    }
}

总结：基础算法的性能提升就在于对细粒度操作的精确分类和对空间和时间的有效权衡，这里的inplace_merge操作就是在考虑各种细粒度场景下有限空间的最优解决方案。

nth_element
template<class RandomAccessIterator>
inline void nth_element(RandomAccessIterator first,
                        RandomAccessIterator nth,
                        RandomAccessIterator last){
    __nth_element(first,nth,last,value_type(first));
}

template<class RandomAccessIterator,class T>
void __nth_element(RandomAccessIterator first,
                RandomAccessIterator nth,
                RandomAccessIterator last,
                T*){
    while(last-first>3){
        RandomAccessIterator cut=__unguard_partition(first, last, T(__median(*first,*(first+(last-first)/2),*(last-1))));
        if(cut<=nth)
            first=cut;
        else 
            last=cut;
    }
    __insertion_sort(first,last);
}
mergesort(基于inplace_merge)
template<class BidirectionalIterator>
void mergesort(BidirectionalIterator first,BidirectionalIterator last){
    typename iterator_traits<BidirectionalIterator>::difference_type n=distance(first,last);
    if(n==0||n==1)
        return ;
    else{
        BidirectionalIterator mid=first+n/2;
        mergesort(first,mid);
        mergesort(mid,last);
        inplace_merge(first,mid,last);
    }
}
### 关注memory pool、iterator_traits、deque、RB-tree、hash、quicksort、mergesort
#7 仿函数
###7.1 仿函数简介
仿函数事实上就是一种功能性封装类型，它对函数操作符operator（）进行重载，然后重新定义某一算子功能，其对象被传入算法作为一个动态功能嵌入到容器操作中去。传统意义上我们的函数指针也可作为形参传入，但是函数指针不能满足STL对抽象性的要求（函数指针毕竟不是一种抽象性更高的自定义类型，而c++的类可以完成更为复杂的功能），并且它也无法和STL的其他组件搭配。
###7.2 可配接的关键
- STL仿函数应该有能力被函数配接器修饰。为了有配接能力，每一个仿函数必须定义自己的相应型别。这些型别是为了让配接器能够取出，获得仿函数的某些信息。相应型别都只是一些typedef，所有必要操作在编译期就全部完成了，对程序的执行效率没有任何影响。
- 其型别主要用来表现函数参数型别和传回值型别。<stl_function.h>定义了两个classes，分别代表一元和二元仿函数，其中没有任何members，唯有一些型别定义。任何仿函数，只要依个人需求选择继承其中一个class，便自动拥有了那些型别，也就拥有了配接能力
#####7.2.1 unary_function
一元仿函数的基类
#####7.2.1 binary_function
二元仿函数的基类
###7.3 算术类仿函数
###7.4 关系运算类仿函数
###7.5 逻辑运算类仿函数

#8 配接器
adaptor的定义：将一个class的接口转换为另外一个class的接口，使原本因接口不兼容而不能合作的classes可以一起运作。
注：感觉有点像装饰器，就是在一个类型的接口上装饰出另外一组接口，然后封装出一个新的类型
### 8.1 配接器简介与分类
- STL所提供的各种配接器中，改变仿函数接口者，我们称之为function adapter，改变容器接口者，我们称之为container adapter。改变迭代器接口者，我们称之为iterator adapter
#####8.1.1 应用于容器
queue和stack基于deque上的配接器，使用包含的方式将底层容器嵌入到新类型中
#####8.1.2 应用于迭代器
insert iterator、reverse iterators、iostream iterators.
#####8.1.3 应用于仿函数
灵活度最强的配接器功能，可以实现bind、negate、compose、以及对一般函数或者成员函数的修饰（使其成为一个仿函数），在<stl_function.h>中是这么规定的
- bind：bind2nd(less<int>(),12)，这里的意思是将仿函数的第二个参数绑定为12，其仍然返回一个仿函数类型
- compose：compose1(f(x),g(x))，复合函数，及g(x)的返回值作为f(x)的参数
- 对于一般函数和成员函数的兼容：可以传入普通函数，但是无法实现配接功能，除非加上ptr_fun()和mem_fun()。
###8.4 function adapters
和其他配接器一样，函数配接器不过是包含一个函数成员并在其之上使用一些操作，并返回一个仿函数对象的封装结构罢了。
上一篇下一篇

猜你喜欢

热点阅读