STL源码剖析 阅读笔记

字数统计: 11.7k字   |   阅读时长: 47分

前言

大一开始接触STL，一直以来熟于使用却疏于原理。读STL源码有什么用呢？作者侯捷在前言中写到这段话：

1
2
3
4
5
6
人们常说，不要从轮子重新造起，要站在巨人的肩膀上。面对扮演轮子角色的这
些STL 组件，我们是否有必要深究其设计原理或实作细节呢？答案因人而异。从
应用的角度思考，你不需要探索实作细节（然而相当程度地认识底层实作，对实
务运用有绝对的帮助）。从技术研究与ᴀ质提升的角度看，深究细节可以让你彻
底掌握一切；不论是为了重温数据结构和算法，或是想要扮演轮子角色，或是
想要进一步扩张别人的轮子，都可因此获得深厚扎实的基础。

参考资料：
《STL源码剖析》– 侯捷

概述

1
2
3
4
5
STL 所实现的，是依据泛型思维架设起来的一个概念结构。这个以抽
象概念（abstract concepts）为主体而非以实际类别（classes）为主体的结构，形成
了一个严谨的接口标准。在此接口之下，任何组件有最大的独立性，并以所谓迭
代器（iterator）胶合起来，或以所谓配接器（adapter）互相配接，或以所谓仿函
式（functor）动态选择某种策略（policy 或 strategy）。

GNU源码开放精神

全世界所有STL实品，都源于HP公司拥有的原始版本。每个头文件都有开放源码的声明。

SGI STL实作版本

SGI版本被GCC采用，可读性非常高，对语言特性支持良好。

六大组件

  • container 容器
    用于存放数据 实质是class template

  • algorithm 算法
    实质是function template

  • iterator 迭代器
    容器与算法之间的桥梁，是所谓的泛型指针

  • functor 仿函数
    行为类似函数，可以作为算法的策略（policy），重载了operator ()的class或class template，或者是函数指针。

  • adapter 适配器
    修饰容器和仿函数、迭代器的，比如stack和queue其实是deque+适配器

  • allocator 配置器
    动态空间配置、管理和释放的class

SGI STL 的编译器组态设定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
不同的编译器对C++语言的支持程度不尽相同。做为一个希望具备广泛移植能力
的链接库，SGI STL 准备了一个环境组态文件<stl_config.h>，其中定义许多常
数，标示某些状态的成立与否。所有 STL 头文件都会直接或间接含入这个组态文件，
并以条件式写法，让前处理器（pre-processor）根据各个常数决定取舍哪一段程序
码。

例如：
// in client
#include <vector>

// in <vector>
#include <stl_algobase.h>

// in <stl_algobase.h>
#include <stl_config.h>

空间配置器 allocator

如果只是想学应用，空间配置器最不需要学习，因为它隐藏在各种组件的背后，默默付出。

但如果要掌握container的原理，它又显得极其关键，因为STL整个操作数据都放在容器中，而容器又需要空间配置器为其分配空间。

具备sub-allocation的SGI空间配置器

SGI的配置器用的是alloc而非allocator，且STL里面的容器都默认采用alloc配置器，如：

1
2
template<class T,class Alloc = alloc> //预设使用alloc为配置器
class vector{};

其实SGI中也有allocator，但是它自己没使用，也不建议我们使用，allocator只把c++里的new和delete做了一个简单的包装。比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
inline T* allocate(ptrdiff_t size,T*){
    set_new_handler(0);
    T* tmp = (T*)(::operator new(size_t)(size * sizeof(T)));
    if(tmp == 0 ){
        cerr<<"out of memory"<<endl;
        exit(1);
    }return tmp;
}
template<class T>
inline void deallocate(T* buffers){
    ::operator delete(buffer);
}

new_handler的查阅的一些资料：

  • new_handler类型函数将在默认内存申请函数(operator new和operator new[])申请内存失败时被调用。
  • 默认情况下，当内存不能够分配时，new操作将抛出一个bad_alloc的异常。你可以改变这个默认操作，通过set_new_handler设置一个new_handler。你可以使用set_new_handler(0)，获得一个不抛出异常的new.
  • 用户定义的my_handler应该可以做以下几几件事之一:
    　释放内存，产生更多可用的内存
    　抛出bad_alloc异常
    　终止程序

在这里传入参数0，就不会抛出异常，而是程序直接exit(1)。

std::alloc

为了精密分工，STL将内存配置由allocate()负责，内存释放由deallocate()负责；对象构建工作由const ruct()负责，对象析构由destroy()负责。

1
2
3
<memory>中有两个文件：
<stl_alloc.h>负责空间配置和释放
<stl_construct.h>负责对象构造和析构

空间配置的设计思想：

  • 向system heap申请空间
  • 考虑多线程状态
  • 考虑内存不足时的应变措施
  • 考虑内存fragment问题

在申请空间的时候为了线程安全，是要对堆空间进行互斥访问的，这里作者为了简化复杂性，忽略了多线程的处理。
SGI STL的内存配置基于C语言的malloc和free。另外考虑到小型空间申请可能造成的内存碎片问题，SGI设计了双层级配置器，第一级直接使用malloc和free，第二级就可以根据情况采用不同的策略。
如果申请空间大于128字节，就用第一级配置器，否则用后者，采用较为复杂的内存池（memory pool）方式。

为了符合STL规格，SGI把第一级和第二级配置器包装成了simple_alloc标准接口。

第一级配置器：

  • 实现allocate，用malloc
  • 实现deallocate，用free
  • 模拟new_handler，处理内存不足的状况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void *allocate(size_t n){
    void *result = malloc(n);
    if(0==result) result = oom_malloc(n);//内存不足时调用out_of_memory方式
    return result;
}
static void deallocate(void *p,size_t){
    free(p);
}
//另外，还给了接口，用来自定义oom handler

//而oom_malloc其实就是在不断尝试释放、配置、释放、配置...
for(;;){
    my_malloc_handler = __malloc_alloc_oom_handler;
    if(0 == my_malloc_handler){__THROW_BAD_ALLOC;}//如果处理例程没设定，直接bad alloc
    (*my_malloc_handler)();//调用处理例程，企图释放内存
    result = malloc(n);
    if(result)return result;
}

第二级配置器：

第二级配置器多了一些机制，避免内存碎片。
内存碎片带来的问题不仅仅是难以利用，在管理这些内存碎片时也会带来额外负担。
当申请内存少于128byte时，以memory pool管理。为了方便管理，第二级配置器会把申请的内存需求上调至8的倍数，并维护16个free-lists，各自管理的大小分别是8,16,24,…,128bytes的空间。（类似于邻接表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void *allocate(size_t n){
    if(n > (size_t) __MAX_BYTES)return malloc_alloc::allocate(n);
    //如果申请内存大于最大byte，调用第一级配置器
    
    find result in memory pool
    if(result == 0){
        //重新装填free list
    }
    //调整free list
    return result;
}
static void *deallocate(void *p,size_t n){
    同样是如果n大于最大byte，说明是第一级配置器给予的，
    调用malloc_alloc::deallocate(n);
    否则回收内存
}

如果不够分配，需要到memory pool取出空间给free list使用，这是chunk_alloc()的工作。

构造和析构的基本工具construct和destroy

构造其实就是接受一个指针p和一个初值value，然后实现将初值绑定到指针p所指空间便可。
而destroy有两个版本，一种是对接受的指针进行析构，这种直接调用该对象的析构函数即可；而第二种接受first和last两个迭代器，要对迭代器范围内的对象进行析构，考虑效率，可以先利用value_type获得迭代器所指向对象的数据类型，然后判断这些对象的析构是否可以省略。
对类型判断和对是否可省略的判断目前当作黑盒子，是可以实现的。

内存基本处理工具

  • uninitialized_copy
  • uninitialized_fill
  • uninitialized_fill_n

如果是POD，也就是scalar types或传统的C struct 类型，必然拥有copy/assignment函数，可以采用最有效率的方法，而对于not-POD，就采用保险安全的方法。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class ForwardIterator,class T>
inline void uninitialized_fill(ForwardIterator first,ForwardIterator last,
                                const T& x){
    __uninitialized_fill(first,last,x,value_type(first));                                
}
template<class ForwardIterator,class T>
inline void __uninitialized_fill(ForwardIterator first,ForwardIterator last,
                                const T& x,__true_type){
    fill(first,last,x);
}
template<class ForwardIterator,class T>
inline void __uninitialized_fill(ForwardIterator first,ForwardIterator last,
                                const T& x,__false_type){
    ForwardIterator cur = first;
    (;cur!=last;cur++)construct(& *cur,x);//必须一个一个构造，不能用STL算法
}

迭代器 Iterator

迭代器的中心思想在于，将数据容器container和算法algorithm分开，彼此独立设计，再用迭代器将它们联系起来。如何设计出这两者之间的良好胶着剂，是个大难题。

迭代器是一种行为类似指针的对象，因此迭代器最重要的工作就是对operator*和operator->进行重载。

可参考auto_ptr（一个用来包装原生指针的对象，帮助解决内存泄漏的问题）。

1
2
3
4
5
void func(){
    auto_ptr<string> ps(new string("hello"));
    cout<<*ps<<endl;
    cout<<ps->size()<<endl;//离开不需要释放内存，会自动回收
}

智能指针

在这里不妨对智能指针做一个简单的了解。
所谓智能指针其实就是一个类对象，当超出对象作用域时，类自动调用析构函数，自动释放资源，简化了内存管理。

auto_ptr

智能指针可以像类的原始指针一样访问类的public成员，成员函数get()返回一个原始的指针;
成员函数reset()重新绑定指向的对象，而原来的对象则会被释放。
注意我们访问auto_ptr 的成员函数时用的是“.”，访问指向对象的成员时用的是“->”。我们也可用声明一个空智能指针auto_ptrptest();
当我们对智能指针进行赋值时，如ptest2 = ptest，ptest2会接管ptest原来的内存管理权，ptest会变为空指针；
如果ptest2原来不为空，则它会释放原来的资源。
基于这个原因，应该避免把auto_ptr放到容器中，因为算法对容器操作时，很难避免STL内部对容器实现了赋值传递操作，这样会使容器中很多元素被置为NULL。
判断一个智能指针是否为空不能使用if(ptest == NULL)，应该使用if(ptest.get() == NULL)。
release这个函数只是把智能指针赋值为空，但是它原来指向的内存并没有被释放，相当于它只是释放了对资源的所有权。

unique_ptr

C++11新标准，取代了C++98的auto_ptr。
unique_ptr 是一个独享所有权的智能指针，它提供了严格意义上的所有权，包括：
1、拥有它指向的对象
2、无法进行复制构造，无法进行复制赋值操作。即无法使两个unique_ptr指向同一个对象。但是可以进行移动构造和移动赋值操作
3、保存指向某个对象的指针，当它本身被删除释放的时候，会使用给定的删除器释放它指向的对象
unique_ptr 可以实现如下功能：
1、为动态申请的内存提供异常安全
2、讲动态申请的内存所有权传递给某函数
3、从某个函数返回动态申请内存的所有权
4、在容器中保存指针
5、auto_ptr 应该具有的功能
unique_ptr 和 auto_ptr用法很相似，不过不能使用两个智能指针赋值操作，应该使用std::move; 而且它可以直接用if(ptest == NULL)来判断是否空指针；release、get、reset等用法也和auto_ptr一致，使用函数的返回值赋值时，可以直接使用=, 这里使用c++11 的移动语义特性。另外注意的是当把它当做参数传递给函数时（使用值传递，应用传递时不用这样），传实参时也要使用std::move,比如foo(std::move(ptest))。它还增加了一个成员函数swap用于交换两个智能指针的值。

1
2
3
4
5
6
ptest2 = std::move(ptest);
//不能直接ptest2 = ptest，调用了move后ptest2原本的对象会被释放，ptest2对象指向原本ptest对象的内存
if(ptest == NULL)cout<<"ptest = NULL\n";
//因为两个unique_ptr不能指向同一内存地址，所以经过前面move后ptest会被赋值NULL，输出ptest=NULL
Test* p = ptest2.release();
//release成员函数把ptest2指针赋为空，但是并没有释放指针指向的内存，所以此时p指针指向原本ptest2指向的内存

shared_ptr

从名字share就可以看出了资源可以被多个指针共享，它使用计数机制来表明资源被几个指针共享。可以通过成员函数use_count()来查看资源的所有者个数。出了可以通过new来构造，还可以通过传入auto_ptr, unique_ptr,weak_ptr来构造。当我们调用release()时，当前指针会释放资源所有权，计数减一。当计数等于0时，资源会被释放。

1
cout<<ptest2.use_count()<<endl;//显示此时资源被几个指针共享

weak_ptr

1
2
3
4
5
6
weak_ptr是用来解决shared_ptr相互引用时的死锁问题,
如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,
资源永远不会释放。
它是对对象的一种弱引用，不会增加对象的引用计数，
和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，
它可以通过调用lock函数来获得shared_ptr。

迭代器类型

1
2
3
4
在实现迭代器的过程中，往往会暴露出太多容器的实现细节，而这些细节本该是封装隐藏起来的。
要自己设计迭代器，就要对容器有非常深刻的理解，不如干脆把迭代器的开发工作交给容器设计者好了。

如此一来，所有实现细节反而得以封装不被使用者看到。

利用function template的参数推导机制，获取变量类型。

1
2
3
4
5
6
7
8
9
10
11
template<class I,class T>
void func2(I iter,T t){
    T tmp;//这样就获取了迭代器指向变量的类型
};
template<class I>
inline void func(I iter){
    func2(iter,*iter);
}
int main(){
    int a;func(&a);
}

这样只要对外展示func函数，把实际操作放到func2中，就可以推导出迭代器指向类型。

traits 萃取器

定义迭代器所指对象的类型为value type。
如果函数要以value type作为返回值，就无法使用参数推导了。
可以用内嵌类型解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
struct Iter{
    typedef T value_type;//申明内嵌类型
    T* ptr;
    Iter(T* ptr=0):ptr(ptr){}
    T& operator*() const{return *ptr;}
}
template<class I>
typename I::value_type func(I iter){
    return *iter;
}
int main(){
    Iter<int> it(new int(0));
    cout<<func(it)<<endl;//typename I::value_type自动具象化为int
}

typename修饰必不可少，因为在被编译器具象化之前，T是未知的，所以需要告诉编译器这是一个成员函数，而不是一个成员变量。
这个做法有个缺陷，就是不能对原生指针进行萃取。因为原生类型不是class type，无法内嵌类型。

偏特化

含义：如何类模板中拥有一个或以上的模板参数，我们可以针对其中某个模板参数进行特化工作，也就是说在泛化设计中提供特化版本，赋予某些模板参数一个明确指定的版本。
偏特化是针对模板参数做出的更进一步条件限制所设计出来的一个特化版本。

如：

1
2
3
4
5
template<typename T>
class C{...};//允许T为任何类型

template<typename T>
class C<T*>{...};//这个特化版本只适用于T为原生指针的情况，即“进一步限制”

traits就像一台“特性萃取机”，萃取各个迭代器的相应类型。通过class template偏特化的作用，不论原生指针或class迭代器，都可以让外界方便获得相应类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
value type
difference type
pointer
reference
iterator categoly

template<class I>
struct iterator_traits{
    typedef typename I::iterator_category;
    typedef typename I::value_type;
    typedef typename I::difference_type;
    typedef typename I::pointer;
    typedef typename I::reference;
}

value type

value type是指迭代器所指对象的类型。

difference type

difference_type用来表示两个迭代器之间的距离。

对于原生指针的特化版本：

1
2
3
4
template<class T>
struct iterator_traits<T*>{
    typedef ptrdiff_t difference_type;//偏特化版本
}

对于const修饰的原生指针的特化版本：

1
2
3
4
template<class T>
struct iterator_traits<const T*>{
    typedef ptrdiff_t difference_type;//偏特化版本
}

那么，现在想要任何迭代器I的difference_type，可以写成：

1
typename iterator_traits<I>::difference_type;

reference type

从迭代器是否可以改变所指对象内容来看，迭代器分constant iterators（如const int* pic）和mutable iterators（如int * pi），当对一个和mutable iterator进行引用时，得到的是一个左值，因为左值允许赋值操作。

在C++中，函数如果传回左值，都是以引用的方式进行。比如p的value type是T，那么*p的类型不应该是T，而是T&；如果p的value type是const T，那么 * p的类型是const T&。这里讨论的 * p就是reference type。

pointer

pointer和reference在C++中有密切关联。
如果传回一个左值，用之表示所指之物是可能的，那么传回一个左值，用之表示所指之物的地址也是可能的。也就是说，我们传回一个pointer指向迭代器所指之物。

1
2
Item& operator*() const {return *ptr;}
Item* operator->() const {return ptr;}

iterator_category

迭代器根据移动特性和操作分为五类：

  • input iterator 只读
  • output iterator 只写
  • forward iterator 允许读写
  • bidrectional iterator 双向移动
  • random access iterator 支持随机访问

比如实现一个advance函数，对于不同迭代器有不同实现方法，使用函数重载机制能够在编译期就确定正确的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct input_iterator_tag{};
struct output_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 InputIterator,class Distance>
inline void __advance(InputIterator& i,Distance n,input_iterator_tag){
    while(n--)++i;
}
template<class InputIterator,class Distance>
inline void __advance(InputIterator& i,Distance n,forward_iterator_tag){
    __advance(i,n,input_iterator_tag());
}
template<class InputIterator,class Distance>
inline void __advance(InputIterator& i,Distance n,bidirectional_iterator_tag){
    if(n>=0)while(n--)++i;
    else while(n++)--i;
}
template<class InputIterator,class Distance>
inline void __advance(InputIterator& i,Distance n,random_access_iterator_tag){
    i+=n;
}
template<class InputIterator,class Distance>
inline void advance(InputIterator& i,Distance n){
    __advance(i,n,iterator_traits<InputIterator>::iterator_category());
}

通过继承，不必再写单纯只做传递调用的函数。

std::iterator

为了规范迭代器类型，便于traits萃取，所有新设计的迭代器都继承自std iterators class，就可保证STL所需规范。

1
2
3
4
5
6
7
8
9
10
template<class Category,class T,class Distance = ptrdiff_t,
        class Pointer = T*,class Reference = T&>
struct iterator{
    typedef ...
}
//要使用iterator，就传入前两个参数即可，如
template<class Item>
struct ListIter{
    public std::iterator<std::forward_iterator_tag,Item>{}
}

iterator源代码完整重列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 5种迭代器类型
struct input_iterator_tag{};
struct output_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{};

// 自行开发的迭代器最好继承自std::iterator

// traits 萃取器
template<class Iterator>
struct iterator_traits {
    typedef typename Iterator::iterator_category iterator_category;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
};

// 原生指针traits偏特化版
template<class T>
struct iterator_traits<T*> {
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;
}

// 以及还有部分源码，就不贴了，大概都是如何获取traits类型，以及迭代器distance方法

SGI STL的私房菜 __type_traits

不在标准规范以内，是SGI STL内部的东西。
这里我们关注的类型特性指：这个类型是否可以copy？是否可以赋值？是否可以直接释放？
根据结果可以采用最有效率的措施，比如构造、析构、拷贝、赋值时的特殊操作。这样能够使得容器获得显著的效率提升。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
__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  // plain old data

// 针对char、signed char、short、int等基本类型提供特化版本，采用最快速的方式，如memcpy等进行copy和assgin。

__STL_TMPLATE_NULL struct __type_traits<char> {
    typedef __true_type has_trivial_default_constructor;
    ...
}

// 通过这个，在__unitialized_fill_n函数里，就可以根据__true_type和__false_type走不动调用。以上只是对原生指针进行了介绍，实际上还有很多复杂情形。

容器 Container

学完空间分配器后，原本打算按照顺序先看迭代器，但对于特征萃取器部分非常困惑，于是打算先跳过迭代器，看容器部分。

容器可以分为序列式和关系式，容器之间存在内含的关系，比如heap内含一个vector，而stack和queue内含一个deque等等。

vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<class T,class Alloc = alloc>
class vector {
    public :
    // 嵌套类型定义
    typedef T value_type;
    typedef value_type* pointer;
    ...
    
    protected :
    typedef simple_alloc<value_type, Alloc> data_allocator;
    //定义了巢状型别
    iterator start,finish,end_of_storage;
    ...
    
    public :
    explicit vector(size_type n) { fill_initialize(n, T()); }
    // explicit关键字限制了这个构造函数只能显式调用，规范了代码编写，避免一些错误

    void push_back(const T& x){
        if(finish == end_of_storage){
            insert_aux(end(), x);
        } else {
            construct(finish++, x);//在alloc里面，construct使用了placement new对迭代器位置进行覆盖。
        }
    }
}

vector是线性连续空间，因此迭代器的类型是可随机访问的，如果写出vector::iterator it，其实类似于int*。

在构造、元素添加时，如果容量不够，会扩充至2倍。而扩张的过程必须经历“重新配置空间、元素复制、释放原空间”的过程。

注意：一旦vector进行了空间重新配置，之前的迭代器就会失效了，这里经常容易犯错。
vector属于平时用的很多的容器，要特别注意。
在涉及insert、append、pop等操作时，通用做法都是检查是否会超size，然后再挪位，并且做相应的构造和析构操作。

list

list对于空间运用是精准的，insert和erase的时候都会涉及申请和释放一个空间。

1
2
3
4
5
6
7
8
template<class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev; // 按理说这里可以用__list_node<T>*
    void_pointer next;
    T data;
}
// 双向链表

list的结点不能单纯的用原生指针存储，因为这些结点不保证在存储空间中连续存在。因为要支持双向链表的功能，所以迭代器的类型是Bidrectional Iterators。

主要可以关注迭代器实现的++和–运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef __list_iterator<T,Ref,Ptr> self;
typedef __list_node<T>* link_type;
link_type node; // 指向list的结点

self& operator++(){
    node = (link_type)((*node).next);
    return *this;
}
self operator++(this){
    self tmp = *this;
    ++*this;
    return tmp;
}
self& operator--(){
    node = (link_type)((*node).prev);
    return *this;
}
self operator--(this){
    self tmp = *this;
    --*this;
    return tmp;
}

SGI list是一个环形双向链表。因此，如果需要满足前闭后开原则，可以让node指向一个空结点。node表示最后一个结点的下一个位置，即end。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
iterator begin() {
    return (link_type)((*node).next);
}
iterator end() {
    return node;
}
bool empty() const {
    return node->next == node;
}
size_type size() const {
    size_type result = 0;
    distance(begin(),end(),result);
    return result;
}
reference front() {
    return *begin();
}
reference back() {
    return *(--end());
}

deque

deque是一种双向开口的连续线性空间，可以在头尾做元素的插入和删除操作。deque允许动态地以分段连续空间组合，也就是随时增加一段新的空间，并链接起来。
deque提供随机访问，但是迭代器的实现复杂程度是vector不能比的。除非必要，还是使用vector效率更高。
deque的连续空间是由一段一段定量连续空间组成的，一旦有必要在首尾增加新空间，deque就配置一段新的连续空间，并且维护其整体连续的假象。
deque采用一块MAP作为主控，MAP中每个元素都是一个指针，指向另一块较大的连续线性空间，称为缓存区。缓存区才是deque的空间主体。
MAP本质上是一个T**，也就是MAP本身是一个指针，所指之物又是一个指针，指向一块类型为T的空间。

deque实现难点在迭代器。而迭代器的++和–运算非常复杂，需要配合MAP进行维持“整体连续”的假象。

1
2
3
4
5
6
template<class T,class Ref,class Ptr, size_t BufSiz>
struct __deque_iterator {
    typedef __deque_iterator<T,T&,T*,BufSiz> iterator;
    
    // deque的迭代器没继承std::iterator
}

对于MAP的维护类似于vector，再引入start和finish对MAP的首尾进行跟踪。

1
2
3
start.cur 指向当前MAP首部指向线性区域的具体位置
start.first/last 指向当前MAP首部指向线性区域的首尾
start.node 指向start在MAP所在的位置

stack

stack以deque作为缺省时的底部结构。由于stack是在底部容器的基础上完成所有工作，这种性质称为adapter（适配器）。stack一般被称为适配器容器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class T,class Sq = deque<T> >
class stack {
    protected:
    Sq c; // 底层容器
    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();
    }
}

除了用deque实现stack，也可以用vector、list等。stack不提供走访功能，因此不需要迭代器。

queue

类似stack。

heap

heap是priority_queue的幕后英雄。关于heap可以主要了解一下heap算法。
heap底层容器可以用vector实现：

1
2
3
push_heap:把新加入的元素放到vector的end()处，然后将新结点跟父结点比较，如果需要交换位置就交换，直到不需要交换为止。

pop_heap:拿走根结点。这个时候要对top位置做一个填充。可以从root的左右两端拿走较大的，一直这样递归下去，直到停止。然后再把heap的最后一个元素放在空位。

堆算法感觉能够手写pop和push的代码就足够了。利用heap的性质，还能实现sort_heap算法。本质是利用popHeap一直取最值。

priority_queue

只允许在底增加元素，在顶部取出元素。缺省情况下使用max-heap完成。

slist

单向链表。

关联式容器

关联式容器，每笔数据都有一个key和一个value，当元素被插入到关联式容器中时，容器内部结构会按照其key值，来决定放置的适当位置。关联式容器没有所谓头尾，不会有popBack、pushBack、popFront等操作。
一般而言，关联式容器内部实现是平衡树（和散列表），以获得更好的搜寻效率。

AVL tree

为确保整理深度为O(logN)，直观上是每个节点的左右儿子的高度相同，AVL tree退而求其次，只要任何结点的左右儿子高度差不超过1，则认为平衡。

zig-zag就不看了，在竞赛时期对于这个通常使用模板，不用特别深究实现，了解原理即可。

RB tree

红黑树被应用于set和map，满足以下规则：

  1. 每个结点不是红色就是黑色
  2. 根节点为黑色
  3. 如果节点是红色，那么它的子节点必须为黑色
  4. 任意一个结点到达其叶子的任何路径，所含黑节点数必须相同

根据规则4，新增结点必须为红色。
根据规则3，新增结点的父结点必须为黑色。如果新增节点插入后未满足以上规则，就要对颜色和树形进行修改。

RB tree在插入、删除性能上优于AVL tree，AVL tree适用于在大量查询、少量插删的场景，否则在调整树形时会消耗太多的性能。

因为规则3和4，能够保证从节点x到它所有叶子的距离差不超过2倍。证明：

1
设x到a是最短路径，而x到b是最长路径，且dis(x,a) < dis(x,b)，有x到a路径上所有点都是黑色，而路径x到b一定是红黑各有。此时，最坏情况下，x到b路径上红点和黑点的数量是相等的。也就是，dis(x,b) <= 2 * dis(x,a) 。

对于zig-zag具体实现不做深究，主要了解一下插入时需要做什么：
0. 插入点一定是红色的，如果是黑色的，就破坏了规则4

  1. 插入节点作为根结点（规则2）：把红色变成黑色
  2. 父亲节点为黑色：不需要改变
  3. 父亲节点为红色，且叔叔也是红色：将父亲和叔叔改成黑色，同时让爷爷变红，递归
  4. 父亲为红色，叔叔为黑色（默认空结点为黑色）：进行相应的换色和旋转

RB tree 的node

1
2
3
4
5
6
7
8
9
10
11
struct __rb_tree_node_base {
    color_type color;
    base_ptr parent;
    base_ptr left;
    base_ptr right;
}
template<class value> 
struct __rb_tree_node : public __rb_tree_node_base {
    typedef __rb_tree_node<value> *link_type;
    value value_field; // 获取节点的值
}

RB tree的迭代器

要将红黑树实现成一个支持泛型的容器，迭代器的设计非常关键，首先要考虑迭代器类型、前进、后退，以及成员访问等操作。
RB tree的iterator提供双向迭代，但不具备随机访问能力，前进和后退比较特殊，iterator的operator++()和operator–()调用了基层迭代器的increment()和decrement()，前进后退是按照二叉树的节点排列实现的。

看看increment和decrement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void increment(){
    if (node->right){
        node = node->right;
        while(node->left)node = node->left;
    }
    /*
    如果当前节点有右儿子，那么只要找到右儿子子树里最小节点便可
    */
    else {
        base_ptr y = node->parent;
        while(node == y->right){
            node=y;
            y = y->parent;
        }
        /*
        本身就是个右儿子，那么就一直往上找到第一个不是右儿子的位置，然后此时的父节点就是解答
        */
        if (node->right != y) {
            node = y;
        }
    }
}

通过代码可以看出，实际上operator++()和operator–()的时间复杂度是O(logN)的。

通过这个例子也可以从源码中看出，一些我们认为是O(1)的操作，其实都是O(logN)的。比如begin()、end()等。

RB tree的内存管理
专属空间配置器rb_tree_node_allocator，每次只配置一个节点

1
2
3
4
5
6
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;
}

set

set的元素会根据键值排序，不允许有两个相同的键值。
不能通过set的迭代器改变set的元素值，因为元素值就是键值，如果任意改变，就会影响set的组织。因此，在底层把set的iterator定义成const_iterator。

1
2
3
4
template<class Key,class Compare = less<Key>, class Alloc = alloc>
class set{
    rep_type t; // 采用红黑树来表现set
}

map

所有元素根据key进行排序，所有元素都是pair，同时拥有key和value。

1
2
3
4
5
6
7
template<class T1,class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    first_type first;
    second_type second;
}

hashtable

二叉搜索树具有对数时间复杂度的表现，而散列表可以在插入、删除、搜寻上具有常数时间复杂度的表现。
使用hash会带来一个碰撞的问题，解决碰撞光是做各种探测是不够的，当表内元素过多时，需要做一次rehashing。

线性探测：
先了解什么是负载系数，指的是元素个数/表大小。
采用线性探测时，最坏情况需要遍历整个表，然后放入一个元素后，下次又要遍历整个表。插入成本的提高速度，远远高于负载系数的成长速度，这样的效率非常低。

二次探测：
如果计算出哈希值为H，则下一次使用 $ (H+1)^2 $，而不是线性探测那样。
假设表大小为质数，并且永远保持负载系数为0.5以下，那么可以确定每插入一个元素需要的探测次数不超过2。
而根据等式整理可得，二次探测并不需要真的去使用乘法和取模运算，而是加减法。

二次探测能够很好的避免线性探测带来的问题，但是假如x!=y && h(x)==h(y)，这时的冲突还是不可避免的。这种情况可以使用双哈希。

开链：
开链方法会让负载系数大于1，SGI STL的hash table就是用这个方法实现的。
简单来说就是现在表的一个元素并不只是一个节点，而是一个桶，桶x可以放入所有h(a)==x的数据。

1
2
3
4
5
template<class value>
struct __hashtable_node {
    __hashtable_node* next;
    value val;
}

hashtable的迭代器

__hashtable_iterator是一种单向迭代器，由于node中自带了next指针，所以迭代器可以轻松的进行前进操作。

实现iterator operator ++()

1
2
3
4
5
6
7
8
9
10
11
12
template<class v,class k,class hf,class exk,class eqk,class a>
__hashtable_iterator<v,k,hf,exk,eqk,a>&
__hashtable_iterator<v,k,hf,exk,eqk,a> operator ++(){
    const node* old = cur;
    cur = cur->next;
    if (!cur) {
        size_type bucket = ht->bkt_num(old->val);
        while(!cur && ++bucket < ht->buckets.size())
            cur = ht->buckets[bucket];
    }
    return *this;
}

hashtable的数据结构
hashtable的bucket聚合体是由vector实现，以完成动态扩充的。

1
2
3
4
5
template<class k,class v,class hashfcn,class extractKey,class equalKey,class Alloc = alloc>
class hashtable {}
vector<node*, Alloc>buckets;
size_type num_elements;
size_type bucket_count() const {return buckets.size();}

其中extractkey是从节点取出键值的方法，equalkey是判断键值是否相同的方法。

前面提到hashtable的表大小最好是质数，所以SGI STL预设了28个质数，存放在一个数组里，用来提供给vector动态扩充时参考。

在insert时做了一次判断是否需要表格重整，根据vector的当前大小和已插入元素个数来比较。
而重构时的算法非常优美，节省了很大常数，整体复杂度是O(m)的。

在判断元素的落脚处，是hash function的责任，SGI把这个任务封装成一层，从而取得一个可以执行取模运算的数字。这是因为有些数据是无法进行取模运算的，比如字符串const char*，这时候就需要我们提供一些转换函数。

来看看find和count函数怎么实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
iterator find(const key_type& key) {
    size_type n = bkt_num(key);
    node *first;
    for (first = buckets[n]; first && !equals(get_key(first->val),key));
    first = first->next){}
    return iterator(first,this);
}
size_type count(const key_type& key) const {
    const size_type n = bkt_num_key(key);
    size_type result = 0;
    for (const node* cur = buckets[n];cur;cur = cur->next) {
        if (equals(get_key(cur->val),key))++result;
    }
    return result;
}

hash functions
提到计算元素位置，就不得不见识一下。
bkt_num()调用了hash functions里面的方法，针对char、int、long等整数类型做一个返回原值。但对于const char*，就设计了转换函数

1
2
3
4
5
6
7
8
9
10
11
12
template<class key> struct hash{};
inline size_t __stl_hash_string(const char* s) {
    unsigned long h = 0;
    for(;*s;++s)h = 5*h+*s;
    return size_t(h);
}
由此可见，SGI STL对于无法处理的元素，如string、double等，就需要用户自行定义hash function。

## hash_set

STL只规范复杂度和接口，并不规范实现方法，但STL的set基本是用RB tree实现的，而SGI在标准规格之外提供了hash_set，以hashtable为底层机制。
如果一个类型没有hash function，那么它的hash_set就无法使用，因为hashtable是无法处理的。

template<class value,
class hashFcn = hash,
class equalkey= equal_to,
class Alloc = alloc>
class hash_set {
typedef hashtable<value,value,hashfcn,identity,equalkey,Alloc> ht;
ht rep; // 底层是hashtable
}

1
2

要使用hash_set维护const char*，需要添加hashFcn，用strcmp的值来比较是否相同，而不是直接比较const char*。

struct eqstr {
bool operator()(const char *s1,const char *s2)const {
return strcmp(s1,s2)==0;
}
}
int main(){
hash_set<const char*,hash<const char*>,eqstr> set;
set.insert(“haha”);
set.insert(“hvva”);
set.insert(“hvaa”);
}

1
2
3
4
5
6
7
8
9
10
11
12
可以知道，hash_set里的元素遍历输出，是没有排序的结果。

## hash_map

SGI还提供了hash_map，几乎都是调用hashtable的操作行为而已。
使用map，是为了能够根据key快速搜寻元素，而map和hash_map的区别就是key是否有自动排序功能。由于基本是封装了hashtable的方法，在此不做展开。

# 算法 algorithms

## mutating algorithms
所有stl算法都作用在迭代器指示的区间上，所谓质变算法，是指运算过程中会更改区间内迭代器所指的元素内容。比如swap、replace、fill、remove、permutation、partition、random suffling、sort等。
如果把质变算法作用在const迭代器上，就会出现错误，如:

vector vec(10);
vector::const_iterator it1 = vec.begin();
vector::const_iterator it2 = vec.end();
sort(it1,it2); // 报错，因为mutating algorithm作用在const 迭代器。

1
2
3
4

## nonmutating algorithms
如find、serach、count、for_each、equal、max、min。
但是for_each是可以嵌套质变算法的，如在for_each嵌套一个修改迭代器指向值的functor。

template
struct plus2 {
void operator()(T &x)const {
x+=2;
}
};
int ia[]= {1,2,3,4,566,745,1};
vector iv(ia,ia+sizeof(ia)/sizeof(int));

for_each(iv.begin(),iv.end(),plus2());

1
2
3
4
5
6
7
8
9
10
11
12
13

## STL算法的一般形式

所有泛型算法前两个参数都接收一对迭代器，称为first和last，是一对左闭右开的区间。这个区间的必要条件是，经过increment反复运用后，能够从first到达last。如果这个条件无法达到，那就会造成无法预料的结果。对于迭代器类型，不同的泛型算法能够接收的迭代器类型也不一样。

许多STL算法支持多个版本，在缺省情况使用缺省运算版本，另一个版本接收外界传入的functor。

质变算法有两种，第一种是在原来的空间进行质变（in-place），第二种是复制一份副本，在copy版进行质变。这种方法通常有函数名称尾词，如replace()和replace_copy()。

STL的算法独立于其处理的数据结构，不受数据结构的羁绊，比如遇到array、vector，或者是list、deque，正确实现所有操作。
关键在于对操作对象的类型加以抽象，迭代器的移动加以抽象，整个算法就能在抽象的层面工作了。

比如：

template
T* find(T *begin, T *end, const T& value) {
while(begin != end && *begin != value) ++ begin;
return begin;
}

1
2
3

这样的find是很好的。因为几乎适用于任何容器，而指针们应该支持以下操作：判断不等inequally、取值dereferencelm、迭代器递增prefix increment、复制copy。
对于以上find，除了支持原生指针，还可以用Iterator进行泛化。

template<class Iterator, class T>
Iterator find(Iterator begin, Iterator end, const T& value) {
while(begin != end && *begin != value) ++ begin;
return begin;
}

1
2
3

**个人认为STL里的algorithm部分，简单的算法只需要简单了解即可。迭代器、容器用的比较多，几个最常见的algorithm掌握。**

// accumulate
template<class InputIterator, class T>
T accumulate(InputIterator first,InputIterator last, T init) {
for(;first!=last;++first) init = init + *first;
return init;
}

template<class InputIterator, class T,class BinaryOperation>
T accumulate(InputIterator first,InputIterator last, T init,
BinaryOperation binary_op) {
for(;first!=last;++first) init = binary_op(init,*first);
return init;
}

// adjacent_difference
// 计算相邻元素的差值
template<class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result) {
if (first == last)return result;
*result = *first;
…
}

// partial_sum
template<class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first,InputIterator last,OutputIterator result) {
if (first == last) return result;
*result = first;
return __partial_sum(first,last,result,value_type(first));
}
template<class InputIterator, class OutputIterator,class T>
OutputIterator __partial_sum(InputIterator first,InputIterator last,OutputIterator result, T) {
T value = *first;
while(++first != last) {
value = value + * first;
*++result = value;
}
return ++result;
}

// power SGI专属，不在STL标准内，计算某数的n次方。使用快速幂完成的
template<class T,class Integer>
inline T power(T x,Integer n) {
return power(x, n, multiplies());
}

// fill 将[first, end)内所有元素填上新值
template<class InputIterator, class T>
void fill(ForwardIterator first,ForwardIterator last, const T& value) {
for(; first != last;++first) *first = value;
}

// iter_swap 交换两个迭代器所指之物的值

// lexicographical_compare 两个区间的字典序，第一个是否严格小于第二个
template
inline const T& max(const T& a,const T& b) {
return a<b?b:a;
}
template<class T,class Compare>
inline const T& max(const T& a,const T& b, Compare comp) {
return comp(a,b)?b:a;
}

// swap
template
inline void swap(T& a,T& b) {
T tmp = a;
a = b;
b = tmp;
}

// copy 强化效率无所不用其极

不论是对客户端程序或者对STL内部而言，copy都是一个常常被调用的函数，由于copy进行的是复制操作，不外乎运用assignment operator或copy constructor，这取决于当前元素是否是trivial assignment的。如果可以直接进行复制行为，如memcpy、memmove等，就大量节省时间。

copy 特化： memmove() const char *内存底层操作，速度极快
copy 泛化： __copy_dispatch()

// max_element

// merge 应用于有序区间
while(first1 != last1 && first2!=last2) {
if …;
else;
}
最后把剩余的copy进去

// gcd

template
T __gcd(T m, T n) {
while(n) {
T t = m%n;m=n;n=t;
}
return m;
}

// unique 移除重复的元素(需要先排序)
unique会返回一个迭代器，指向新区间的尾端，新区间内不含相邻重复的元素。
unique产生的残留可以用erase去除。
template
ForwardIterator unique(ForwardIterator first, ForwardIterator last) {
first = adjacent_find(first,last); // 找到相邻重复元素起点
return unique_copy(first,last,first);
}
template<class InputIterator, class OutputIterator>
inline OutputIterator unique_copy(InputIterator first, InputIterator last,
OutputIterator result) {
if (first == last) return result;
return __unique_copy(first, last, result, iterator_category(result));
}

// 根据iterator_category有若干种适应不同类型的方法。

// lower_bound
有两个版本，1是根据 < 确定位置，2是根据comp(value,*it2)确定位置。

// next_permutation
这个用的次数还比较多，而且对于原理也不是很清楚，趁此机会可以好好看看如何实现的
有两个版本，1是根据less than来确定顺序，2是根据comp(value,*it2)确定顺序。

template
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
if (first == last) return false; // 如果没有元素， false
BidirectionalIterator i = first;
++ i;
if (i == last) return false; // 如果只有1个元素， false
i = last;
– i;

for(;;){
    BidirectionalIterator ii = i; // 从尾部推进
    --i;
    if (*i < * ii) { // 出现可以交换的位置了，那么这次肯定是true
        BidirectionalIterator j = last;
        while(!(*i < *--j));
        iter_swap(i,j);
        reverse(ii,last);
        return true;
    }
    if (i == first) {
        reverse(first, last);
        return false;
    }
}

}

设3 6 4 2为pn，下一个序列pn+1应该是4 2 3 6。观察第一个序列可以发现pn中的6 4 2已经为减序，在这个子集中再也无法排出更大的序列了，因此必须移动3的位置且要找一个数来取代3的位置。在6 4 2中6和4都比3大，但6比3大的太多了，只能选4。将4和3的位置对调后形成排列4 6 3 2。注意，由于4和3大小的相邻关系，对调后产生的子集6 3 2仍保持逆序，即该子集最大的一种排列。而4是第一次移动到头一位的，需要右边的子集为最小的排列，因此直接将6 3 2倒转为2 3 6便得到了正确的一个序列pn+1

整体复杂度是O(n)的。

// random_shuffle
random_shuffle会在N!个结果中均匀的产生一个解。有两个版本，差别就在于随机数的取值。1是使用内部随机数产生器，2是使用一个产生随机数的functor。

template
inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last) {
__random_shuffle(first, last, distance_type(first));
}
template<class RandomAccessIterator, class Distance>
void __random_shuffle(RandomAccessIterator first,RandomAccessIterator last, Distance*){
if(first == last)return;
for(RandomAccessIterator i = first+1;i!=last;++ i){
#if_def __STL_NO_DRAND48
iter_swap(i, first+Distance(rand() % ((i - first) + 1)));
#else
iter_swap(i, first+Distance(lrand48() % ((i - first) + 1)));
#endif
}
}

O(n)，遍历每个位置i，然后产生一个随机位置j，交换i和j。

// sort
快速排序

在SGI中，设置了阈值，当超过阈值使用快速排序，如果数据量小于某个门槛，为避免快速排序递归调用带来过大的额外开销，就改用插入排序。如果递归深度过大，会改成堆排序。
插入排序复杂度是O(n2)的，听起来不是很好，但是在数据量小，且做了优化后，性能有不错的效果。
当分割行为有恶化的趋势时，采用堆排序。

在SGI中，使用的是三点中值法来确定pivot。即首、尾、中央三个位置的元素。
显然，迭代器必须要是RandomAccessIterator。

在源码中，如果元素个数小于等于16，就用插入排序完成。

//nth_element
确定第x位的排名，排在x之前的一定比x小，排在x后的一定比x大。

如果长度大于3，使用类似于快速排序的中值法分割序列，而当长度不大于3时，就用插入排序。

// merge_sort
归并排序。 因为归并排序需要借助额外内存，并且在内存之间移动时会耗费不少时间，所以merge sort的性能是比不上sort的，但是实现简单、概念简单。

```

Funtors 函数对象

函数对象，一种具有函数特质的对象。仿函数主要用在哪里？STL提供的各种algorithms，允许用户使用两种版本，其中一个版本表现出最常用的运算，第二种版本则表现出最好的泛化演算，允许用户用template参数来指定要采取的策略。

先将操作设计成一个函数，再将函数指针当作算法的一个参数（或者把这个操作设计成一个对象）。

仿函数存在的意义是，函数指针不能完全满足STL对于抽象性的要求，也不能满足灵活性，无法与其他组件产生很好的搭配。

仿函数实际上就是一个“行为类似函数”的对象，其类型定义中必须自定义function call operator()。

1.有一元和二元的区别
2.有算术类、关系运算类、逻辑运算类三种类型

Adapters 适配器

应用于容器、迭代器、仿函数；
容器实例有stack和queue；
迭代器实例；
仿函数实例：对返回值进行否定、函数指针、成员函数指针。

赏

谢谢打赏

支付宝
微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

iOS Developer, ACMer, ...