大家所熟知的数据容器,包括STL提供的容器,很重要的一部分是与内存管理相关的,也就是说你这个容器要为节点分配内存,你需要提供一系列内存分配的策略来供用户选择。我们从哪里学来的这种数据结构?教科书,产品代码,甚至面试(面试者往往会要求你清楚描述,或者写出内存管理部分的代码)。
在我们为我们的软件提供LIB的时候,这些内存管理部分,总是不停的烦扰我们,因为很多BUG都是因为这部分代码引起的。一部分原因是因为内存管理的代码是最困难的(在C++中),另一方面原因是提供一个或者一系列通用的内存管理策略是很困难的,因为有很多场景,我们无法预料。即使我们提供了扩展性很好的基础架构,我们也不能保证后来者有能力完全理解你原先的代码,并且提供合适的他所需要的策略。
我接下来想要介绍的一系列文章,就是如何设计无内存管理的数据容器。你也许会问,那谁为每个node分配内存?
很好的问题。我们来假设一下,如果没有容器,你的对象如何分配内存?这是每一个类设计者必须考虑的问题,如果你告诉我或者自言自语说,我从来没考虑过这种问题啊?那是因为你都是在用C++提供的默认的内存管理方式-------直接从公共的heap中分配对象,或者从栈中分配对象。但是在很多大型软件中,对于一些关键的数据结构(类),我们总是希望为它提供特殊服务。也就是提供一个快速内存分配和释放的方法(比如独立的memory pool)。这就是所谓的内存分配策略。不同的对象可能有不同的策略,或者从不同的地方,用不同的方式分配内存。所以为容器设计一个通用的内存分配器,是很困难的。
这里我们所要介绍的无内存管理的容器,它的特殊性就是不提供内存分配器,你插入的每个对象就是它的节点,你可以如往常那样设计你的数据结构,而不需要考虑你想使用哪种容器,你所需要做的就是往你的类中添加一个特殊的data member,容器和你的数据结构之间就是依靠这个容器规定的data member联系起来的。这样你可以用你想要的方式为你的数据结构提供内存分配方式。这也就意味着,在一个软件系统中,我们分离了容器和内存管理,这样为我们的设计提供了更高的自由度。
下面是一个简单的例子:
-
template
-
class QueueHeader{
-
-
};
-
template
-
class QueueLinker{
-
};
-
-
-
class MyClass{
-
.................................
-
-
QueueLinker mNext;
-
-
static QueueHeader specialHeader;
-
};
-
-
MyClass::MyClass()
-
{
-
specialHeader.add(this);
-
}
-
-
MyClass::~MyClass()
-
{
-
specialHeader.remove(this);
-
}
-
-
void func()
-
{
-
MyClass o1;
-
MyClass o2 = new MyClass;
-
-
}
接下来,我们会一一介绍如何设计这种无内存分配器的容器。
记住:这种容器的一个最重要的特点就是,被管理对象即节点。
阅读(1762) | 评论(0) | 转发(0) |