简单的allocator应用

andalousie

前些日子，我曾经在数据结构与算法板块发表过一篇《来，大家看一个单链表~ 推荐，因为内存分配方式很独特哦~》里面用到了简单的allocator，我习惯叫她空间配置器。那么这几天我把它略微泛化了一下，用到了上面那篇文章里面和我以前写过自己的str.h里面都还可以。大家可以对比一下和原来两篇文章里面的不同。
首先是链表的代码。
allocator.h

1. #if !defined (BASE_ALLOCATOR)
   
2. #define BASE_ALLOCATOR
   
3. #include <cstddef>
   
4. #include <new>
   
5. 
   
6. template<typename T>
   
7. class Allocator
   
8. {
   
9.         enum { BlockLinks = 4 }; // small value for testing
   
10.         class Block
    
11.         {
    
12.         public:
    
13.                 Block (Block * next): _next (next) {}
    
14.                 Block * Next () { return _next; }
    
15.         private:
    
16.                 Block * _next;
    
17.         };
    
18. public:
    
19.         typedef T value_type;
    
20.         typedef value_type* pointer;
    
21.         class Pool
    
22.         {
    
23.         public:
    
24.                 Pool (Pool * next): _next (next) {}
    
25.                 pointer val;
    
26.                 Pool * _next;
    
27.         };
    
28. 
    
29.         Allocator ()
    
30.                 : _blocks (0), _size(BlockLinks * sizeof(value_type)) {}
    
31.         ~Allocator () { deallocate (); }
    
32.         void deallocate ();
    
33.         void * allocate ();
    
34.         void recycle (void * mem);
    
35. private:
    
36.         Block * _blocks;
    
37.         Pool  * _p;
    
38.         size_t   _size;
    
39. };
    
40. 
    
41. template<typename T>
    
42. inline void * Allocator<T>::allocate ()
    
43. {
    
44.         if (_p == 0)
    
45.         {
    
46.                 // use global operator new to allocate a block of links
    
47.                 char * p = ::new char [sizeof (Block) + BlockLinks * sizeof (List::Link)];
    
48.                 // add it to the list of blocks
    
49.                 Block * block = ::new (p) Block (_blocks);
    
50.                 _blocks = block;
    
51.                 // add it to the list of links
    
52.                 p += sizeof (Block);
    
53.                 for (int i = 0; i < BlockLinks; ++i)
    
54.                 {
    
55.                         Pool * link = ::new (p) Pool (_p);
    
56.                         _p = link;
    
57.                         p += sizeof (Pool);
    
58.                 }
    
59.         }
    
60.         void * mem = _p;
    
61.         _p = _p->_next;
    
62.         return mem;
    
63. }
    
64. 
    
65. template<typename T>
    
66. inline void Allocator<T>::deallocate ()
    
67. {
    
68.         while (_blocks != 0)
    
69.         {
    
70.                 // it was allocated as an array of char
    
71.                 char * mem = reinterpret_cast<char *> (_blocks);
    
72.                 _blocks = _blocks->Next();
    
73.                 ::delete [] mem;
    
74.         }
    
75. }
    
76. 
    
77. template<typename T>
    
78. inline void Allocator<T>::recycle(void * mem)
    
79. {
    
80.         Pool * link = static_cast<Pool *> (mem);
    
81.         link->_next = _p;
    
82.         _p = link;
    
83. }
    
84. #endif

复制代码

List.h //去掉了原来的List.cpp实现文件

1. #if !defined (LIST_H)
   
2. #define LIST_H
   
3. #include <new>
   
4. #include <cassert>
   
5. #include "allocator.h"
   
6. 
   
7. /*** Add this on VC6.0 */
   
8. namespace std
   
9. {
   
10.         using ::size_t;
    
11. }
    
12. 
    
13. class List
    
14. {
    
15. public:
    
16.         List ();
    
17.         ~List ();
    
18.         void insert (int value);
    
19.         List* del_front ();
    
20.         void merge (List& x);
    
21.         void swap (List& x);
    
22.         int  size () { return _size; }
    
23.         bool isEmpty() const { return !_pHead; } // conversion to bool
    
24. public:
    
25.         class Link
    
26.         {
    
27.         public:
    
28.                 Link (Link* pNext, int value = -1)
    
29.                         : _pNext (pNext), _value (value) {}
    
30.                 Link *  Next () const { return _pNext; }
    
31.                 void        SetNext (Link * next) { _pNext = next; }
    
32.                 int     GetValue () const { return _value; }
    
33.                 // allocator
    
34.                 void * operator new (std::size_t size);
    
35.                 void   operator delete (void * mem);
    
36.                 static void Purge ();
    
37.         private:
    
38.                 static Allocator<Link> _linkAlloc;
    
39.                
    
40.                 Link *  _pNext;
    
41.                 int                _value;
    
42.         };
    
43. public:
    
44.         class iterator
    
45.         {
    
46.                 friend class List;
    
47.         public:
    
48.                 void      operator =  (const iterator& it) { _pLink = it._pLink; }
    
49.                 bool      operator == (const iterator& it) { return _pLink == it._pLink; }
    
50.                 bool      operator != (const iterator& it) { return _pLink != it._pLink; }
    
51.                 iterator& operator ++ () { _pLink = _pLink->Next (); return *this; }
    
52.                 int       operator *  () const { return _pLink->GetValue (); }
    
53.                
    
54.                 iterator  operator + (std::size_t n)
    
55.                 {
    
56.                         iterator tmp = *this;
    
57.                         while(n--) ++tmp;
    
58.                         return tmp;
    
59.                 }
    
60. 
    
61.                 iterator (Link * p = 0)
    
62.                         : _pLink (p) {}
    
63.                 iterator (const iterator& it)
    
64.                         : _pLink (it._pLink) {}
    
65.         protected:
    
66.                 Link * _pLink; // current link
    
67.         };
    
68. 
    
69.         friend class iterator;
    
70.         iterator begin () { return iterator (_pHead); }
    
71.         iterator end   () { return iterator (0); }
    
72. private:
    
73.         List::Link const * GetHead () const { return _pHead; }
    
74.        
    
75.         List::Link * _pHead;
    
76.         int    _size;
    
77. };
    
78. 
    
79. /** Implementations */
    
80. Allocator<List::Link> List::Link::_linkAlloc;
    
81. 
    
82. void * List::Link::operator new (std::size_t size)
    
83. {
    
84.         assert (size == sizeof (Link));
    
85.         return _linkAlloc.allocate ();
    
86. }
    
87. 
    
88. void List::Link::operator delete (void * mem)
    
89. {
    
90.         if (mem)
    
91.                 _linkAlloc.recycle (mem);
    
92. }
    
93. 
    
94. void List::Link::Purge () { _linkAlloc.deallocate (); }
    
95. 
    
96. // List
    
97. 
    
98. List::List ()
    
99.         : _pHead (0), _size(0)
    
100. {}
     
101. 
     
102. List::~List ()
     
103. {
     
104.         while ( _pHead != 0 )
     
105.         {
     
106.                 Link * pLink = _pHead;
     
107.                 _pHead = _pHead->Next (); // unlink pLink
     
108.                 delete pLink;
     
109.         }
     
110. }
     
111. 
     
112. void List::insert (int value)
     
113. {
     
114.         Link * pLink = new Link (_pHead, value);
     
115.         _pHead = pLink;
     
116.         _size++;
     
117. }
     
118. 
     
119. List* List::del_front ()
     
120. {
     
121.         List * tmp = new List;
     
122.         tmp->_pHead = _pHead;
     
123.         _pHead = _pHead->Next ();
     
124.         // don't delete recursively!
     
125.         tmp->_pHead->SetNext(0);
     
126.         tmp->_size = 1;
     
127.         return tmp;
     
128. }
     
129. 
     
130. void List::swap (List& x)
     
131. {
     
132.         List::Link * tmp = _pHead;
     
133.         _pHead = x._pHead;
     
134.         x._pHead = tmp;
     
135.        
     
136.         int tmpsize = _size;
     
137.         _size = x._size;
     
138.         x._size = tmpsize;
     
139. }
     
140. 
     
141. void List::merge (List& x)
     
142. {
     
143.         iterator f1 = begin(); iterator l1 = end();
     
144.         iterator f2 = x.begin(); iterator l2 = x.end();
     
145.        
     
146.         iterator prev;
     
147.         while(f1 != l1 && f2 != l2)
     
148.         {
     
149.                 if(*f2 <= *f1)
     
150.                 {
     
151.                         iterator next = f2;
     
152.                         ++next;
     
153.                         if(!prev._pLink)
     
154.                         {
     
155.                                 _pHead = f2._pLink;
     
156.                                 f2._pLink->SetNext (f1._pLink);
     
157.                         }
     
158.                         else
     
159.                         {
     
160.                                 prev._pLink->SetNext (f2._pLink);
     
161.                                 f2._pLink->SetNext (f1._pLink);
     
162.                         }
     
163.                         prev = f2;
     
164.                         f2 = next;
     
165.                 }
     
166.                 else
     
167.                 {
     
168.                         prev = f1;
     
169.                         ++f1;
     
170.                 }
     
171.         }
     
172.         if(f2 != l2)
     
173.                 prev._pLink->SetNext (f2._pLink);
     
174.        
     
175.         _size += x._size; x._size = 0;
     
176. }
     
177. 
     
178. #endif

复制代码

然后搬出我最新修改的str.h头文件，是实现自己的string的。
str.h

1. #ifndef STD_STRING
   
2. #define STD_STRING
   
3. 
   
4. #include "ios.h"
   
5. #include <string.h>
   
6. 
   
7. void memmove(char *dest, char *src, size_t n)
   
8. {
   
9.     /* No need to do that thing. */
   
10.     if (dest == src)
    
11.         return;
    
12. 
    
13.     /* Check for destructive overlap.  */
    
14.     if (src < dest && dest < src + n) {
    
15.         /* Destructive overlap ... have to copy backwards.  */
    
16.         src += n;
    
17.         dest += n;
    
18.         while (n-- > 0)
    
19.             *--dest = *--src;
    
20.     } else {
    
21.         /* Do an ascending copy.  */
    
22.         while (n-- > 0)
    
23.             *dest++ = *src++;
    
24.     }
    
25. }
    
26. 
    
27. template <class T>
    
28.   void swap (T &a, T &b)
    
29. {
    
30.   T tmp = a;
    
31.   a = b;
    
32.   b = tmp;
    
33. }
    
34. 
    
35. template <class Iterator>
    
36.   void reverse (Iterator first, Iterator last)
    
37. {
    
38.   while ((first!=last)&&(first!=--last)) {
    
39.     swap(*first, *last);
    
40.     ++first;
    
41.   }
    
42. }
    
43. 
    
44. class out_of_range{
    
45. public:
    
46.         out_of_range()
    
47.         {
    
48.                 std::cerr << "Error: Invalid access of element. " << std::endl;
    
49.         }
    
50. };
    
51. 
    
52. namespace std{
    
53.         class string{
    
54.         public:
    
55.                 typedef size_t        size_type;
    
56.                 typedef char          value_type;
    
57.                 typedef const string& const_reference;
    
58.                 typedef const char *  const_pointer;
    
59.                 typedef value_type *  iterator;
    
60. 
    
61.         private:
    
62.                 class str_allocator
    
63.                 {
    
64.                         struct free
    
65.                         {
    
66.                                 char * val;
    
67.                                 free *_next;
    
68.                         };
    
69.                 public:
    
70.                         str_allocator () : _p (0) {}
    
71.                         ~str_allocator () { deallocate(); }
    
72.                         void deallocate();
    
73.                         void * allocate();
    
74.                         void recycle (void * link);
    
75.                 private:
    
76.                         free * _p;
    
77.                 };
    
78.                
    
79.         public:
    
80.             string(const_pointer str = "");                 //default constructor(value_type)
    
81.             string(value_type);
    
82.             string(const_reference);                  //assign constructor(string)
    
83.             
    
84.             string&    operator= (const_reference);         //operator=
    
85.             string     operator+ (const_reference) const;   //operator+
    
86.             string&    operator+=(const_reference);         //operator+=
    
87.             
    
88.             //bool operators
    
89.             bool       operator==(const_reference) const;    //operator==
    
90.             bool       operator==(const_pointer) const;
    
91.             bool       operator!=(const_reference) const;    //operator!=
    
92.             bool       operator!=(const_pointer) const;
    
93.             bool       operator< (const_reference) const;    //operator<
    
94.             bool       operator< (const_pointer) const;
    
95.             bool       operator> (const_reference) const;    //operator>
    
96.             bool       operator> (const_pointer) const;
    
97.             bool       operator<=(const_reference) const;    //operator<=
    
98.             bool       operator<=(const_pointer) const;
    
99.             bool       operator>=(const_reference) const;    //operator>=
    
100.             bool       operator>=(const_pointer) const;
     
101.             
     
102.             value_type&      operator[](const size_type) const;  //operator[]
     
103.             value_type&      at(const size_type n) const;
     
104.             
     
105.             iterator   begin() { return m_data; }
     
106.             iterator   end()   { return m_data + _len; }
     
107. 
     
108.                 void * operator new (size_type size) { return _str_alloc.allocate(); }
     
109.                 void   operator delete (void * mem) { if (mem) _str_alloc.recycle (mem); }
     
110.                 static void release () { _str_alloc.deallocate(); }
     
111.             
     
112.             size_type  size() const { return _len; }
     
113.             size_type  length() const { return _len; }
     
114.                 string     substr(size_type pos, size_type len) const;
     
115.             string&    erase(size_type pos, size_type len);
     
116.             void       swap(string& str);
     
117.             void       clear();
     
118.             bool       empty()  { return !_len; }
     
119.             const_pointer c_str() const { return m_data; }
     
120.             ~string(void);
     
121.         private:
     
122.                 static str_allocator _str_alloc;
     
123.             value_type *m_data;
     
124.             size_type  _len;
     
125.             mutable bool local;
     
126.         };
     
127. 
     
128.         string::str_allocator string::_str_alloc;
     
129.         
     
130.         inline string::string(const_pointer str)
     
131.         {
     
132.                 _len   = strlen(str);
     
133.         m_data = new value_type[_len+1];
     
134.         strcpy(m_data, str);
     
135.         local  = true;
     
136.         }
     
137.         
     
138.         inline string::string(value_type ch)
     
139.         {
     
140.             m_data = new value_type[1];
     
141.         m_data[0] = ch;
     
142.         _len   = 1;
     
143.         local  = true;
     
144.         }
     
145.         
     
146.         inline string::string(const_reference other)
     
147.         {
     
148.                 local  = false;
     
149.             m_data = other.m_data;
     
150.             _len   = other._len;
     
151.         }
     
152.         
     
153.         inline string::~string(void)
     
154.         {
     
155.                 if(local) delete [] m_data;
     
156.         }
     
157.         
     
158.         inline string& string::operator=(const_reference other)
     
159.         {
     
160.             if (this!=&other)
     
161.             {
     
162.                 string tmp(other);
     
163.                 swap(tmp);
     
164.             }
     
165.             return *this;
     
166.         }
     
167.         
     
168.         inline string string::operator+(const_reference other)const
     
169.         {
     
170.             string s;
     
171.             s.local = false;
     
172.                 s.m_data = new value_type[strlen(m_data)+strlen(other.m_data)+1];
     
173.              strcpy(s.m_data,m_data);
     
174.             strcat(s.m_data,other.m_data);
     
175.             s._len = _len + other._len;
     
176.              return s;
     
177.         }
     
178.         
     
179.         inline string& string::operator+=(const_reference other)
     
180.         {
     
181.             *this = *this + other;
     
182.             return *this;
     
183.         }
     
184.         
     
185.         inline bool string::operator==(const_reference s) const
     
186.         {
     
187.              return s._len == _len
     
188.                    && !strcmp(m_data,s.m_data);
     
189.         }
     
190.         
     
191.         inline bool string::operator==(const_pointer s) const
     
192.         {
     
193.              return strlen(s) == _len
     
194.                    && !strcmp(m_data,s);
     
195.         }
     
196.         
     
197.         inline bool string::operator!=(const_reference s) const
     
198.         {
     
199.              return !(*this == s);
     
200.         }
     
201.         
     
202.         inline bool string::operator!=(const_pointer s) const
     
203.         {
     
204.              return !(*this == s);
     
205.         }
     
206.         
     
207.         inline bool string::operator< (const_reference s) const
     
208.         {
     
209.              return strcmp(m_data,s.m_data) < 0;
     
210.         }
     
211.         
     
212.         inline bool string::operator< (const_pointer s) const
     
213.         {
     
214.              return strcmp(m_data,s) < 0;
     
215.         }
     
216.         
     
217.         inline bool string::operator> (const_reference s) const
     
218.         {
     
219.              return strcmp(m_data,s.m_data) > 0;
     
220.         }
     
221.         
     
222.         inline bool string::operator> (const_pointer s) const
     
223.         {
     
224.              return strcmp(m_data,s) > 0;
     
225.         }
     
226.         
     
227.         inline bool string::operator<=(const_reference s) const
     
228.         {
     
229.              return !(*this > s);
     
230.         }
     
231.         
     
232.         inline bool string::operator<=(const_pointer s) const
     
233.         {
     
234.              return !(*this > s);
     
235.         }
     
236.         
     
237.         inline bool string::operator>=(const_reference s) const
     
238.         {
     
239.              return !(*this < s);
     
240.         }
     
241.         
     
242.         inline bool string::operator>=(const_pointer s) const
     
243.         {
     
244.              return !(*this < s);
     
245.         }
     
246.         
     
247.         inline char& string::operator[](const size_type n) const
     
248.         {
     
249.              if (n<0 || n>=_len) throw out_of_range();
     
250.             return m_data[n];
     
251.         }
     
252.         
     
253.         inline char& string::at(const size_type n) const
     
254.         {
     
255.              if (n<0 || n>=_len) throw out_of_range();
     
256.             return m_data[n];
     
257.         }
     
258. 
     
259.         inline string string::substr(size_type pos, size_type len) const
     
260.         {
     
261.                 string s;
     
262.                 s.local = false;
     
263.                 s.m_data = new value_type[len+1];
     
264.                 memcpy(s.m_data, m_data + pos, len);
     
265.                 s.m_data[len] = '\0';
     
266.                 return s;
     
267.         }
     
268.         
     
269.         inline string& string::erase(size_type pos, size_type len)
     
270.         {
     
271.                 if (pos >= _len || 0 == len) return *this;
     
272.                 const size_type remainder = pos + len;
     
273.                 if (remainder >= _len || remainder < pos)
     
274.                 {
     
275.                 *(m_data + pos) = '\0';
     
276.                 _len = pos;
     
277.                 return *this;
     
278.             }
     
279.             size_type left = _len - remainder + 1;
     
280.             value_type *d  = m_data + pos;
     
281.             value_type *s  = m_data + remainder;
     
282.             memmove(d, s, left);
     
283.             _len -= len;
     
284.             return *this;
     
285.         }
     
286.         
     
287.         inline void string::swap(string& str)
     
288.         {
     
289.                 string tmp(str);
     
290.                
     
291.                 str.local  = local;
     
292.                 str.m_data = m_data;
     
293.                 str._len   = _len;
     
294.                
     
295.                 local  = tmp.local;
     
296.                 m_data = tmp.m_data;
     
297.                 _len   = tmp._len;
     
298.         }
     
299.         
     
300.         inline void string::clear()
     
301.         {
     
302.                 m_data = new value_type[1];
     
303.                 strcpy(m_data, "");
     
304.                 _len   = 0;
     
305.         }
     
306. 
     
307.         //String Allocator (Actually a memory pool)
     
308.         inline void * string::str_allocator::allocate ()
     
309.         {
     
310.                 if (_p != 0)
     
311.                 {
     
312.                         void * mem = _p;
     
313.                         _p = _p->_next;
     
314.                         return mem;
     
315.                 }
     
316.                 else
     
317.                 {
     
318.                         // use global operator new
     
319.                         return ::new free [sizeof (char)];
     
320.                 }
     
321.         }
     
322. 
     
323.         inline void string::str_allocator::deallocate ()
     
324.         {
     
325.                 while (_p != 0)
     
326.                 {
     
327.                         // it was allocated as an array of char
     
328.                         char * mem = reinterpret_cast<char *> (_p);
     
329.                         _p = _p->_next;
     
330.                         ::delete [] mem;
     
331.                 }
     
332.         }
     
333. 
     
334.         inline void string::str_allocator::recycle(void * mem)
     
335.         {
     
336.                 free * link = static_cast<free *> (mem);
     
337.                 link->_next = _p;
     
338.                 _p = link;
     
339.         }
     
340.         
     
341.         istream& operator>>(istream& is, string& str)
     
342.         {
     
343.             char buffer[1000];
     
344.             is >> buffer;
     
345.             str = buffer;
     
346.              return is;
     
347.         }
     
348.         
     
349.         istream & getline(istream & is, string & str)
     
350.         {
     
351.             char buffer[1000];
     
352.             is.getline(buffer, 1000);
     
353.             str = buffer;
     
354.             return is;
     
355.         }
     
356.         
     
357.         ostream& operator<<(ostream& os, string& str)
     
358.         {
     
359.             os << str.c_str();
     
360.             return os;
     
361.         }
     
362.         
     
363. } //namespace std
     
364. 
     
365. #endif

复制代码

今天很晚了，就不过多讲解了。大家要支持哦~

yuzhouliu2000

学习了，支持一下，辛苦了

andalousie

希望大家支持我。虽然我水平不怎么高~{:7_168:}