来，大家看一个单链表~ 推荐，因为内存分配方式很独特哦~
本帖最后由 andalousie 于 2014-4-11 16:10 编辑List.h#if !defined (LIST_H)
#define LIST_H
#include <new>
class LinkAllocator;
class List
{
public:
List ();
~List ();
void insert (int value);
bool isEmpty() const { return !_pHead; } // conversion to bool
public:
class Link
{
public:
Link (Link* pNext, int value = -1)
: _pNext (pNext), _value (value) {}
Link *Next () const { return _pNext; }
void SetNext (Link * next) { _pNext = next; }
int GetValue () const { return _value; }
// allocator
void * operator new (std::size_t size);
void operator delete (void * mem);
static void Purge (); //Purge method is used to release the memory
private:
static LinkAllocator _linkAlloc;
Link *_pNext;
int _value;
};
public:
class iterator
{
public:
void operator =(const iterator& it) { _pLink = it._pLink; }
bool operator == (const iterator& it) { return _pLink == it._pLink; }
bool operator != (const iterator& it) { return _pLink != it._pLink; }
iterator& operator ++ () { _pLink = _pLink->Next (); return *this; }
int operator *() const { return _pLink->GetValue (); }
iteratoroperator + (std::size_t n)
{
iterator tmp = *this;
while(n--) ++tmp;
return tmp;
}
iterator (Link const * p = 0)
: _pLink (p) {}
iterator (const iterator& it)
: _pLink (it._pLink) {}
private:
Link const * _pLink; // current link
};
friend class iterator;
iterator begin () { return iterator (_pHead); }
iterator end () { return iterator (0); }
private:
Link const * GetHead () const { return _pHead; }
Link * _pHead;
};
class LinkAllocator
{
enum { BlockLinks = 4 }; // small value for testing
class Block
{
public:
Block (Block * next): _next (next) {}
Block * Next () { return _next; }
private:
Block * _next;
};
public:
LinkAllocator () : _p (0), _blocks (0) {}
~LinkAllocator () { Purge (); }
void Purge ();
void * NewLink ();
void Recycle (void * link);
private:
List::Link* _p;
Block * _blocks;
};
#endiflist.cc#include "List.h"
#include <cassert>
#include <iostream>
LinkAllocator List::Link::_linkAlloc;
void * List::Link::operator new (std::size_t size)
{
assert (size == sizeof (Link));
return _linkAlloc.NewLink ();
}
void List::Link::operator delete (void * mem)
{
if (mem)
_linkAlloc.Recycle (mem);
}
void List::Link::Purge () { _linkAlloc.Purge (); }
// List
List::List ()
: _pHead (0)
{}
List::~List ()
{
while ( _pHead != 0 )
{
Link * pLink = _pHead;
_pHead = _pHead->Next (); // unlink pLink
delete pLink;
}
}
void List::insert (int value)
{
Link * pLink = new Link (_pHead, value);
_pHead = pLink;
}
// LinkAllocator
void * LinkAllocator::NewLink ()
{
if (_p == 0)
{
std::cout << "\tAllocating a new block\n";
// use global operator new to allocate a block of links
char * p = ::new char ;
// add it to the list of blocks
Block * block = ::new (p) Block (_blocks);
_blocks = block;
// add it to the list of links
p += sizeof (Block);
for (int i = 0; i < BlockLinks; ++i)
{
List::Link * link = ::new (p) List::Link (_p);
_p = link;
p += sizeof (List::Link);
}
}
void * mem = _p;
_p = _p->Next ();
std::cout << "\tGetting link from free list\n";
return mem;
}
void LinkAllocator::Recycle (void * mem)
{
std::cout << "\tReturning link to free list\n";
List::Link * link = static_cast<List::Link *> (mem);
link->SetNext (_p);
_p = link;
}
void LinkAllocator::Purge ()
{
std::cout << "\tPurging link allocator\n";
while (_blocks != 0)
{
// it was allocated as an array of char
char * mem = reinterpret_cast<char *> (_blocks);
_blocks = _blocks->Next();
::delete [] mem;
}
}测试文件testlist.cpp#include <iostream>
#include "List.h"
int main()
{
List list;
list.insert (1);
list.insert (2);
list.insert (5);
list.insert (3);
std::cout << "List contents:\n";
for (List::iterator it = list.begin();
it != list.begin() + 2;
++it)
{
std::cout << *it << " ";
}
std::cout << std::endl;
}输出结果
可以看出链表的allocator通过整体性的Block分配内存，然后切割分给Link使用。用完后先由allocator的Recycle方法回收，最后由析构函数统一调用Purge方法释放。增加了效率。
链表的iterator本人只写出了正向的，因为是单链表；如果是像标准库里面一样，双向链表，就可以用prev指针来实现逆向迭代了。讲述到此完毕，请支持！！
其中空间配置器参考了http://www.drdobbs.com/a-quick-and-simple-memory-allocator/184403440 好的，谢谢楼主，我先收藏了 没有注释 看的头大 本帖最后由 andalousie 于 2014-4-11 16:13 编辑
Fly_Sheep 发表于 2014-4-11 03:22 static/image/common/back.gif
没有注释 看的头大
没事，亲，这就注释一下~。不过具体点，请问你需要注释哪儿呢？除了我注释过的，虽然是英文哈~ 我不习惯用中文注释程序。中文解释一般放在程序外面。 andalousie 发表于 2014-4-11 15:58 static/image/common/back.gif
没事，亲，这就注释一下~。不过具体点，请问你需要注释哪儿呢？除了我注释过的，虽然是英文哈~ 我不习惯用 ...
没想到楼主会回复哈 其实注释倒不用多详细 只需在方法前和类前面注释就行了 比如说 这个方法是干什么的 这个字段声明是干嘛的等等 Fly_Sheep 发表于 2014-4-12 14:42 static/image/common/back.gif
没想到楼主会回复哈 其实注释倒不用多详细 只需在方法前和类前面注释就行了 比如说 这个方法是干什么的 这 ...
那我简单列述一下吧
ListAllocator类class Block 用于划分内存块
Newlink申请新的空间给链结构
Purge释放
Recycle回收List类List() 构造函数
~List() 析构函数
List::Link 嵌入的类Link声明
List::iterator类 迭代器，就是重载各种运算符的类，表现出来就像指针
这是主要方法的中文名称
这个必须要看看那啊 谢谢楼主分享！！！！！！！！
页:
[1]