设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › 简单的allocator应用
返回列表 发新帖
查看: 1943|回复: 2

[技术交流] 简单的allocator应用

[复制链接]
andalousie
发表于 2014-3-3 23:46:02 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 andalousie 于 2014-3-31 00:10 编辑

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

  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.         };

  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. };

  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. }

  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. }

  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"

  7. /*** Add this on VC6.0 */
  8. namespace std
  9. {
  10.         using ::size_t;
  11. }

  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.                 }

  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.         };

  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. };

  79. /** Implementations */
  80. Allocator<List::Link> List::Link::_linkAlloc;

  82. void * List::Link::operator new (std::size_t size)
  83. {
  84.         assert (size == sizeof (Link));
  85.         return _linkAlloc.allocate ();
  86. }

  88. void List::Link::operator delete (void * mem)
  89. {
  90.         if (mem)
  91.                 _linkAlloc.recycle (mem);
  92. }

  94. void List::Link::Purge () { _linkAlloc.deallocate (); }

  96. // List

  98. List::List ()
  99.         : _pHead (0), _size(0)
  100. {}

  102. List::~List ()
  103. {
  104.         while ( _pHead != 0 )
  105.         {
  106.                 Link * pLink = _pHead;
  107.                 _pHead = _pHead->Next (); // unlink pLink
  108.                 delete pLink;
  109.         }
  110. }

  112. void List::insert (int value)
  113. {
  114.         Link * pLink = new Link (_pHead, value);
  115.         _pHead = pLink;
  116.         _size++;
  117. }

  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. }

  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. }

  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. }

  178. #endif
复制代码

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

  4. #include "ios.h"
  5. #include <string.h>

  7. void memmove(char *dest, char *src, size_t n)
  8. {
  9.     /* No need to do that thing. */
  10.     if (dest == src)
  11.         return;

  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. }

  27. template <class T>
  28.   void swap (T &a, T &b)
  29. {
  30.   T tmp = a;
  31.   a = b;
  32.   b = tmp;
  33. }

  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. }

  44. class out_of_range{
  45. public:
  46.         out_of_range()
  47.         {
  48.                 std::cerr << "Error: Invalid access of element. " << std::endl;
  49.         }
  50. };

  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;

  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; }

  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.         };

  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.         }

  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.         }

  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.         }

  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.         }

  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

  365. #endif
复制代码
今天很晚了，就不过多讲解了。大家要支持哦~

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

yuzhouliu2000
发表于 2014-3-4 09:01:56 | 显示全部楼层
学习了，支持一下，辛苦了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

andalousie
 楼主| 发表于 2014-3-5 10:25:37 | 显示全部楼层
希望大家支持我。虽然我水平不怎么高~{:7_168:}
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-9 03:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表