allocator

std::allocator

是所有标准库容器默认使用的内存分配器（封装了内存分配策略）。

new把内存分配和对象构造耦合在一起，delete则把内存释放和对象析构耦合在一起。

但是对于内存池等需求，这两个过程应该解耦成两步（内存管理与数据构造）。显然对于容器类型，
在使用reserve扩容时，只是执行了内存分配，不应该进行对象构造。

allocator<T> a;
a.allocate(n); // 分配一段未初始化内存，保存n个T类型
a.construct(p, args); // 在p地址构造一个对象，参数为args
a.destroy(p); // 析构p地址处的对象
a.deallocate(p, n); // 释放从p地址开始的n个T类型

所以可以自己实现一个allocator（比如使用全局静态的buffer）
去替换标准库容器的内存分配逻辑。
list在每次插入时都需要进行内存分配；vector在size达到capacity时需要进行内存重分配。

std::pmr::memory_resource

对内存资源进行抽象，可以提供给std::pmr::polymorphic_allocator进行分配和释放。

allocate();
deallocate();
virtual do_allocate() = 0;
virtual do_deallocate() = 0;

具体的memory_resource类型，即memory_resource的子类，override了纯虚函数。

• std::pmr::monotonic_buffer_resource：仅在析构时释放申请的内存
• std::pmr::unsynchronized_pool_resource：内存池，用于单线程
• std::pmr::synchronized_pool_resource：可以用于多线程，有锁保护
• std::new_delete_resource：使用全局new和delete
• std::null_memory_resource：什么都不干

使用就只需要创建一个内存资源，然后提供给polymorphic_allocator使用即可。
因为在polymorphic_allocator里拿到的是基类指针（即memory_resource *），所以在执行具体的内存管理策略时是
依靠的运行时多态

monotonic_buffer_resource( void* buffer, std::size_t buffer_size,
                           std::pmr::memory_resource* upstream );
// 设置当前的缓冲区为buffer，下一个缓冲区大小为buffer_size，并设置无法分配时的上游内存资源（不传入就是用默认的）
polymorphic_allocator( std::pmr::memory_resource* r );

std::pmr::monotonic_buffer_resource mem;
std::vector<char, std::pmr::polymorphic_allocator<char>> buf{&mem};
std::pmr::vector<char> buf{&mem}; // 上一个的别名形式

placement new

注意operator new可以选择使用在分配失败时抛出异常的版本还是返回空指针的版本。

实际上operator new只是分配内存（大概率是调用了malloc），且可以被重载，并加入其它形参。

void *A::operator new(size_t ); // operator new
void *operator new(size_t, void *)

new operator首先调用operator new分配空间，然后转换成所需类型的指针后调用相关对象的构造函数（即调用placement new），并返回指针。
不能重载，其行为不能也不应被改变。

所以new其实也是有分配内存（operator new）和构造对象（placement new）两步构成的。

placement new是对operator new的一个全局重载，忽略size_t参数，
仅在传入的地址上执行构造函数创建对象，并返回地址。

注意在使用完后需要自行调用析构函数销毁。

new (ptr) T(1)：operator new的额外参数加在new后面的括号里

内存分配器

目标：解决内部碎片（一个page内没用完）、外部碎片（申请大page时，连续的小page没法用）

链表：first fit, next fit, best fit

buddy（用多个链表分别维护不同的2的幂次的内存块，有时会进行合并或分裂，有效减缓外部碎片）

slab（在buddy的基础上，对小内存分配进行优化，进一步减缓内部碎片）

jemalloc进一步分为small、large、huge三种场景。

• arena：用于内存分配，每个CPU会绑定若干arena
• tcache：每个线程私有的缓存

重要的tricks：

• boudary tags：每个块之前和之后都有meta信息（该块的大小；如果该块被使用，末尾的meta信息可以被覆盖掉），这样可以从任意一个块往前或往后遍历，还可以合并连续的块。
• binning：相同大小的块放在一个bin里，用链表串联。
• caching：延迟空闲块的合并、提前空闲块的分裂