[读书笔记]《STL源码剖析》

摘要

学习STL，从入门到放弃，记录笔记，分享心得 :)

下面这些只是outline，也是我学习STL时的切入点

---

章节

第二章

chapter. 2.1

(1) set_new_handler() 设置new 出问题时的handler函数

(2) new, ::operator new, placement new

(3) ptrdiff_t, size_t

(4) malloc(), free(p), *p=(NULL / nullptr / 0)

chapter. 2.2

(1) sub-allocation

(2) First：std::alloc -> allocate(), deallocate() -> malloc(), free() -> Fake set_new_handler()

(3) Second：oom_malloc() -> free_list -> chunk_alloc() -> memory pool

chapter. 2.3

(1) constuct(), destroy(), uninitialized_copy(), uninitialized_fill(), uninitialized_fill_n()

(2) Commit or Rollback Principle：要么全做，要么不做

(3) POD (Plain Old Data) : trivial ctor/dtor/copy/assignment

(4) Difference : memmove(), memcpy()

(5) Specialization based on is_POD (_type_traits)：特化

---

第三章

chapter. 3.2

(1) Smart Pointer : dereference(operator *), member access(operator->) [auto_ptr, shared_ptr]

(2) Trick : Explicit(防止隐式转型), Member Template(成员函数模板)：在这里用来解决类似Stack<int>到Stack<float>赋值时的隐式转换 [推荐”Effective C++” & “More Effective C++”]

chapter. 3.3

(1) Difference : static_cast<>, reinterpret_cast<>

chapter. 3.4 （重中之重）

(1) Template 参数型别推导

(2) Nested Type : STL Standard(内嵌型别声明)

(3) Partial Specialization（偏特化）：对一部分特殊类型(原生指针，const 指针)指定特化

(4) 五种迭代器型别

(5.1) 在执行时期决定函数版本，会影响程序效率，最好能够在编译器就选择正确的版本。函数重载机制可以达成这个目标：加入一个tag参数，通过推导tag类型进行编译期类型函数推导(p95)，真TM巧妙

(5.2) 通过继承消除”单纯只做传递调用”的函数：当派生类无法满足时，直接向上判断父类类型是否有相应函数，有则调用，否则继续向上查找

Traits 理解

http://blog.csdn.net/shudou/article/details/10270971
(1) 我们需要Iterator作为算法和容器的中间件
(2) Iterator是一个指针
(3) (*Iterator) 编译无法通过 -> 增加一个中间层，进行参数推导
(4) (*Iterator)定义函数返回值时，编译无法通过 -> 需要Traits
(5) 原生指针也是RandomAccessIterator，但是原生指针没有value_type，此时需要偏特化技术来解决

---

第四章

chapter. 4.2 Vector

(1) Difference : Array(一旦分配无法改变) & Vector(自动扩容，未雨绸缪)

(2) Key Method : 配置新空间 => 数据移动 => 释放旧空间

(3) Vector 提供RandomAccessIterator，管理三个指针（start, finish, end_of_storage）

(4) Vector的动态增加大小，并不是在原空间之后接续新空间，而是以原大小的两倍配置一块较大空间，因此，一旦vector进行了扩容，指向原vector的所有迭代器都会失效

(5) Insert : 根据插入点之后的数据长度和待插入数据长度的大小关系采用不同的移动拷贝方式，提高效率

(6) Insert：插入数据永远在插入点的前面

chapter. 4.3 List

(1) Double Linked-List : List是一个双向循环链表，提供Bidirectional Iterators

(2) Insert 和 Splice(接合操作)不会导致原迭代器失效，删除操作只会导致删除的那个迭代器失效

(3) 为实现STL前开后闭的规范(end()返回的是尾部后一个元素)，刻意在环状链表的尾端加上一个空白节点

(4) 判断STL容器是否为空时，最好使用empty()，避免使用size()==0，因为底层实现如下：

bool empty() const {
    return node->next == node;
}

size_type size() const{
    size_type result = 0;
    distance(begin(), end(), result);
    return result;
}

很明显empty是O(1)算法，而size() 是O(n)

(5) List不能使用STL标准sort()算法，因为sort()只接受RandomAccessIterator，因此List需要定义自己的成员函数list::sort()

chapter. 4.4 Deque

(1) Deque : 双向开口的连续线性空间，而且对头尾元素的插入和移除都是常数时间

(2) Deque没有容量，因为它是动态地以连续空间链接而成，逻辑上Deque是连续的，提供和Vector一样的RandomAccessIterator，但是实际上，Deque的物理结构可以不是连续的

(3) 主控map[buffer *]：map管理若干缓冲区的指针

(4) Iterator[cur, first, last, node] : start（第一缓冲区的第一个元素），finish（最后缓冲区的最后一个元素的下一个位置）

(5) set_node()：该方法在行进过程中遇到缓冲区边缘，当需要跳一个缓冲区的时候需要调用

(6) reserve_map_at_front() / reserve_map_at_back() : 当Deque的保留空间都不够用时，需要更换map，包括三个步骤（配置更大的，拷贝原来的，释放原来的）

chapter. 4.5 Stack

底层用Deque实现，封闭前端开口，只在尾部提供push() 和 pop()

const_reference top() const {
    return c.back();
}
void push(const value_type& x){
    c.push_back(x);
}
void pop() {
    c.pop_back(); //注意，这里并不返回任何值
}

Stack不提供迭代器

chapter. 4.6 Queue

底层用Deque实现，封闭前端push_front()和后端pop_back

const_reference front() const {
    return c.front();
}
void push(const value_type& x){
    c.push_back(x);
}
void pop() {
    c.pop_front();
}

Queue不提供迭代器

List也可以作为Queue的底层容器

chapter. 4.7 Heap

(1) Heap 本质上是一个 Priority Queue

(2) 可能的底层实现：

List :
    1. 元素插入是常数时间，但是要找到list中的极值，必须对整个list进行线性扫描
    2. 在插入时进行排序的话，虽然取得机制和元素删除操作达到最高效率，但是元素插入只有线性表现

Binary Search Tree(二叉搜索树，红黑树RB-T):
    1. 元素的插入和极值的取得都有O(logN)的表现
    2. 但是二叉搜索树实现太复杂

正解 : Complete Binary Tree(完全二叉树)
    1. 完全二叉树内没有节点漏洞，因此可以使用array或vector来存储所有节点
    2. Trick:通过将0号元素设置为特殊值，从1号元素开始计数，那么对于array的i处，其左子节点必然位于2i处，右节点在2i+1处
    3. array不能改变大小，但是Heap需要改变大小，因此Vector是更好的选择

(3) Heap相关算法

push_heap() 
    1. 在尾部加入新元素
    2. 向上回溯，调整整个Heap

pop_heap()
    1. 取出尾端元素
    2. 将root元素放在尾端
    3. 将尾端元素放在root
    4. 调整last指针(--last)
    5. 从root处执行向下回溯
    6. 然后使用vector的back()函数获得极值，用pop_back()移除极值

sort_heap()
    1. 循环执行vector.size()次pop_heap()即可

make_heap()
    1. 以现有的vector为基础，执行size()次的push_heap()

(4) Heap 没有迭代器

chapter. 4.8 Priority-Queue

底层是个heap

chapter. 4.9 Slist

(1) 单向链表，只提供Forward Iterator
(2) slist只提供push_front()，因此，数据的顺序与插入顺序相反
(3) slist定义了一个单独的head用来定位slist，但是这个head不存储任何数据，实际的head指针在head->next上

---

优秀参考博客

(1) 全文摘录： http://blog.csdn.net/terence1212/article/details/52287762

(2)
精华理解：http://blog.csdn.net/shudou/article/details/10270971

(3) http://www.cnblogs.com/wangkangluo1/archive/2012/11/23/2783877.html