总览

先来看所有的容器

allocator

我们知道，C++在堆上分配内存依赖的是new 和delete

那么new的时候在做什么呢？

先分配一块内存，然后再调用初始化函数

delete的时候也是一样，先调用析构函数，然后释放内存

那么allocator就是把这四个步骤进行了封装

#include <new>// for new
#include <cstddef> //  size_t
#include <climits> // for unit_max
#include <iostream> // for cerr
using namespace std;

namespace SLD {
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;

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

    //申请内存
    pointer allocate(size_type n, const void* hint = 0)
    {
        T* tmp = (T*)(::operator new((size_t)(n * sizeof(T))));
        //operator new 和new operator是不同的
        if (!tmp)
            cerr << "out of memory"<<endl;

        return tmp;

    }

    //释放内存
    void deallocate(pointer p)
    {
        ::operator delete(p);
    }

    //构造
    void construct(pointer p, const T& value)
    {
        new(p) T1(value);
    }

    //析构
    void destroy(pointer p)
    {
        p->~T();
    }

    //取地址
    pointer address(reference x)
    {
        return (pointer)&x;
    }


    const_pointer const_address(const_reference x)
    {
        return (const_pointer)&x;
    }

    size_type max_size() const 
    {
        return size_type(UINT_MAX/sizeof(T));
    }
};
}

vector

对于一条 vector,其标准语句应该为

vetor<int, allocator<int>>

在头文件的定义中，写作如下的形式

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;
    pointer _Mylast;
    pointer _Myend;
};

可以看到，vector拥有这三个迭代器，分别表示vetcor的开头、vetor的结尾、vector当前可用的结尾

vector的扩容是很消耗时间的，因为他需要以下三步

1.完全弃用现有内存空间，重新申请更大内存空间
2.将原内存空间中的数据移动到新的内存空间中去
3.将旧的内存空间释放

当扩容的时候，根据编译器的同，重新决定新容量的大小
如vs2017,扩容因子就是1.5

2. list

没啥好说的，就是linux侵入式链表的逻辑

3. queue和stack

更没啥好说的，给个指针实现就好了
默认情况下是由deque实现的

4.deque

deque的结构如下图所示，可以看到，deque是开辟了一段又一段的连续空间，然后对应有一个数组，里头存的是对应连续空间的首地址

deque有这样四个参数

template<class T,...>
struct __deque_iterator{
    ...
    T* cur;
    T* first;
    T* last;
    map_pointer node;//map_pointer 等价于 T**
}

1.cur：指向当前正在遍历的元素；

2.first：指向当前连续空间的首地址；

3.last：指向当前连续空间的末尾地址；

4.node：它是一个二级指针，用于指向 map 数组中存储的指向当前连续空间的指针。

deque中同样也保存了map数组的起始值和结束值指针

5. priority_queue

内核是由最大最小堆实现的
堆，说白了就是个二叉树，对于最大堆有个特点就是每个节点都比自己的儿子节点要小
这里给一个rust版本的
(https://github.com/Lordworms/interview_shit/blob/main/algorithm/src/heap/heap.rs)

对于堆来说，有以下三种操作

1.插入
插入到数组最后，然后向上调整

2.pop
把最后一个元素和堆顶元素交换，之后向下调整

3.重构
从后往前向上调整或者从前往后向下调整

6.map,set

都由红黑树实现
红黑树的性质
1.每个节点要么是黑色，要么是红色。
2.根节点是黑色。
3.每个叶子节点（NIL）是黑色。
4.每个红色结点的两个子结点一定都是黑色。
5.任意一结点到每个叶子结点的路径都包含数量相同的黑结点
6.根到叶子结点的最长路径不超过最短路径的两倍

红黑树并不是完美平衡二叉树，但是他是完美黑色节点平衡二叉树

有三种操作能让红黑树自平衡
旋转的意义就是把大一些的子树上移，小一些的子树下移
1.左旋

当前节点的左子树

2.右旋

3.变色
不用介绍惹

支持这些操作:
1.查找

2.插入

a.插入节点并把其设置为红色
b.重新染色并且通过自旋来解决冲突
那么包含以下四种场景
a. 当前节点为根

把当前节点染成黑色

b. 当前节点的叔叔节点为红色

对当前节点的叔叔和父亲节点重新染色

c. 当前节点的叔叔节点是黑色(三角形)
旋转其父亲节点(相反方向)

d. 当前节点的叔叔节点是黑色(直线情况)

旋转其祖先节点(相反方向) 并对父亲和祖先节点重新染色

3.删除
对于删除，有这几种情况
a. transplant

用python代码整,很好懂

def transplant(self,u,v):
    if u.parent==None:
        self.root=v
    elif u==u.parent.left:
        u.parent.left=v
    else:
        u.parent.right=v
    v.p=u.p

b. delete

(1)left is nil
只需要调用transplant然后重新染色就好了

(2)right is nil

只需要调用transplant然后重新染色就好了

(3)neither is nil

找对应的右子树的最小节点，然后把该节点当成根，然后删除对应节点，接入本来的节点的父节点中去，并修改颜色

c. delete_fixup
修改对应颜色

6.unordered_map的扩张的方式

在C++ STL中，unordered_map是使用哈希表来实现的，其扩张方式如下：

1.当插入新元素时，如果元素数量已经达到了负载因子(load factor)的阈值，就需要对哈希表进行扩张操作。

2.扩张操作会创建一个新的哈希表，将旧哈希表中的所有元素重新哈希到新哈希表中。

3.扩张后的新哈希表的大小为原哈希表大小的两倍，并重新计算新的负载因子阈值。

4.扩张操作的具体实现可以是：分配新哈希表的空间，将旧哈希表中的所有元素遍历并重新插入到新哈希表中。

7.unordered_map解决冲突的方式

1.链表法（Separate Chaining）：将相同哈希值的元素链接到同一个链表中。当发生哈希冲突时，新元素会被插入到对应的链表中。

2.开放地址法（Open Addressing）：在哈希表中找到一个空闲的位置来存储发生哈希冲突的元素。常见的开放地址法有线性探测、二次探测和双重哈希等。

3.建立更多的桶（Bucket）：增加哈希表的大小，通过增加桶的数量来减少哈希冲突的概率。

在std::unordered_map中，默认使用链表法来解决哈希冲突。当发生哈希冲突时，新元素会被插入到链表的尾部。然而，在某些情况下，链表法可能会导致性能下降，因为链表的遍历和访问操作可能会增加缓存不命中的数量。在这种情况下，可以考虑使用其他的解决哈希冲突的方法，例如开放地址法或二叉树等。可以通过自定义哈希函数和比较函数来实现这些解决哈希冲突的方法。

reference from (https://blog.csdn.net/vjhghjghj/article/details/88647336/?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-0--blog-78110973.pc_relevant_3mothn_strategy_recovery&spm=1001.2101.3001.4242.1&utm_relevant_index=2)

(reference from https://www.jianshu.com/p/e136ec79235c)