高级数据结构_搜索树

发表于2022-03-12更新于2025-11-04阅读次数

内容

  1. 各种搜索树之间的关系
  2. 树式查找的总体构思
  3. 树式查找基本算法与数据结构
  4. 二叉搜索树–基于半线性的树形结构
  5. 我们的理想：兼顾动态修改与静态查找操作效率
  6. 理想平衡
  7. 适度平衡
  8. AVL–平衡二叉搜索树–最坏情况下，单次动态修改和静态查找也均可以在O(logn)时间内完成

本文章的搜索树实现有两种方式

  1. 类C结构体实现方式，自学习实现。
  2. 模板类实现方式，参考邓俊辉的《数据结构_C++语言版_第3版》。

各种搜索树之间的关系

image-20220312143749079

二叉搜索树–类C结构体

节点结构

  • 节点结构
1
2
3
4
5
6
7
8
typedef int KeyType;
typedef struct BstNode
{
	KeyType key;
	BstNode* leftchild;
	BstNode* parent;
	BstNode* rightchild;
}BstNode,*BSTree;
  • Buynode
1
2
3
4
5
6
7
BstNode* Buynode()
{
	BstNode* s = (BstNode*)malloc(sizeof(BstNode));
	if (NULL == s)exit(1);
	memset(s, 0, sizeof(BstNode));
	return s;
}

Insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
BstNode* MakeRoot(KeyType kx)
{
	BstNode* pnode = Buynode();
	pnode->key = kx;
	return pnode;
}
bool Insert(BstNode*& ptr, KeyType kx)
{
	if (ptr == NULL)
	{
		ptr = MakeRoot(kx);
		return true;
	}
	BstNode* p = ptr;	//遍历Node的指针
	BstNode* pa = NULL;	//实时追踪p的parent
	while (p != NULL && p->key != kx)
	{
		pa = p;
		p = kx < p->key ? p->leftchild : p->rightchild;
	}
	/* 实际上不用再判断p->key == kx, 只要p != NULL就说明找到了相等的节点，
	   如果此时p!=NULL的话，上面的while循环的退出就是因为p->key==kx而退出的
	*/
	if (p != NULL /* && p->key == kx */)return false;

	// 此时已经找到要插入的位置
	p = Buynode();
	p->key = kx;
	p->parent = pa;
	// 更新pa的左或右孩子
	if (p->key < pa->key) pa->leftchild = p;
	else pa->rightchild = p;
	return true;
}

代码结构优化–Insert中包含了建根的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool Insert(BstNode*& ptr, KeyType kx)
{
	BstNode* p = ptr;	//遍历Node的指针
	BstNode* pa = NULL;	//实时追踪p的parent
	while (p != NULL && p->key != kx)
	{
		pa = p;
		p = kx < p->key ? p->leftchild : p->rightchild;
	}
	if (p != NULL)return false;

	// 此时已经找到要插入的位置			//其中，包括根为空的情况
	p = Buynode();
	p->key = kx;
	p->parent = pa;
    if(pa == NULL)	//建根的情况
    {
        ptr = p;
    }
    else // 更新pa的左或右孩子
    {
        if(p->key < pa->key)
            pa->leftchild = p;
        else 
            pa->rightchild = p;
    }
    return true;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void InOrder(BstNode* ptr)
{
	if (ptr != NULL)
	{
		InOrder(ptr->leftchild);
		cout << ptr->key << " ";
		InOrder(ptr->rightchild);
	}
}
int main()
{
	BSTree root = NULL;
	int ar[] = { 53,17,78,9,45,65,87,23,81,94,88,100 };
	int n = sizeof(ar) / sizeof(ar[0]);
	for (int i = 0; i < n; ++i)
	{
		cout << Insert(root, ar[i]) << endl;
	}
    InOrder(root);cout << endl;
	return 0;
}

Next & NiceInOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
BstNode* First(BstNode* ptr)
{
	while (ptr != NULL && ptr->leftchild != NULL)
	{
		ptr = ptr->leftchild;
	}
	return ptr;
}
// 找到当前节点的直接后继（按关键码大小）
BstNode* Next(BstNode* ptr)
{
	if (ptr == NULL)return NULL;
    // 存在右分支
	if (ptr->rightchild != NULL)
	{
		return First(ptr->rightchild);
	}
	else // 没有右分支
	{
		BstNode* pa = ptr->parent;
        // 沿着右子树回溯，直到找到自己作为父节点的左子树
        // 这一过程可以用中序遍历的次序解释
        while(pa != NULL && pa->leftchild != ptr)
        {
            ptr = pa;
            pa = ptr->parent;
        }
        return pa;
	}
}
1
2
3
4
5
6
7
8
void NiceInOrder(BstNode* ptr)
{
    for(BstNode* p = First(ptr); p != NULL; p = Next(p))
    {
        cout << p->key << " ";
    }
    cout << endl;
}

Prev & NiceRevInOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
BstNode* Last(BstNode* ptr)
{
	while (ptr != NULL && ptr->rightchild != NULL)
	{
		ptr = ptr->rightchild;
	}
	return ptr;
}
BstNode* Prev(BstNode* ptr)
{
    if(ptr == NULL)return NULL;
    // 存在左分支
    if(ptr->leftchild != NULL)
    {
        return Last(ptr->leftchild);
    }
    else
    {
        BstNode* pa = ptr->parent;
        while(pa != NULL && pa->leftchild != ptr)
        {
            ptr = pa;
            pa = ptr->parent;
        }
        return pa;
    }
}
1
2
3
4
5
6
7
8
void NiceRevInOrder(BstNode* ptr)
{
    for(BstNode* p = Last(ptr); p != NULL; p = Prev(p))
    {
        cout << p->key << " ";
    }
    cout << endl;
}

Remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
bool Remove(BstNode*& ptr, KeyType kx)
{
    if(ptr == NULL)return false;
    BstNode* p = ptr;
    while(p != NULL && p->key != kx)
    {
        p = kx < p->key ? p->leftchild : p->rightchild;
    }
    if(p == NULL)return false;
    
    //双分支的特殊处理，与直接后继节点替换。把删除的目标转向其直接后继节点。进而转为删除单分支节点的情况！
    if(p->leftchild != NULL && p->rightchild != NULL)
    {
        BstNode * psucc = First(p->rightchild);	//succ: successor,后继
        p->key = psucc->key;
        p = psucc;
    } 
    //单分支、叶子通用
    BstNode* pa = p->parent;
    BstNode * newchild = p->leftchild!=NULL ? p->leftchild : p->rightchild;
    
    // 使p与newchild解除关系
    	//维护newchild的parent
    if(newchild != NULL)newchild->parent = pa;
    	//解除p的child关系，由于将被删去，把p的左右孩子置为NULL
    p->rightchild = p->leftchild = NULL;
    
    //此处：维护pa的左右孩子。维护根节点
    //如果删除的是根节点：不维护pa的左右孩子(因为pa为空)，替换root
    if(pa == NULL)	//pa == NULL则说明删除的是根节点
    {
        ptr = newchild;
    }
    else			//删除非根节点的情况，维护pa的左右孩子，不替换root
    {
        // 将newchild替代p的位置
            //删除单分支节点时，newchild为其分支节点；
            //删除叶子节点时，newchild为空。不影响。
        if(pa->leftchild == p)
            pa->leftchild = newchild;
        else
            pa->rightchild = newchild;
    }
    //删除结束
    free(p);
    return true;
}

二叉搜索树–模板类

顺序性

在二叉搜索树（binary search tree）中，处处都满足顺序性：
“任一节点r的左（右）子树中，所有节点（若存在）均不大于（不小于）r”。

image-20220312145342588

为回避边界情况，这里暂且假定所有节点互不相等。

下图左三个示例是二叉搜索树，右三个示例是反例。
image-20220312145511100

当然，在实际应用中，对相等元素的禁止既不自然也不必要。可在代码的基础上继续扩展，使得二叉搜索树的接口支持相等词条的同时并存（习题[7-10]）。在去除掉这一限制之后，图中原先的第一个反例，将转而成为合法的二叉搜索树。

中序遍历序列

下图为二叉搜索树的中序遍历序列，单调增。
image-20220312145818194

顺序性是一项很强的条件。实际上，搜索树中节点之间的全序关系，已完全“蕴含”于这一条件之中。以如上图所示的二叉搜索树为例，只需该树做一次中序遍历，即可将该树转换为一个线性序列，且该序列中的节点严格按照其大小次序排列。

这一现象，并非巧合。借助数学归纳法，可以证明更具一般性的结论：任何一棵二叉树是二叉搜索树，当且仅当其中序遍历序列单调非降。

BST模板类

1
2
3
4
5
6
7
8
9
10
#include "BinTree.h"
template<typename T> class BST : public BinTree<T>
{
protected:
    BinNodePosi(T) _hot;	//"命中"节点的父亲
public:
    virtual BinNodePosi(T) & search(const T& e);	//查找
    virtual BinNodePosi(T) insert(const T& e);		//插入
    virtual bool remove(const T& e);				//删除
};

可见，在继承原模板类BinTree的同时，BST内部也继续沿用了二叉树节点模板类BinNode。按照二叉搜索树的接口规范定义，这里新增了三个标准的对外接口search()、insert()和remove()，分别对应于基本的查找、插入和删除操作。这三个标准接口的调用参数，都是属于元素类型T的对象引用——这正是此类结构“循关键码访问”方式的具体体现。

以后还将以BST为基类，进一步派生出二叉搜索树的多个变种。无论哪一变种，既必须支持上述三个基本接口，同时在内部的具体实现方式又有所不同。因此，它们均被定义为虚成员函数，从而强制要求派生的所有变种，根据各自的规则对其重写。

查找算法及其实现

二叉搜索树的查找算法，亦采用了减而治之的思路与策略，其执行过程可描述为：从树根出发，逐步地缩小查找范围，直到发现目标（成功）或缩小至空树（失败）。

例如，在下图中查找关键码22的过程如下。首先，经与根节点16比较确认目标关键码更大，故深入右子树25递归查找；经比较发现目标关键码更小，故继续深入左子树19递归查找；经再次比较确认目标关键码更大后，深入右子树22递归查找；最终在节点22处匹配，查找成功。
image-20220312152123162

实际上，针对16、25、19的查找，也将经过该路径的某一前缀，成功终止于对应的节点。当然，查找未必成功。比如针对关键码20的查找也会经过同一查找通路并抵达节点22，但在因目标关键码更小而试图继续向左深入时发现左子树为空，至此即可确认查找失败。

（此类空节点通常对应于空孩子指针或引用，也可假想地等效为“真实”节点，后一方式不仅可简化算法描述以及退化情况的处理，也可直观地解释（B-树之类）纵贯多级存储层次的搜索树。故在后一场合，空节点也称作外部节点（external node），并等效地当作叶节点的“孩子”。返里暂采用前一方式，故空节点不在插图中出现。）

一般地，在上述查找过程中，一旦发现当前节点为NULL，即说明查找范围已经缩小至空，查找失败；否则，视关键码比较结果，向左（更小）或向右（更大）深入，或者报告成功（相等）。

对照中序遍历序列可见，整个过程与有序向量的二分查找过程等效，故可视作后者的推广。

searchIn()算法与search()接口

  • searchIn()

    1
    2
    3
    4
    5
    6
    7
    template<typename T>
    static BinNodePosi(T) & searchIn(BinNodePosi(T) & v, const T& e, BinNodePosi(T) & hot)
    {
        if(v==nullptr || (e == v->data)) return v;
        hot = v;
        return searchIn(((e < v->data) ? v->lc : v->rc), e, hot);
    }

  • search()

    1
    2
    3
    4
    5
    template<typename T> BinNodePosi(T) & BST<T>::search(const T& e)
    {
        //返回目标节点位置的引用，以便后续插入、删除操作。
        return searchIn(_root, e, hot = NULL);
    }

语义约定

以上查找算法之所以如此实现，是为了统一并简化后续不同搜索树的各种操作接口的实现。其中的技巧，主要体现于返回值和hot变量（即BinTree对象内部的_hot变量）的语义约定。

  • 若查找成功，则searchIn()以及search()的返回值都将如图左所示，指向一个关键码为e且真实存在的节点；
  • 若查找失败，则返回值的数值虽然为NULL，但是它作为引用将如图右所示，指向最后一次试图转向的空节点。对于后一种情况，不妨假想地将此空节点转换为一个数值为e的哨兵节点——如此，无论成功与否，查找的返回值总是等效地指向“命中节点”。
    image-20220312160254950
  • 在调用searchIn()算法之前，search()接口首先将内部变量_hot初始化为NULL，然后作为引用型参数hot传递给searchIn()。在整个查找的过程中，hot变量始终指向当前节点的父亲。
    因此在算法返回时，按照如上定义，_hot亦将统一指向“命中节点”的父亲。即便在退化的情况下（比如查找终止并返回于树根处），算法searchIn()的输出依然符合以上语义约定。
  • 请注意，_hot节点是否拥有另一个孩子，与查找成功与否无关。查找成功时，节点e可能是
    叶子，也可能是内部节点；查找失败时，假想的哨兵e等效于叶节点，但可能有兄弟。

效率

  • 在二叉搜索树的每一层，查找算法至多访问一个节点，且只需常数时间，故总体所需时间应线性正比于查找路径的长度，或最终返回节点的深度。
  • 在最好情况下，目标关键码恰好出现在树根处（或其附近），此时只需O(1)时间。
  • 然而不幸的是，对于规模为n的二叉搜索树，深度在最坏情况下可达Ω(n)。比如，当该树退化为（接近于）一条单链时，发生此类情况的概率将很高。此时的单次查找可能需要线性时间并不奇怪，因为实际上这样的一棵“二分”搜索树，已经退化成了一个不折不扣的一维有序列表，而此时的查找则等效于顺序查找。
  • 由此我们可得到启示：若要控制单次查找在最坏情况下的运行时间，须从控制二叉搜索树的高度入手。后续将要讨论的平衡二叉搜索树，正是基于这一思路而做的改进。

插入算法及其实现

算法

  • 为了在二叉搜索树中插入一个节点，首先需要利用查找算法search()确定插入的位置及方向，然后才能将新节点作为叶子插入。
  • 以如左图1所示的二叉搜索树为例。若欲插入关键码40，则在执行search(40)之后，如图2所示，_hot将指向比较过的最后一个节点46，同时返回其左孩子（此时为空）的位置。于是接下来如图©所示，只需创建新节点40，并将其作为46的左孩子接入，拓扑意义上的节点插入即告完成。
    image-20220312162256305
  • 不过，为保持二叉搜索树作为数据结构的完整性和一致性，还需从节点_hot（46）出发，自底而上地逐个更新新节点40历代祖先的高度。
  • 接下来若欲插入关键码55，则在执行search(55)之后如图3所示，_hot将指向比较过的最后一个节点53，同时返回其右孩子（此时为NULL）的位置。于是如图4所示，创建新节点55，并将其作为53的右孩子接入。当然，此后同样需从节点_hot出发，逐代更新祖先的高度。

insert()接口的实现

1
2
3
4
5
6
7
8
9
10
11
template<typename T>
BinNodePosi(T) BST<T>::insert(const T& e)
{
    BinNodePosi(T) &x = search(e);	//search的过程中更新了_hot
    if(x!=nullptr)return x;//如果e值在树中已经存在则不插
    
    x = new BinNode<T> (e, _hot);	//创建新节点x：以e为关键码，以_hot为父
    _size++;
    updateHeightAbove(x);			//更新x及其历代祖先的高度
    return x;
}
  • 首先调用search()查找e。若返回位置x非空，则说明已有雷同节点，插入操作失败。否则，
    x必是_hot节点的某一空孩子，于是创建这个孩子并存入e。
  • 按照以上实现方式，无论插入操作成功与否，都会返回一个非空位置，且该处的节点与拟插入的节点相等。如此可以确保一致性，以简化后续的操作。
  • 另外，上面的查找算法中的对“首个节点插入空树”等特殊情况的处理手法与这里的类似，可以认真体会一番。

效率

由上可见，节点插入操作所需的时间，主要消耗于对算法search()及updateHeightAbove()的调用。后者与前者一样，在每一层次至多涉及一个节点，仅消耗O(1)时间，故其时间复杂度也同样取决于新节点的深度，在最坏情况下不超过全树的高度。

删除算法及其实现

为从二叉搜索树中删除节点，首先也需要调用算法BST::search()，判断目标节点是否的确存在于树中。若存在，则需返回其位置，然后方能相应地具体实施删除操作。

image-20220312165938462

单分支情况

以左图1所示二叉搜索树为例，若欲删除节点69，需首先通过search(69)定位待删除的节点69。因该节点的右子树为空，故只需如图2所示，将69替换为64。则拓扑意义上的节点删除即告完成。另外，为保持二叉搜索树作为数据结构的完整性和一致性，还需更新全树的规模记录，释放被摘除的节点69，并自下而上地逐个更新替代节点64历代祖先的高度。注意，首个需要更新高度的祖先58，恰好由_hot指示。

不难理解，对于没有左孩子的目标节点，也可以对称地予以处理。当然，以上同时也已涵盖了左右孩子均不存在的情况（即目标节点为叶子）。

双分支情况

继续上例，设拟再删除二度节点36，如图2所示，首先调用BinNode::succ()算法，找到该节点的直接后继40。然后，只需如图3所示交换二者的数据项即可将后继节点等效地视作待删除的目标节点。不难验证，该后继节点必无左孩子，从而相当于转化为此前相对简单的情况——单分支情况。最后如图4所示，将新的目标节点36替换为其右孩子46。

注意，在互换36和40后，如图3所示，曾经一度并不满足顺序性，但这并不要紧，在按照上述方法完成整个删除动作后，全树的顺序性必然又将恢复。

同样地，除了更新全树规模记录和释放被摘除节点，此时也要更新一系列祖先节点的高度。不难验证，此时首个需要更新高度的祖先53依然恰好由_hot指示。

remove()实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template<typename T>
bool BST<T>::remove(const T& e)
{
    BinNodePosi(T) & x = search(e);
    if(x == nullptr)return false;
    removeAt(x, _hot);
    --_size;
    updateHeightAbove(_hot);
    return true;
}
template<typename T>
static BinNodePosi(T) removeAt(BinNodePosi(T) & x, BinNodePosi(T) & hot)
{
    BinNodePosi(T) w = x;
    BinNodePosi(T) succ = NULL;
    if(!HasLChild(*x))		//若要删除的节点没有左孩子	
        succ = x = x->rc;	//直接将x替换为其右子树
    else if(!HasRChild(*x))	//若右子树为空
        succ = x = x->lc;	//对称地处理，注意：此时succ!=NULL
    else	//双分支情况
    {	//若左右子树均存在，x和其直接后继w互换，w作为实际被delete节点
        w = w->succ();	//寻找x直接后继w -- 只可能发生在x的右子树中
        swap(x->data, w->data);//交换x和w的data
        BinNodePosi(T) u = w->parent;
        ((u == x) ? u->rc : u->lc) = succ = w->rc;
    }
    hot = w->parent;
    if(succ)succ->parent = hot;
    release(w->data);
    release(w);
    return succ;
}

首先调用search()查找e。若返回位置x为空，则说明树中不含目标节点，故删除操作随即可以失败返回。否则，调用removeAt()删除目标节点x。同样，此后还需更新全树的规模，并调用函数updateHeightAbove(_hot)，更新被删除节点历代祖先的高度。

效率

删除操作所需的时间，主要消耗于对search()、succ()和updateHeightAbove()的调用。在树中的任一高度，它们至多消耗O(1)时间。故总体的渐进时间复杂度，亦不超过全树的高度。

Cpp_STL_allocator

发表于2022-03-07更新于2025-11-04阅读次数

内容

  1. 一级配置器和二级配置器的关系
  2. 类型萃取
  3. allocator
  4. __malloc_alloc_template静态成员的类外初始化，其中函数指针尤为麻烦

空间配置器

SGI STL第一级配置器

1
2
template<int inst>
class __malloc_alloc_template{ /*...*/ };
  1. allocate()直接使用malloc()，deallocate()直接使用free()。
  2. 模拟C++的set_new_handler() 以处理内存不足的情况。

SGI STL第二级配置器

1
2
template<bool threads, int inst>
class __default_alloc_template{ /*...*/ };
  1. 维护16个自由串列，负责16种小型区块的此配置能力。内存池以malloc配置而得。如果内存不足，转第一级配置器进行oom处理。
  2. 如果需求区块大于128bayes，转第一级配置器（直接malloc）。

类型萃取

iterator_traits负责萃取迭代器的特性，而SGI的__type_traits把这种技法进一步扩大到迭代器以外的世界。

我们对类型关注的属性有：

  1. has_trivial_default_constructor
  2. has_trivial_copy_constructor
  3. has_trivial_assignment_operator
  4. has_trivial_destructor
  5. is_POD_type

如果某种类型的构造、拷贝、赋值、析构函数是不必要的，那么我们在对这个类型进行以上动作时，就可以采用最原始化、最有效率的措施，如malloc、memcpy等。这就是对类型属性萃取的意义。

1
2
struct __true_type {};
struct __false_type {};

小试牛刀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#pragma once
namespace xcg
{

struct __true_type {};
struct __false_type {};

template<class T>
struct __type_traits
{
	typedef __true_type		this_dummy_member_must_be_first;
	typedef __false_type	has_trivial_default_constructor;
	typedef __false_type	has_trivial_copy_constructor;
	typedef __false_type	has_trivial_assignment_operator;
	typedef __false_type	has_trivial_destructor;
	typedef __false_type	is_POD_type;
};

template<>
struct __type_traits<char>
{
	typedef __true_type		has_trivial_default_constructor;
	typedef __true_type		has_trivial_copy_constructor;
	typedef __true_type		has_trivial_assignment_operator;
	typedef __true_type		has_trivial_destructor;
	typedef __true_type		is_POD_type;
};

template<>
struct __type_traits<int>
{
	typedef __true_type		has_trivial_default_constructor;
	typedef __true_type		has_trivial_copy_constructor;
	typedef __true_type		has_trivial_assignment_operator;
	typedef __true_type		has_trivial_destructor;
	typedef __true_type		is_POD_type;
};

template<class T>
struct __type_traits<T*>
{
	typedef __true_type		has_trivial_default_constructor;
	typedef __true_type		has_trivial_copy_constructor;
	typedef __true_type		has_trivial_assignment_operator;
	typedef __true_type		has_trivial_destructor;
	typedef __true_type		is_POD_type;
};

}

allocator

STL处理内存的三大部分

STL的allocator把分配空间、释放空间分工了。分配是alloc::allocate()负责，释放是alloc::deallocate()负责；对象构建是::construct()负责，对象析构是::delete()负责，new和delete往往是全局函数。

STL标准规格的配置器定义于<memory>中，SGI<memory>内含以下两个文件：

1
2
#include<stl_alloc.h>
#include<stl_construct.h>

实际上，STL除了以上两个重要部分，还有stl_uninitialized.h，是处理大块内存的。

这个切入点，就可以直接把话题导向内存池了，我们可以根据具体类型的构造、析构、赋值函数是否无关紧要而采取最有效率的措施。

空间的配置与释放std::alloc

对象构建前的空间配置、对象析构后的空间释放，两个动作都由<stl_alloc.h>负责。SGI对此的设计哲学如下：

  1. 向system heap申请空间；
  2. 考虑多线程状态；
  3. 考虑内存不足时的应对措施；
  4. 考虑内存碎片问题

对于第四个问题——内存碎片问题，SGI设计了两级配置器。第一级是对于足够大的内存块处理方式。第二级是对于太小的内存块处理方式。这个大小的标准以128bytes为界。

一级配置器：

  1. 直接malloc
  2. 直接free
  3. 模拟c++的set_new_handler处理内存不足情况

二级配置器：

  1. 维护16个自由链表(free lists)，内存池以malloc获取，内存不足则用一级配置器处理。
  2. 如果需求区块大于128bytes，转调用一级配置器。

一级配置器的静态成员及其初始化

先以一个简单的例子说明静态成员的类外初始化。

1
2
3
4
5
6
7
8
9
10
11
class Object
{
private:
    static int num;
    static void (*pfun)();
};

int Object::num = 0;
//void (*pfun)() = nullptr;			//error
//要告诉编译器，pfun来自哪个类。
void (* Object::pfun)() = nullptr;	//correct

其中，template<int inst>代表“非类型”模板，模板中的参数只是用于标识的。

1
2
3
4
5
6
7
8
9
10
11
template<int inst>
class Object
{
private:
    static int num;
    static void (*pfun)();
};
template<int inst>
int Object<inst>::num = 0;
template<int inst>
void (* Object<inst>::pfun)() = nullptr;

alloc类的静态成员

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<int inst>
class __malloc_alloc_template
{
private:
    static void * oom_malloc(size_t n);
    static void * oom_realloc(void * p, size_t new_sz);
    static void (*__malloc_alloc_oom_handler)();
public:
    static void * allocate(size_t n);
    static void deallocate(void * p, size_t n);
    static void * reallocate(void * p, size_t old_sz, size_t new_sz);
    //static ? set_malloc_handler(void (*f)());
    //函数名是set_malloc_handler，参数是一个void(*)()类型的变量，参数名字是f。
    //其欲返回函数指针void (*)()。
    //但是不能这样写：static void(*)() set_malloc_handler(void (*f)());
    //下面是正确写法
    static void(* set_malloc_handler(void(*f)()) ) ();
};
//此时的类外初始化
//__malloc_alloc_template类的私有成员__malloc_alloc_oom_handler
template<int inst>
void(* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = nullptr;

为了解决函数指针类型的可读性问题，使用typedef或using重定义类型名字。瞬间清爽了许多。

1
2
3
4
5
6
7
8
9
class __malloc_alloc_template
{
public:
    using PFUN = void(*)();
private:
    static PFUN __malloc_alloc_oom_handler;
public:
    static PFUN set_malloc_handler(PFUN p);
};

接下来进行类外初始化：

1
2
3
4
5
6
7
8
9
//__malloc_alloc_template类的私有成员__malloc_alloc_oom_handler
template<int inst>
typename __malloc_alloc_template<inst>::PFUN __malloc_alloc_template<inst>::__malloc_alloc_oom_handler = nullptr;
/*
别看名字过长，实际和之前的形式一样。
仿照以下方式写，成员类型+哪个类<T>::成员名 = ...
template<int inst>
int Object<inst>::num = 0;
/*

一级配置器函数实现

函数成员总览：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<int inst>
class __malloc_alloc_template
{
private:
    static void * oom_malloc(size_t n);
    static void * oom_realloc(void * p, size_t new_sz);
    static void (*__malloc_alloc_oom_handler)();
public:
    static void * allocate(size_t n);
    static void deallocate(void * p, size_t n);
    static void * reallocate(void * p, size_t old_sz, size_t new_sz);
public:
    using PFUN = void(*)();
    static PFUN set_malloc_handler(PFUN p);
};

oom_handler

oom_handler，指out of memory时的处理。

1
2
3
4
5
6
static PFUN set_malloc_handler(PFUN p)
{
    PFUN old = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = p;
    return old;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void * oom_malloc(size_t size)
{
    void* result = NULL;
    void (*my_malloc_handler)() = nullptr;
    for(;;) //infinite loop
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
    	if(nullptr == my_malloc_handler)
        {
            __THROW_BAD_ALLOC;
        }
        my_malloc_hanler();
        result = malloc(size);	//after handling, retry to malloc
        if(nullptr != result)
        {
            return result;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void * oom_realloc(void * p, size_t new_sz)
{
    void* result = NULL;
    void (*my_malloc_handler)() = nullptr;
    for(;;) //infinite loop
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
    	if(nullptr == my_malloc_handler)
        {
            __THROW_BAD_ALLOC;
        }
        my_malloc_hanler();
        result = realloc(p, new_sz);	//after handling, retry to malloc
        if(nullptr != result)
        {
            return result;
        }
    }
}

allocate

1
2
3
4
5
6
7
8
9
static void* allocate(size_t size)
{
    void* result = malloc(size);
    if(nullptr == result)
    {
        result = oom_malloc(size);
    }
    return result;
}

对oom_handler的简要测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include"my_alloc.h"

char* chunk1 = (char*)malloc(sizeof(char)*10000000);
void handler1()
{
    if(chunk1!=nullptr)
    {
        free(chunk1);
    }
    chunk1 = nullptr;
    xcg::malloc_alloc::set_malloc_handler(nullptr);
}
int main()
{
    //设置hanler函数
    xcg::malloc_alloc::set_malloc_handler(handler1);
    //尝试申请100个int空间
    //在allocate函数中，可以通过调试器强制将result赋为nullptr则可进行oom处理测试。
    int * p = (int*)xcg::malloc_alloc::allocate(sizeof(int)*100);
    return 0;
}

deallocate

1
2
3
4
static void deallocate(void * p, size_t n)
{
    free(p);
}

reallocate

1
2
3
4
5
6
7
8
9
static void * reallocate(void * p, size_t old_sz, size_t new_sz)
{
    void * result = realloc(p, new_sz);
    if(nullptr == result)
    {
        result = oom_realloc(p, new_sz);
    }
    return result;
}

二级配置器

  • 一级配置器的问题

    • 直接的malloc后的数据上下各有一个越界标记。上越界标记之外还有信息，包括申请了多少字节，还有next域、prev域以便连接到链表中进行内存管理。除此之外可能还有有效/失效(是否释放)的标记。
    • 除了包装信息占空间较多之外，还有malloc时花费的时间也多。这样就造成对于比较小的对象数据在malloc时入不敷出。
    • 结论就是：对于较小数据，适用于内存池来进行内存管理。

  • 对于客户端申请较小空间（128bytes）的具体处理流程：

    1. 每次配置一大块内存，并维护对应的自由链表(free-list)
    2. 下次如果再有相同大小的内存需求，直接从free-list中取出若干小块。
    3. 如果客户端释放小块内存，就由配置器回收到free-list中。所以配置器除了分配空间，还负责回收空间。

  • 为了方便管理，SGI第二级配置器会主动按任何小块内存的内存需求量计算成8的倍数。（比如客户端要求30bytes，则计算为32bytes。

  • 共维护16个free-lists，各自管理大小分别为8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128的小额区块。

  • free-lists的单结点结构如下：

    1
    2
    3
    4
    5
    union obj
    {
        union obj * free_list_link;
        char client_data[1];	//the client sees this
    }

总览

1
2
3
enum { __ALIGN = 8};
enum { __MAX_BYTES = 128};
enum { __NFREELISTS = __MAX_BYTES / __ALIGN};	// 128 / 8 = 16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<bool threads, int inst>	//参数1：是否考虑多线程，参数2：标识
class __default_alloc_template
{
private:
    union obj	/* 只是类型定义 */
    {
        union obj * free_list_link;	//next
        char client_data[1];
    };
private:
    static obj * volatile free_list[__NFREELISTS];//volatile修饰obj*，即free_list数组中对于的数据内容。
    static char* start_free;//每次配置的一大块'内存' 的内存来源的剩余部分的起始
    static char* end_free;	//每次配置的一大块'内存' 的内存来源的剩余部分的末尾
    static size_t heap_size;//上面提到的都是内存来源，而这个内存来源都是从堆区申请的，堆区申请的总空间数要记录在案
    static size_t ROUNT_UP(size_t bytes);
    static size_t FREELIST_INDEX(size_t bytes);	//hash
    static char* chunk_alloc(size_t size, int & nobjs);//size - 对象的大小，nobjs对象的个数
    static void* refill(size_t size);	//重新填充
public:	/* 用户调用 */
    static void* allocate(size_t size);
    static void deallocate(void* p, size_t n);
    static void* reallocate(void* p, size_t old_sz, size_t new_sz);
};

成员初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
// 对free_list[__NFREELISTS]进行初始化。
template<bool threads, int inst> //	1: __default_alloc_template是模板类，需要声明
typename __default_alloc_template<threads, inst>::obj * volatile // 2: obj是__default_alloc_template<threads, inst>类内的类，需要加上“哪个类”，并且要加上"typename"以示"obj"是个类名，而非成员。
    __default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {};	// 3: free_list[__NFREELISTS]是__default_alloc_template<threads, inst>类内的成员，需要加上“哪个类”，但无需加"typename"。
// 对start_free进行初始化
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::start_free = nullptr;
// 对end_free进行初始化
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = nullptr;
// 对heap_size进行初始化
template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

函数实现

准备工作

1
using malloc_alloc = __malloc_alloc_template<0>;

allocate

相当于单链表的头删法，返回删了的节点的地址给用户用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void * allocate(size_t size)
{
    if(size > (size_t)__MAX_BYTES)
    {
        return malloc_alloc::allocate(size);	//转给一级配置器。
    }
    obj * result = nullptr;
    obj * volatile * my_free_list = nullptr;	//是二级指针，要指向obj*
    my_free_list = free_list + FREELIST_INDEX(size);
    result = *my_free_list;
    if(nullptr == result)	//说明此下标处无内存块了，需要申请。
    {
        void * r = refill(ROUND_UP(size));
        return r;
    }
    *my_free_list = result->free_list_link;	//把free_list此下标的指针更新到下一个节点。相当于链表的头删法。
    return result;
}

refill

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static void * refill(size_t size)
{
    int nobjs = 20;
    char * chunk = chunk_alloc(size, nobjs);
    //chunk_alloc运行之后，nobjs值可能发生改变。
    if(1 == nobjs)
    {
        //如果nobjs是1，则说明内存块正好用完，不用再处理后续内存区域的链接、移动
        return chunk;
    }
    
    //接下来，把内存块分崩离析，依次串联。
    obj * volatile * my_free_list = NULL;
    obj * result = (obj*)chunk;
    obj * current_obj = NULL, * next_obj = NULL;
    my_free_list = free_list + FREELIST_INDEX(size);
    *my_free_list = next_obj = (obj*)(chunk+size);
    for(int i = 1; ; ++i)
    {
        current_obj = next_obj;
        next_obj = (obj*)((char*)next_obj + size);
        if(i == nobjs-1)//最后一块
        {
            current_obj->free_list_link = NULL;
            break;
        }
        current_obj->free_list_link = next_obj;
    }
    return result;
}

chunk_alloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
static char* chunk_alloc(size_t size, int & nobjs)
{
    char * result = NULL;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free;
    if(bytes_left >= total_bytes)
    {
        result = start_free;
        start_free = start_free + total_bytes;
        return result;
    }
    else if(bytes_left >= size)
    {
        nobjs = bytes_left / size;
        total = size * nobjs;
        
        result = start_free;
        start_free = start_free + total_bytes;
        return result;
    }
    else //内存不足以分配1个对象，把剩余的插入到其他下标(剩8字节插到0, 16字节插到1, ...)，然后再另外申请一个大的
    {
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        if(bytes_left > 0)
        {
            obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left);
            //头插
            ((obj*)start_free)->free_list_link = *my_free_list;
            *my_free_list = (obj*)start_free;
        }
        //剩余的残存空间 处理完毕，接下来申请大块内存
        start_free = (char*)malloc(bytes_to_get);
        if(NULL == start_free)	//堆区居然没有资源了！无奈之计，只能向比他之后的链表找有无剩余块。
        {
            obj * volatile * my_free_list = NULL;
            for(int i = size; i <= __MAX_BYTES; i += __ALIGN)	//注意，i从size开始，而不一定从最小的块大小8开始，因为找比你小的没有用处。得找大的。
            {
                my_free_list = free_list + FREELIST_INDEX(i);
                obj * p = NULL;
                if(NULL != p)	//找到了比他大的的剩余的了！
                {
                    *my_free_list = (*my_free_list)->free_list_link;
                    start_free = (char*)p;
                    end_free = start_free + i;
                    return chunk_alloc(size, nobjs);
                }
            }
            //如果上面的for循环没能使得其找到合适的内存块，则说明真的是“山穷水尽疑无路”了，只能转1级配置器，抛出异常或者通过handler处理。
            start_free = malloc_alloc::allocate(bytes_to_get);
        }
        end_free = start_free + bytes_to_get;
        heap_size += bytes_to_get;
        return chunk_alloc(size, nobjs);	//递归此函数，相当于重新来一遍流程
    }
}

ROUND_UP & INDEX

1
2
3
4
5
6
7
8
9
10
static size_t ROUNT_UP(size_t bytes)
{
    // 0 -> 0, 1~8 -> 8, 9~16 - > 16, 17~24 -> 24, ...
    return (bytes+ __ALIGN-1) & ~(__ALIGN - 1);
}
static size_t FREELIST_INDEX(size_t bytes)
{
    // 1~8 -> 0, 9~16 -> 1, 17~24 -> 2, ...
    return ((bytes+ __ALIGN-1) / __ALIGN) - 1;
}

测试allocate

1
2
3
4
5
6
#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
#else
typedef __default_alloc_template<0, 0> alloc;
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class T, class Alloc>
class simple_alloc
{
public:
    static T* allocate(size_t n)	//申请n个T对象
    {
        return Alloc::allocate(sizeof(T)*n);
    }
    static T* allocate()
    {
        return Alloc::allocate(sizeof(T));
    }
    void deallocate(T *p, size_t n)
    {
        if(NULL == p)return;
        Alloc::deallocate(p, sizeof(T)*n);
    }
    void deallocate(T* p)
    {
        if(NULL == p)return;
        Alloc::deallocate(p, sizeof(T));
    }
};

引入list进行测试

1
2
3
4
5
6
7
8
9
10
11
12
#include"my_list.h"
using namespace std;
int main()
{
    xcg::my_list<char> mylist;
    
    for(int i = 0; i < 23; ++i)
    {
        mylist.push_back(i + 'a');
    }
    return 0;
}

list构建流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<class _Ty, class _A = xcg::alloc>
class my_list
{
public:
    typedef _Ty							 value_type;
    typedef _Ty&						 reference;
    typedef _Ty*						 pointer;
    typedef const _Ty&					 const_reference;
    typedef const _Ty*					 const_pointer;
    
    typedef _A							 allocator_type;
    typedef xcg::simple_alloc<_Node, _A> data_allocate;		//simple_alloc中使用的是第二个参数的allocate。在这里即使用_A::allocate，默认参数是xcg::alloc，而根据开关语句，若是使用malloc_alloc则为一级配置器，若为default_alloc则用二级配置器。我们默认使用的是__default_alloc_template<0, 0>。
    
public:
    my_list() : _Head(_Buynode()), _Size(0) {}
protected:
    _Nodeptr _Buynode(_Nodeptr _parg = NULL, _Nodeptr _narg = NULL)
    {
        _Nodeptr _S = data_allocate::allocate();
        _Acc::_Prev(_S) = _parg == NULL ? _S : _parg;
        _Acc::_Next(_S) = _narg == NULL ? _S : _narg;
        return _S;
    }
private:
    _Nodeptr _Head;
    size_t _Size;
};

deallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void deallocate(void * p, size_t size)	// n 表示空间大小
{
    if(size > (size_t)__MAX_BYTES)
    {
        malloc_alloc::deallocate(p, size);
        return;
    }
    //归还给配置器
    obj * q = (obj*)p;
    obj * volatile * my_free_list = free_list + FREELIST_INDEX(size);
    //头插
    q->free_list_link = *my_free_list;
    *my_free_list = q;
    return;
}

测试deallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
iterator erase(iterator _P)
{
    _Nodeptr _S = _P++._Mynode();
    _Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
    _Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
    destroy(&_Acc::_Value(_S));	//不删除节点，而是释放value域。
    _Freenode(_);
    
    return _P;
}
void _Freenode(_Nodeptr _P)
{
    data_allocate::deallocate(_P);
}
void pop_back()
{
    erase(--end());
}
void pop_front()
{
    erase(begin());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Object
{
private:
    int value;
public:
    Object(int x = 0) : value(x)
    {
        cout << "create object" << this << endl;
    }
    ~Object()
    {
        cout << "destroy object" << this << endl;
    }
};
int main()
{
    xcg::my_list<Object> objlist;
    for(int i = 0; i < 10; ++i)
    {
        objlist.push_back(Object(i));
    }
    objlist.pop_back();
    return 0;
}

reallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void* reallocate(void * p, size_t old_sz, size_t new_sz)
{
    if(old_sz > (size_t)__MAX_BYTES && new_sz > (size_t)__MAX_BYTES)
    {
        return malloc_alloc::reallocate(p, old_sz, new_sz);
    }
    // old_sz == 20, new_sz == 22	-->24, 24
    if(ROUND_UP(old_sz) == ROUND_UP(new_sz))
    {
        return p;
    }
    // old_sz > 128, new_sz < 128
    // old_sz < 128, new_sz < 128
    // old_sz < 128, new_sz > 128
    size_t sz = old_sz < new_sz ? old_sz : new_sz;
    void * s = allocate(new_sz);
    memmove(s, p ,sz);
    deallocate(p, old, sz);
    return s;
}