来，大家看一个单链表~ 推荐，因为内存分配方式很独特哦~

andalousie

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 (); }
                
                iterator  operator + (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;
};

#endif

list.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 [sizeof (Block) + BlockLinks * sizeof (List::Link)];
                // 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

pzhccy

好的，谢谢楼主，我先收藏了

Fly_Sheep

没有注释 看的头大

andalousie

Fly_Sheep 发表于 2014-4-11 03:22

                               
登录/注册后可看大图

没有注释 看的头大

没事，亲，这就注释一下~。不过具体点，请问你需要注释哪儿呢？除了我注释过的，虽然是英文哈~ 我不习惯用中文注释程序。中文解释一般放在程序外面。

Fly_Sheep

andalousie 发表于 2014-4-11 15:58

                               
登录/注册后可看大图

没事，亲，这就注释一下~。不过具体点，请问你需要注释哪儿呢？除了我注释过的，虽然是英文哈~ 我不习惯用 ...

没想到楼主会回复哈 其实注释倒不用多详细 只需在方法前和类前面注释就行了 比如说 这个方法是干什么的 这个字段声明是干嘛的等等

andalousie

Fly_Sheep 发表于 2014-4-12 14:42

                               
登录/注册后可看大图

没想到楼主会回复哈 其实注释倒不用多详细 只需在方法前和类前面注释就行了 比如说 这个方法是干什么的 这 ...

那我简单列述一下吧
ListAllocator类

class Block 用于划分内存块
Newlink申请新的空间给链结构
Purge释放
Recycle回收

List类

List() 构造函数
~List() 析构函数
List::Link 嵌入的类Link声明
List::iterator类 迭代器，就是重载各种运算符的类，表现出来就像指针

这是主要方法的中文名称

simple123

这个必须要看看那啊

cable5881

谢谢楼主分享！！！！！！！！