1、内存分配每一层面

C++ Applications->
C++ Library(std::allocator)->
C++ primitives(new,new[],new(),::operator new(),...)->
CRT(malloc/free)->
O.S.API(such as HeapAlloc,VirtualAlloc,...)用法：
void* p1 = malloc(512);	// 512bytes
free(p1);void* p2 = ::operator new(512);	// 512bytes
::operator delete(p2);::operator new()底层实现就是调用了malloc。
::operator delete()底层实现就是调用了free。#ifdef __MSC_VERint* p3 = allocator<int>().allocate(3, (int*)0);	// 分配3个intsallocator<int>().deallocate(p3,3);
#endif
#ifdef __GNUC__void* p4= alloc::allocate(512);	// 512bytes.旧版本G2.9alloc::deallocate(p4,512);void* p5 = allocator<int>().allocate(3);	// 分配3个ints.新版本allocator<int>().deallocate((int*)p5,3);void* p6 = __gnu_cxx::__pool_alloc<int>().allocate(3);	// 分配3个ints.新版本__gnu_cxx::__pool_alloc<int>().deallocate((int*)p6,3);
#endif方式p5和方式p6是gnuc的两种分配器方式，事实上gnuc有七八个分配器。

2、C++ 表达式new和delete不可重载，C++ 函数::operator new()和::operator delete()可以重载。

3、表达式new实际上是做了下面3个语句的事情：

Complex* pc = new Complex(1,2);
编译器转为:
Complex* pc;
try
{void* mem = operator new(sizeof(Complex));	// operator new里面调用的就是mallocpc = static_cast<Complex*>(mem);pc->Complex::Complex(1,2);	// 注意只有部分编译器(VC6)可以这样调用ctor.
}
catch(std::bad_alloc)
{// 若allocation失败就不执行ctor
}注：如果要直接调用ctor，可运用placement new：
new(p)Complex(1,2);

4、表达式delete实际上是做了下面2个语句的事情：

delete pc;
编译器转为:
pc->~Complex();			// 先调用析构函数
operator delete(pc);	// 然后再释放内存。operator delete里面调用的就是free

5、array new

Complex* pca = new Complex[3];
调用3次ctor(默认构造函数)。
无法给参数初始值。

6、array delete

delete[] pca;
调用3次dtor。

• 如果没有写中括号，只会调用1次dtor。

• 对于class without ptr member可能没影响。

• 对于class with pointer member通常有影响。

• 如果array new的是一个non-trivial dtor的类，则pca指向的地址就是一个元素的地址；

• 否则，如果new的是一个trivial dtor的类，编译器会在放元素的前面用一个4个字节记录数组的大小，则当delete pca的时候，

• 编译器不知道delete pca原来是需要delete掉数组的，那么此时编译器去delete掉记录了数组大小的那4个字节就会有问题。

• vc debug环境下会运行时报错。

7、placement new的一种用法：

class A
{
public:int id;A() : id(0) {}A(int i) : id(i) {}~A() {}
}A* buf = new A[3];	// 调用了3次ctor A()
A* tmp = buf;// 在tmp所在的位置调用ctor(在这个定点new上创建对象)
for(int i=0; i<3; ++i)new(tmp++)A(i);		// 调用了3次ctor A(int i)

8、placement new允许我们将object构建于allocated memory中。

没有所谓的placement delete，因为placement new根本没有分配memory。

char* buf = new char[sizeof(Complex)*3];
Complex* pc = new(buf)Complex(1,2);
编译器转为：
Complex* pc;
try
{void* mem = operator new(sizeof(Complex), buf);	// operator new()里面啥也没做，直接返回bufpc = static_case<Complex*>(mem);pc->Complex::Complex(1,2);
}
catch(std::bad_alloc)
{// 若allocation失败就不执行ctor
}注意，关于 placement new 或指new(p)，或指::operator new(size,void*);

9、placement new 也可以重载。

• 我们可以重载class member operator new()，写出多个版本，前提是每一版本的声明都必须有独特的参数列，
  其中第一参数必须是size_t，其余参数以new所指定的placement arguments为初值。
  出现于new(…)小括号内的便是所谓placement arguments。

• 我们也可以(并不是必须，所以也可以没有)重载class member operator delete()，写出多个版本。但它们绝不会被delete调用。
  只有当new所调用的ctor抛出exception，才会调用这些重载版的operator delete()。
  它只可能这样被调用，主要用来归还未能完全创建成功的object所占用的memory。

• 即使operator delete(…)未能一一对应于operator new(…)，也不会出现任何报错(VC6会有警告)。(编译器认为你是要放弃处理ctor发出的异常)

10、placement new在标准库string的一个使用例子——basic_string使用new(extra)扩充申请量：

template<...>
class base_string
{inline static void* operator new(size_t, size_t);	// 第一个参数是类的大小，必须的。第二个是placement new的参数
}xxxx xxxxx::operator new(size_t s, size_t extra)
{return Allocator::allocate(s + extra*sizeof(charT));
}size_t extra = xxxxx;
Rep *p = new(extra)Rep;		// 此处传参extra正是传给operator new的第二个参数extra那块内存正是string用来做引用计数的。

11、连续创建几个只有8个字节大小的对象，如果使用自己预先申请到的一大片内存的方式，那就没有cookie(但这大块内存的上下还是有cookie的)，每个对象的地址间隔(一般,因为malloc拿到的内存可能是分散的)是8字节。

但是如果是没有使用自己的内存池，那么每个对象的地址间隔是16字节，在内存布局上是上下各多了4个字节的cookie。

12、设计内存池时的一种巧妙的手法——这种技术称为embedded pointers(嵌入式指针)：

class A*
{
private:struct ARep{unsigned long miles;char type;}
private:union			// sizeof(A)是8字节 {ARep rep;	// 8个字节A* next;	// 4个字节，所以只要union中的前4个字节当做指针来用}
}

在operator new()里面用union里面的next来存放下一个内存块的地址，返回一个内存块的地址时，外面又可以在这块内存存放数据。(假设这里的内存池是用链表来设计的)

常见的类都是大于等于4个字节的，因此借用前4个字节来当链表指针用是没有问题的。

上面的版本独立出allocator来就是:

class allocator
{
private:struct obj{struct obj* next;		}
}另外，
void* A::operator new(size_t size)
{if(size != sizeof(A))		// 当有继承的时候,大小不等return ::operator new(size);...
}

13、macro for static allocator

#define IMPLEMENT_POOL_ALLOC(class_name) \ 
allocator class_name::myAlloc;class Foo
{...
}
IMPLEMENT_POOL_ALLOC(Foo)

14、当operator new没能力为你分配出你所申请的memory，会抛出一个std::bad_alloc exception。可以令编译器这么做：

new(nothrow)Foo;

C++会在抛出exception之前会先(不止一次)调用一个可由client指定的handler，以下是new handler的形式和设定方法：

typedef void（*new_handler)();
new_handler set_new_handler(new_handler p)throw();

设计良好的new handler只有两个选择：

• 让更多的memory可用
• 调用abort()或exit()

void noMoreMemory()
{abort();
}void main()
{set_new_handler(noMoreMemory);
}

15、=default、=delete

• operator new：不支持default、支持delete
• operator new[]：支持delete
• operator delete：不支持default、支持delete
• operator delete[]：支持delete

这里说的支持，是指类这样定义能编译通过，但是使用该类的时候还是用不了。

16、标准库std::allocator的实现每个编译器厂家可能都不一样。

• VC6的allocator，内部没有做任何的内存管理，只是以::operator new和::operator delete完成allocate()和deallocate()，没有任何特殊设计。

• BC5的allocator只是以::operator new和::operator delete完成allocate()和deallocate()，没有任何特殊设计。

• G2.9的allocator只是以::operator new和::operator delete完成allocate()和deallocate()，没有任何特殊设计。
  G2.9容器使用的分配器，不是std::allocator而是std::alloc。

• G4.9标准库中有许多extended allocators，其中__gnu_cxx::__pool_alloc就是G2.9的alloc。
  allocator是标准分配器。

• G4.9的allocator只是以::operator new和::operator delete完成allocate()和deallocate()，没有任何特殊设计。

17、mingw5.3.0中的std::map源码跟踪如下：

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map
{...
}template<typename _Tp>
class allocator: public __allocator_base<_Tp>
{...
}template<typename _Tp>
using __allocator_base = __gnu_cxx::new_allocator<_Tp>;template<typename _Tp>
class new_allocator
{...// NB: __n is permitted to be 0.  The C++ standard says nothing// about what the return value is when __n == 0.pointerallocate(size_type __n, const void* = 0){ if (__n > this->max_size())std::__throw_bad_alloc();return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));}// __p is not permitted to be a null pointer.voiddeallocate(pointer __p, size_type){ ::operator delete(__p); }...
}

18、G2.9 std::alloc运行模式

• 16条链表(称为freelist-自由链表)，每条的节点内存大小间隔8个字节。所以，第一条链表节点内存大小是8字节，最后一条是128字节。

• 标准库每次申请一大块内存是20size。
  其实是202size+RoundUp(累计申请量>>4)，但是只用了前20个，后20个的话是备用(其实是先全部放入备用池，然后再取20个出来用)。
  备用是留给下一次申请内存的时候用，但不一定是当前那条链表。当备用用完后，下一次再申请内存的时候又是202size。
  另外，当备用内存很多，而申请的内存很小的时候，则申请20个，因为申请的个数是1-20之间。RoundUp(累计申请量/16)是追加量，上调至16的倍数。
  当备用内存很少，而申请的内存很大(备用内存不足以分配一个)的时候，会先将备用池的剩余量(碎片)分配给对应大小的链表。然后备用池剩余量为0了，再去申请202*size+RoundUp(累计申请量>>4)的内存。

• 当系统内存不足时，alloc先会从手中资源最接近申请内存大小(即仅比申请大小大一点点的有空闲内存个数的链表)的链表中回填一个内存给备用池，然后再从备用池中切出一块给申请内存的用户。
  比申请大小大的所有链表都没有空闲的内存个数时，则分配内存失败。

• volatile关键字用于多线程。

19、VC6的malloc

SBH:Small Block Heap

VC6里面有小区块内存的内存管理。VC10不再有，因为已经搬到操作系统的HeapAlloc函数里面去了。

初始化：mainCRTStartup() -> _heap_init() -> __sbh_heap_init()

第一次分配内存：mainCRTStartup() -> _ioinit() -> malloc()/_malloc_dbg() -> _heap_alloc_dbg() -> _heap_alloc_base() -> _sbh_alloc_block()

_malloc_dbg是debug模式下调用的申请内存的函数，有额外的debug header开销(夹着一个_CrtMemBlockHeader结构体)。

debug模式下：所有经过malloc拿到的内存块，都被sbh登记起来(链表串起来)。同时也正因为debug header的存在，debug模式很厉害，可以追踪内存的变化等等。

debug header里面有个字段是记录这内存是用来干什么的，比如在main函数正式开始前的那些叫CRT_BLOCK，main函数过程中的是NORMAL_BLOCK，则main函数结束的那一刻，如果还有标记为NORMAL_BLOCK的内存块(但此时还有标记为CRT_BLOCK的内存块)，则就是内存泄漏了。

SBH的内存管理其实就是分段管理，每段32KB。分段管理的好处是利于归还给操作系统，归还的时候可以归还某一段。
每段32KB，分为8个page，每个页4KB。

GCC的malloc和VC6的malloc的设计大概差不多，都是有上下cookie。

20、内存块上下cookie的作用之一：上下内存块的合并。

21、gcc allocator的内存管理不是为了速度快，是为了去除cookie。malloc的速度已经够快了，因为malloc内部实现也是个内存池。

22、loki allocator的内存回收与VC6的malloc内存回收都有延缓归还内存的设计。

loki allocator使用“以array取代list，以index取代pointer”的特殊实现手法。

loki allocator能够以很简单的方式判断“chunk全回收”进而将memory归还给操作系统。(记录可用区块的个数是否等于总个数)

23、VS2013的标准分配器

• deallocate()其实是直接调用::operator delete()
• allocate()其实是直接调用::operator new()

24、G4.9的标准分配器

• deallocate()其实是直接调用::operator delete()
• allocate()其实是直接调用::operator new()

25、G4.9的malloc_allocator

• deallocate()其实是直接调用std::free()
• allocate()其实是直接调用std::malloc()

头文件在./ext/malloc_allocator.h

26、G4.9的array_allocator

• array_allocator并不会回收已给出的内存空间。
• array_allocator的deallocate()啥也没做。

27、G4.9的debug_allocator

附带额外的空间用以记录整个内存块的大小。

28、G2.9分配器那套称为SGI style的，因为那一套是从SGI买过来的。

欲使用std::allocator以外的allocator，必须自行#include<ext/...>
例如：#include <ext/pool_allocator.h>
vector<int, __gnu_cxx::__pool_alloc<int>> vecPool;

29、G4.9的bitmap_allocator

头文件在./ext/bitmap_allocator.h

为一次只要一个元素大小内存的容器服务(其实所有容器都是一次只要一个元素)。

bitmap_allocator的每一大块(super block)有类型的定义，即不同的value type即使大小相同也不混用。

bitmap_allocator也有延缓归还内存的设计，当超过64个空闲块的时候，归还最大的那块。

30、const member functions(常量成员函数)，const告诉编译器该函数只读成员数据。

const对象不能调用非const成员函数。所以当一个成员函数明明是不会改动data members的，却没有修饰为const时，用const对象去调用就会报错，但这不应该。

const对象其data members不得改动。

当成员函数的const和non-const版本同时存在，const object只会(只能)调用const版本，non-const object只会(只能)调用non-const版本。

函数重载是不管return type的，但const是函数签名的一部分。

在设计类的时候，不改变data members的成员函数应该加const。

31、标准库string的拷贝(里面有引用计数)也是共享一份的、copy on write的。