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

andalousie

List.h

1. #if !defined (LIST_H)
   
2. #define LIST_H
   
3. #include <new>
   
4. 
   
5. class LinkAllocator;
   
6. 
   
7. class List
   
8. {
   
9. public:
   
10.         List ();
    
11.         ~List ();
    
12.         void insert (int value);
    
13.         bool isEmpty() const { return !_pHead; } // conversion to bool
    
14. public:
    
15.         class Link
    
16.         {
    
17.         public:
    
18.                 Link (Link* pNext, int value = -1)
    
19.                         : _pNext (pNext), _value (value) {}
    
20.                 Link *  Next () const { return _pNext; }
    
21.                 void        SetNext (Link * next) { _pNext = next; }
    
22.                 int     GetValue () const { return _value; }
    
23.                 // allocator
    
24.                 void * operator new (std::size_t size);
    
25.                 void   operator delete (void * mem);
    
26.                 static void Purge (); //Purge method is used to release the memory
    
27.         private:
    
28.                 static LinkAllocator _linkAlloc;
    
29.                
    
30.                 Link *  _pNext;
    
31.                 int                _value;
    
32.         };
    
33. public:
    
34.         class iterator
    
35.         {
    
36.         public:
    
37.                 void      operator =  (const iterator& it) { _pLink = it._pLink; }
    
38.                 bool      operator == (const iterator& it) { return _pLink == it._pLink; }
    
39.                 bool      operator != (const iterator& it) { return _pLink != it._pLink; }
    
40.                 iterator& operator ++ () { _pLink = _pLink->Next (); return *this; }
    
41.                 int       operator *  () const { return _pLink->GetValue (); }
    
42.                
    
43.                 iterator  operator + (std::size_t n)
    
44.                 {
    
45.                         iterator tmp = *this;
    
46.                         while(n--) ++tmp;
    
47.                         return tmp;
    
48.                 }
    
49. 
    
50.                 iterator (Link const * p = 0)
    
51.                         : _pLink (p) {}
    
52.                 iterator (const iterator& it)
    
53.                         : _pLink (it._pLink) {}
    
54.         private:
    
55.                 Link const * _pLink; // current link
    
56.         };
    
57. 
    
58.         friend class iterator;
    
59.         iterator begin () { return iterator (_pHead); }
    
60.         iterator end   () { return iterator (0); }
    
61. private:
    
62.         Link const * GetHead () const { return _pHead; }
    
63.         
    
64.         Link * _pHead;
    
65. };
    
66. 
    
67. class LinkAllocator
    
68. {
    
69.         enum { BlockLinks = 4 }; // small value for testing
    
70.         class Block
    
71.         {
    
72.         public:
    
73.                 Block (Block * next): _next (next) {}
    
74.                 Block * Next () { return _next; }
    
75.         private:
    
76.                 Block * _next;
    
77.         };
    
78. public:
    
79.         LinkAllocator () : _p (0), _blocks (0) {}
    
80.         ~LinkAllocator () { Purge (); }
    
81.         void Purge ();
    
82.         void * NewLink ();
    
83.         void Recycle (void * link);
    
84. private:
    
85.         List::Link  * _p;
    
86.         Block * _blocks;
    
87. };
    
88. 
    
89. #endif

复制代码

list.cc

1. #include "List.h"
   
2. #include <cassert>
   
3. #include <iostream>
   
4. 
   
5. LinkAllocator List::Link::_linkAlloc;
   
6. 
   
7. void * List::Link::operator new (std::size_t size)
   
8. {
   
9.         assert (size == sizeof (Link));
   
10.         return _linkAlloc.NewLink ();
    
11. }
    
12. 
    
13. void List::Link::operator delete (void * mem)
    
14. {
    
15.         if (mem)
    
16.                 _linkAlloc.Recycle (mem);
    
17. }
    
18. 
    
19. void List::Link::Purge () { _linkAlloc.Purge (); }
    
20. 
    
21. // List
    
22. 
    
23. List::List ()
    
24.         : _pHead (0)
    
25. {}
    
26. 
    
27. List::~List ()
    
28. {
    
29.         while ( _pHead != 0 )
    
30.         {
    
31.                 Link * pLink = _pHead;
    
32.                 _pHead = _pHead->Next (); // unlink pLink
    
33.                 delete pLink;
    
34.         }
    
35. }
    
36. 
    
37. void List::insert (int value)
    
38. {
    
39.         Link * pLink = new Link (_pHead, value);
    
40.         _pHead = pLink;
    
41. }
    
42. 
    
43. // LinkAllocator
    
44. 
    
45. void * LinkAllocator::NewLink ()
    
46. {
    
47.         if (_p == 0)
    
48.         {
    
49.                 std::cout << "\tAllocating a new block\n";
    
50.                 // use global operator new to allocate a block of links
    
51.                 char * p = ::new char [sizeof (Block) + BlockLinks * sizeof (List::Link)];
    
52.                 // add it to the list of blocks
    
53.                 Block * block = ::new (p) Block (_blocks);
    
54.                 _blocks = block;
    
55.                 // add it to the list of links
    
56.                 p += sizeof (Block);
    
57.                 for (int i = 0; i < BlockLinks; ++i)
    
58.                 {
    
59.                         List::Link * link = ::new (p) List::Link (_p);
    
60.                         _p = link;
    
61.                         p += sizeof (List::Link);
    
62.                 }
    
63.         }
    
64.         void * mem = _p;
    
65.         _p = _p->Next ();
    
66.         std::cout << "\tGetting link from free list\n";
    
67.         return mem;
    
68. }
    
69. 
    
70. void LinkAllocator::Recycle (void * mem)
    
71. {
    
72.         std::cout << "\tReturning link to free list\n";
    
73.         List::Link * link = static_cast<List::Link *> (mem);
    
74.         link->SetNext (_p);
    
75.         _p = link;
    
76. }
    
77. 
    
78. void LinkAllocator::Purge ()
    
79. {
    
80.         std::cout << "\tPurging link allocator\n";
    
81.         while (_blocks != 0)
    
82.         {
    
83.                 // it was allocated as an array of char
    
84.                 char * mem = reinterpret_cast<char *> (_blocks);
    
85.                 _blocks = _blocks->Next();
    
86.                 ::delete [] mem;
    
87.         }
    
88. }

复制代码

测试文件testlist.cpp

1. #include <iostream>
   
2. #include "List.h"
   
3. 
   
4. int main()
   
5. {
   
6.         List list;
   
7.         list.insert (1);
   
8.         list.insert (2);
   
9.         list.insert (5);
   
10.         list.insert (3);
    
11.         std::cout << "List contents:\n";
    
12.         for (List::iterator it = list.begin();
    
13.              it != list.begin() + 2;
    
14.              ++it)
    
15.         {
    
16.                 std::cout << *it << " ";
    
17.         }
    
18.         std::cout << std::endl;
    
19. }

复制代码

输出结果


可以看出链表的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类

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

复制代码

List类

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

复制代码

这是主要方法的中文名称

simple123

这个必须要看看那啊

cable5881

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