马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 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 [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)
{
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;
}
#endif
#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);
int size () { 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 (); }
iterator operator + (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#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_type size() const { return _len; }
size_type length() 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[_len+1];
strcpy(m_data, str);
local = true;
}
inline string::string(value_type ch)
{
m_data = new value_type[1];
m_data[0] = 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[strlen(m_data)+strlen(other.m_data)+1];
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[n];
}
inline char& string::at(const size_type n) const
{
if (n<0 || n>=_len) throw out_of_range();
return m_data[n];
}
inline string string::substr(size_type pos, size_type len) const
{
string s;
s.local = false;
s.m_data = new value_type[len+1];
memcpy(s.m_data, m_data + pos, len);
s.m_data[len] = '\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[1];
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 [sizeof (char)];
}
}
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[1000];
is >> buffer;
str = buffer;
return is;
}
istream & getline(istream & is, string & str)
{
char buffer[1000];
is.getline(buffer, 1000);
str = buffer;
return is;
}
ostream& operator<<(ostream& os, string& str)
{
os << str.c_str();
return os;
}
} //namespace std
#endif
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2014-3-3 23:46:02
置顶卡
千斤顶
显身卡
楼主