STL源码剖析

1. 空间分配器 Allocator

template <class T>
class allocator {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    // rebind allocator of type U
    template <class U>
    struct rebind {
        typedef allocator<U> other;
    };
};

模板类中使用了模板类，使得我们可以通过一个已经实例化的

2. new操作包含了operator new 和 对象构造两部分。在第一部分，需要考虑如下事情：

Alloc使用方式，（看图吧，虽然旧，但还是写得很好的）

3. 一些奇怪的函数写法

首先看下这两个：

char * p[10];指针数组，数组里都是指针
char (*p)[10]; 数组指针，只定义了一个指向数组的指针

对于第一个：char* 是类型。对于第二个，char是类型，从内往外看，p是一个指针，什么样的指针，指向 char [10]这个数组的指针。

然后是这个：

static void (*set_malloc_handler(void (*f)()))()

从内往外看，set_malloc_handler参数为一个函数指针，返回值为一个指针，(此时返回值类型不完整，肯定还需要更多信息获取返回值的类型)，什么样的指针，外层void ()很明显是一个函数，所以是一个指向函数的指针。参考链接

4. 虚函数实现

C++虚函数的实现_c++虚函数实现-CSDN博客

5. destroy函数

trivial destructor函数：不重要的析构函数，

如下两个函数被设计为全局函数

6. if constexpr

• 这是一个编译时条件语句，它在编译时评估条件。
• 如果条件为 true，则编译器会将 if constexpr 块内的代码包含在编译后的程序中。
• 如果条件为 false，则编译器会完全省略 if constexpr 块内的代码，就像它从未存在过一样。
• 因为 if constexpr 是在编译时决定的，所以它可以用来实现模板元编程，以及在编译时消除代码路径，从而优化程序性能。

类似使用方式：std::true_type和std::false_type详解_std::type 比较-CSDN博客

7. 非这本书的，关于stl的知识点都是参考自cplusplus，C++ STL 十六大容器

8. array

   即数组，顺序容器（支持索引随机访问），连续内存（支持通过指针加减，进行访问），固定大小，类模板头：

   template < class T, size_t N > class array;

   不管理内存分配，只有固定内存大小。swap函数对于这个容器来说，会真实的交换两个array的所有元素。虽然 array 和 C++语法中的[]符号无限接近，但两者是两个存在，array 毕竟是标准模板库的一员，是一个class，因此支持begin(), end(), front(), back(), at(), empty(), data(), fill(), swap(), ... 等等标准接口，而[]是真正的最朴素的数组。

9. vector

   与array相同的时，使用的也是连续存储，区别在于会动态的调整存储空间。每次实际分配的空间capacity 大于 容器要求的大小 size。相比于其他容器如deques，lists，vector非常高效因为他就像数组一样，但是对他前半部分的元素进行增删的效率低，

   template < class T, class Alloc = allocator<T> > class vector; // generic template

10. deque

    Double end queue，双端队列，

    序列容器，有动态大小，一般也是以动态数组实现的，支持从头部尾部直接访问以及删除元素。与vector不同的是，不保证元素是连续存储的。虽然vector和deque提供了相似的接口有相似的用途，但两者的内部实现大相径庭，vector内部元素连续存储，deque内部元素可以分散存储，并且记录必要的信息，deque更复杂，这也允许他在面对长序列时更加高效（避免重新分配与迁移数据）

    template < class T, class Alloc = allocator<T> > class deque;

11. list

    （list在c++是链表，在python中是列表）链表是一个序列容器，允许在常数时间内在任何位置上插入删除。底层由双链表实现。与forward_list很像，区别在于forward_list是单链表，换来的是更小的空间。与其他序列容器对比（array, vector and deque），他的优点在于在任何位置插入，移动表现得更好。缺点在于无法顺序访问，以及较低的利用率。

    template < class T, class Alloc = allocator<T> > class list;

12. forward_list

    是序列容器，支持以常数时间在任何地方插入与删除操作。由singly-linked lists实现。

    他的设计目的就是高效，为了高效考虑，他甚至连size函数都没有。

    *template < class T, class Alloc = allocator<T> > class list;*

13. queue

    一种容器适配器,主要为了完成FIFO任务，用一个已经封装好了的类再次进行封装。底层的容器必须包括这些接口empty、size、front、back、push_back、pop_front，只有list和deque满足这些条件，默认用的是deque

    template <class T, class Container = deque<T> > class queue;

14. priority_queue

    优先级队列，也是容器适配器，第一个元素的值永远是最大的。

    类似于堆（其实就是吧），元素可以在任何时候插入，但只有最大的元素能够被访问。内部会自动地维持一个堆结构。

    要求底层的容器支持随机访问，以及有如下的接口empty()、size()、front()、push_back()、pop_back()。vector和deque满足条件，默认用的vector。

15. stack

    后进先出栈，是容器适配器，设计来执行后进先出上下文的元素只能从尾端读写，并且。底层类容器可以是vector，deque，list，默认是deque。（可以用来设计undo操作）

    template <class T, class Container = deque<T> > class stack;

16. map

    前文的都是序列容器，而map是关联容器，存储key和value，元素类型是typedef pair<const Key, T> value_type按照指定顺序存储。在map中，key用来排序以及唯一标识元素，value用来存储值。比起序列容器，通过key访问元素更慢，但可以按照顺序进行遍历。底层通过红黑树实现。

    template < class Key,  //map::key_type           
    class T,                                       // map::mapped_type     class Compare = less<Key>,                     // map::key_compare      class Alloc = allocator<pair<const Key,T> >    // map::allocator_type > class map;

17. multimap

    关联容器，与map的区别在于，可以有多个相同的key，底层也是红黑树。

18. set

    按照一定顺序存储独一无二的元素。底层也是红黑树。允许迭代器++。

19. unordered_map

    底层用hash表存储。这导致了他不支持排序，访问元素更快。

20. unordered_multimap

    允许不同的key

8. copy系列函数

   //copy
   template<class InputIt, class OutputIt>
   OutputIt copy(InputIt first, InputIt last, OutputIt d_first){
       for (; first != last; (void)++first, (void)++d_first)
           *d_first = *first;
       return d_first;
   }

   //copy_if
   template<class InputIt, class OutputIt, class UnaryPred>
   OutputIt copy_if(InputIt first, InputIt last, OutputIt d_first, UnaryPred pred){
       for (; first != last; ++first)
           if (pred(*first)){
               *d_first = *first;
               ++d_first;
           }
       return d_first;
   }

   //copy_backward 从后往前拷贝
   template<class BidirIt1, class BidirIt2>
   BidirIt2 copy_backward(BidirIt1 first, BidirIt1 last, BidirIt2 d_last)
   {
       while (first != last)
           *(--d_last) = *(--last);
       return d_last;
   }

   //copy_n 与copy的区别在于，只是参数变了，作用是一样的
   template<class InputIt, class Size, class OutputIt>
   constexpr //< since C++20
   OutputIt copy_n(InputIt first, Size count, OutputIt result)
   {
       if (count > 0){
           *result = *first;
           ++result;
           for (Size i = 1; i != count; ++i, ++result)
               *result = *++first;
       }
       return result;
   }

9. vector

   一旦引起vector空间变化，他的迭代器就失效了。比如往vector的末尾添加元素时，他的头部迭代器也可能会失效。

   #include <iostream>
   #include <vector>
   using namespace std;
   int main(){
       vector<int> vec{2, 6, 5};
       cout << vec.capacity() << endl;
       vector<int>::iterator iter = vec.begin();
       vec.push_back(4);
       cout << *iter << endl;                                                         return 0;
   }
   3
   =================================================================
   ==1391696==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000010 at pc 0x564f5b1cd7fa bp 0x7fff73d241c0 sp 0x7fff73d241b0

   insert函数，非常有意思，insert(iterator iter, int n, T)

   • 空间足够

     • 插入点之后的元素大于要插入的元素数目（为什么要分两步保存原始元素，而不是一步，第一个原因是待拷贝区域与拷贝区域有交叉，第二个原因是尾部的空间没有被初始化，需要使用uninitialize_copy, 而前面只用copy就行了）

       

     • 插入点之后的元素小于要插入的元素数目

       

   • 空间不够

     

10. list

    list迭代器不能像vector一样使用普通指针作为迭代器，因为他在内存中不保证连续存在。但他有一个重要性质是：插入操作与接合（splice）操作不会导致原有的迭代器失效（这在vector中不成立）。

    这个迭代器的设计思路是：建立一个类，类中包含一个原始指针node，重载++和–操作，让内部的node指针指向(*node).next等。

    list为双向链表，只需要在末尾加上一个空白节点，便符合左闭右开的特点，摇身一变成为last迭代器。

    sort使用的是非递归版本的归并排序：list详解

    void sort() {
            if (head->next == head || head->next->next == head) return;
            list<T, Alloc> carry;//每一归并层之间合并的 “中转站”
            list<T, Alloc> counter[64]; // counter[i]表示第i层《归并层》
            int fill = 0;
            while (!empty()) {//一直输入元素
                carry.splice(carry.begin(), *this, begin());//每次carry首先获取新插入的元素
                int i = 0;
                /*
                每一层从 0->i 归并层进行逐一合并
                */
                while (i < fill && !counter[i].empty()) {
                    counter[i].merge(carry);        //首先把carry 合并到 counter[i]层
                    carry.swap(counter[i++]);   //交由carry临时存储此层归并后的结果
                }
                carry.swap(counter[i]); //将当前处理的结果给到 counnter[i] 层
                if (i == fill) {    //归并层扩容
                    ++fill;
                }
            }
            for (int i = 1; i < fill; ++i) {
                counter[i].merge(counter[i - 1]); //层层归并
            }
            swap(counter[fill - 1]);//最后一层就是答案
        }

11. trick

    对于左闭右开区间[a, b), 他的元素数目是 b - a

    对于左闭右闭区间[a, b], 他的元素数目是 b - a + 1

12. deque

​ deque与vector很大的差异在于，deque可以在常数时间内堆头端元素进行操作，deque内部空间可以是分段的。虽然支持随机访问，当其不是普通指针，相比于vector要复杂很多。（涉及到排序时，可以考虑先将deque复制到vector上，排序后，再复制到deque上，以节约一点开销）

• 迭代器如何进行随机跳转

  self& operator+=(difference_type n) {//difference_type可以看成指针类型，
  	  difference_type offset = n + (cur - first);
  	  if (offset >= 0 && offset < difference_type(buffer_size()))
  	    // 目标位置在同一缓冲区内
  	    cur += n;
  	  else {//offset <= -1 或者 offset >= buffer_size()
  	    // 目标位置不在同一缓冲区内
  	    difference_type node_offset =
  	      offset > 0 ? offset / difference_type(buffer_size())
  	                 : -difference_type((-offset - 1) / buffer_size()) - 1;
  	                 //offset为-1时，(-offset - 1)刚好为0，
  	    // 切换至正确的节点（亦即缓冲区）
  	    set_node(node + node_offset);
  	    // 切换至正确的元素
  	    cur = first + (offset - node_offset * difference_type(buffer_size()));
  	  }
  	  return *this;
  	}

13. 重载箭头运算符C++重载

对于形如point->member的表达式来说，point必须是二者之一：指向类对象的指针、一个重载了operator->() 的类对象

• 如果point是指针，则按照内置的箭头运算符去处理。表达式等价于(*point).member
• 如果point是一个定义了operator->() 的类对象，则point->member等价于point.operator->()->member

14. 优先级队列，由heap实现（heap并不是一个容器）

15. 红黑树 rbt 自平衡的二叉查找树

16. 完全二叉树，没有空隙，因此可以利用列表存储