论坛 › C\C++交流 › 简单的allocator应用

andalousie 发表于 2014-3-3 23:46:02

简单的allocator应用

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

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

template<typename T>
class Allocator
{
        enum { BlockLinks = 4 }; // small value for testing
        class Block
        {
        public:
                Block (Block * next): _next (next) {}
                Block * Next () { return _next; }
        private:
                Block * _next;
        };
public:
        typedef T value_type;
        typedef value_type* pointer;
        class Pool
        {
        public:
                Pool (Pool * next): _next (next) {}
                pointer val;
                Pool * _next;
        };

        Allocator ()
                : _blocks (0), _size(BlockLinks * sizeof(value_type)) {}
        ~Allocator () { deallocate (); }
        void deallocate ();
        void * allocate ();
        void recycle (void * mem);
private:
        Block * _blocks;
        Pool* _p;
        size_t   _size;
};

template<typename T>
inline void * Allocator<T>::allocate ()
{
        if (_p == 0)
        {
                // 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)
                {
                        Pool * link = ::new (p) Pool (_p);
                        _p = link;
                        p += sizeof (Pool);
                }
        }
        void * mem = _p;
        _p = _p->_next;
        return mem;
}

template<typename T>
inline void Allocator<T>::deallocate ()
{
        while (_blocks != 0)
        {
                // it was allocated as an array of char
                char * mem = reinterpret_cast<char *> (_blocks);
                _blocks = _blocks->Next();
                ::delete [] mem;
        }
}

template<typename T>
inline void Allocator<T>::recycle(void * mem)
{
        Pool * link = static_cast<Pool *> (mem);
        link->_next = _p;
        _p = link;
}
#endifList.h //去掉了原来的List.cpp实现文件#if !defined (LIST_H)
#define LIST_H
#include <new>
#include <cassert>
#include "allocator.h"

/*** Add this on VC6.0 */
namespace std
{
        using ::size_t;
}

class List
{
public:
        List ();
        ~List ();
        void insert (int value);
        List* del_front ();
        void merge (List& x);
        void swap (List& x);
        intsize () { return _size; }
        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 ();
        private:
                static Allocator<Link> _linkAlloc;
               
                Link *_pNext;
                int                _value;
        };
public:
        class iterator
        {
                friend class List;
        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 * p = 0)
                        : _pLink (p) {}
                iterator (const iterator& it)
                        : _pLink (it._pLink) {}
        protected:
                Link * _pLink; // current link
        };

        friend class iterator;
        iterator begin () { return iterator (_pHead); }
        iterator end   () { return iterator (0); }
private:
        List::Link const * GetHead () const { return _pHead; }
       
        List::Link * _pHead;
        int    _size;
};

/** Implementations */
Allocator<List::Link> List::Link::_linkAlloc;

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

void List::Link::operator delete (void * mem)
{
        if (mem)
                _linkAlloc.recycle (mem);
}

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

// List

List::List ()
        : _pHead (0), _size(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;
        _size++;
}

List* List::del_front ()
{
        List * tmp = new List;
        tmp->_pHead = _pHead;
        _pHead = _pHead->Next ();
        // don't delete recursively!
        tmp->_pHead->SetNext(0);
        tmp->_size = 1;
        return tmp;
}

void List::swap (List& x)
{
        List::Link * tmp = _pHead;
        _pHead = x._pHead;
        x._pHead = tmp;
       
        int tmpsize = _size;
        _size = x._size;
        x._size = tmpsize;
}

void List::merge (List& x)
{
        iterator f1 = begin(); iterator l1 = end();
        iterator f2 = x.begin(); iterator l2 = x.end();
       
        iterator prev;
        while(f1 != l1 && f2 != l2)
        {
                if(*f2 <= *f1)
                {
                        iterator next = f2;
                        ++next;
                        if(!prev._pLink)
                        {
                                _pHead = f2._pLink;
                                f2._pLink->SetNext (f1._pLink);
                        }
                        else
                        {
                                prev._pLink->SetNext (f2._pLink);
                                f2._pLink->SetNext (f1._pLink);
                        }
                        prev = f2;
                        f2 = next;
                }
                else
                {
                        prev = f1;
                        ++f1;
                }
        }
        if(f2 != l2)
                prev._pLink->SetNext (f2._pLink);
       
        _size += x._size; x._size = 0;
}

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

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

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

    /* Check for destructive overlap.*/
    if (src < dest && dest < src + n) {
      /* Destructive overlap ... have to copy backwards.*/
      src += n;
      dest += n;
      while (n-- > 0)
            *--dest = *--src;
    } else {
      /* Do an ascending copy.*/
      while (n-- > 0)
            *dest++ = *src++;
    }
}

template <class T>
void swap (T &a, T &b)
{
T tmp = a;
a = b;
b = tmp;
}

template <class Iterator>
void reverse (Iterator first, Iterator last)
{
while ((first!=last)&&(first!=--last)) {
    swap(*first, *last);
    ++first;
}
}

class out_of_range{
public:
      out_of_range()
      {
                std::cerr << "Error: Invalid access of element. " << std::endl;
      }
};

namespace std{
      class string{
      public:
                typedef size_t      size_type;
                typedef char          value_type;
                typedef const string& const_reference;
                typedef const char *const_pointer;
                typedef value_type *iterator;

      private:
                class str_allocator
                {
                        struct free
                        {
                              char * val;
                              free *_next;
                        };
                public:
                        str_allocator () : _p (0) {}
                        ~str_allocator () { deallocate(); }
                        void deallocate();
                        void * allocate();
                        void recycle (void * link);
                private:
                        free * _p;
                };
               
      public:
            string(const_pointer str = "");               //default constructor(value_type)
            string(value_type);
            string(const_reference);                  //assign constructor(string)
            
            string&    operator= (const_reference);         //operator=
            string   operator+ (const_reference) const;   //operator+
            string&    operator+=(const_reference);         //operator+=
            
            //bool operators
            bool       operator==(const_reference) const;    //operator==
            bool       operator==(const_pointer) const;
            bool       operator!=(const_reference) const;    //operator!=
            bool       operator!=(const_pointer) const;
            bool       operator< (const_reference) const;    //operator<
            bool       operator< (const_pointer) const;
            bool       operator> (const_reference) const;    //operator>
            bool       operator> (const_pointer) const;
            bool       operator<=(const_reference) const;    //operator<=
            bool       operator<=(const_pointer) const;
            bool       operator>=(const_reference) const;    //operator>=
            bool       operator>=(const_pointer) const;
            
            value_type&      operator[](const size_type) const;//operator[]
            value_type&      at(const size_type n) const;
            
            iterator   begin() { return m_data; }
            iterator   end()   { return m_data + _len; }

                void * operator new (size_type size) { return _str_alloc.allocate(); }
                void   operator delete (void * mem) { if (mem) _str_alloc.recycle (mem); }
                static void release () { _str_alloc.deallocate(); }
            
            size_typesize() const { return _len; }
            size_typelength() const { return _len; }
                string   substr(size_type pos, size_type len) const;
            string&    erase(size_type pos, size_type len);
            void       swap(string& str);
            void       clear();
            bool       empty(){ return !_len; }
            const_pointer c_str() const { return m_data; }
            ~string(void);
      private:
                static str_allocator _str_alloc;
            value_type *m_data;
            size_type_len;
            mutable bool local;
      };

      string::str_allocator string::_str_alloc;
      
      inline string::string(const_pointer str)
      {
                _len   = strlen(str);
      m_data = new value_type;
      strcpy(m_data, str);
      local= true;
      }
      
      inline string::string(value_type ch)
      {
            m_data = new value_type;
      m_data = ch;
      _len   = 1;
      local= true;
      }
      
      inline string::string(const_reference other)
      {
                local= false;
            m_data = other.m_data;
            _len   = other._len;
      }
      
      inline string::~string(void)
      {
                if(local) delete [] m_data;
      }
      
      inline string& string::operator=(const_reference other)
      {
            if (this!=&other)
            {
                string tmp(other);
                swap(tmp);
            }
            return *this;
      }
      
      inline string string::operator+(const_reference other)const
      {
            string s;
            s.local = false;
                s.m_data = new value_type;
             strcpy(s.m_data,m_data);
            strcat(s.m_data,other.m_data);
            s._len = _len + other._len;
             return s;
      }
      
      inline string& string::operator+=(const_reference other)
      {
            *this = *this + other;
            return *this;
      }
      
      inline bool string::operator==(const_reference s) const
      {
             return s._len == _len
                   && !strcmp(m_data,s.m_data);
      }
      
      inline bool string::operator==(const_pointer s) const
      {
             return strlen(s) == _len
                   && !strcmp(m_data,s);
      }
      
      inline bool string::operator!=(const_reference s) const
      {
             return !(*this == s);
      }
      
      inline bool string::operator!=(const_pointer s) const
      {
             return !(*this == s);
      }
      
      inline bool string::operator< (const_reference s) const
      {
             return strcmp(m_data,s.m_data) < 0;
      }
      
      inline bool string::operator< (const_pointer s) const
      {
             return strcmp(m_data,s) < 0;
      }
      
      inline bool string::operator> (const_reference s) const
      {
             return strcmp(m_data,s.m_data) > 0;
      }
      
      inline bool string::operator> (const_pointer s) const
      {
             return strcmp(m_data,s) > 0;
      }
      
      inline bool string::operator<=(const_reference s) const
      {
             return !(*this > s);
      }
      
      inline bool string::operator<=(const_pointer s) const
      {
             return !(*this > s);
      }
      
      inline bool string::operator>=(const_reference s) const
      {
             return !(*this < s);
      }
      
      inline bool string::operator>=(const_pointer s) const
      {
             return !(*this < s);
      }
      
      inline char& string::operator[](const size_type n) const
      {
             if (n<0 || n>=_len) throw out_of_range();
            return m_data;
      }
      
      inline char& string::at(const size_type n) const
      {
             if (n<0 || n>=_len) throw out_of_range();
            return m_data;
      }

      inline string string::substr(size_type pos, size_type len) const
      {
                string s;
                s.local = false;
                s.m_data = new value_type;
                memcpy(s.m_data, m_data + pos, len);
                s.m_data = '\0';
                return s;
      }
      
      inline string& string::erase(size_type pos, size_type len)
      {
                if (pos >= _len || 0 == len) return *this;
                const size_type remainder = pos + len;
                if (remainder >= _len || remainder < pos)
                {
                *(m_data + pos) = '\0';
                _len = pos;
                return *this;
            }
            size_type left = _len - remainder + 1;
            value_type *d= m_data + pos;
            value_type *s= m_data + remainder;
            memmove(d, s, left);
            _len -= len;
            return *this;
      }
      
      inline void string::swap(string& str)
      {
                string tmp(str);
               
                str.local= local;
                str.m_data = m_data;
                str._len   = _len;
               
                local= tmp.local;
                m_data = tmp.m_data;
                _len   = tmp._len;
      }
      
      inline void string::clear()
      {
                m_data = new value_type;
                strcpy(m_data, "");
                _len   = 0;
      }

      //String Allocator (Actually a memory pool)
      inline void * string::str_allocator::allocate ()
      {
                if (_p != 0)
                {
                        void * mem = _p;
                        _p = _p->_next;
                        return mem;
                }
                else
                {
                        // use global operator new
                        return ::new free ;
                }
      }

      inline void string::str_allocator::deallocate ()
      {
                while (_p != 0)
                {
                        // it was allocated as an array of char
                        char * mem = reinterpret_cast<char *> (_p);
                        _p = _p->_next;
                        ::delete [] mem;
                }
      }

      inline void string::str_allocator::recycle(void * mem)
      {
                free * link = static_cast<free *> (mem);
                link->_next = _p;
                _p = link;
      }
      
      istream& operator>>(istream& is, string& str)
      {
            char buffer;
            is >> buffer;
            str = buffer;
             return is;
      }
      
      istream & getline(istream & is, string & str)
      {
            char buffer;
            is.getline(buffer, 1000);
            str = buffer;
            return is;
      }
      
      ostream& operator<<(ostream& os, string& str)
      {
            os << str.c_str();
            return os;
      }
      
} //namespace std

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

yuzhouliu2000 发表于 2014-3-4 09:01:56

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

andalousie 发表于 2014-3-5 10:25:37

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

查看完整版本: 简单的allocator应用