通过重载new 和 delete 大大提高内存空间的分配速度。
template <class type> class Link
{
type elememt;
Link* next;
Link(const type& ele, Link* ne == NULL)
{
element = ele;
next = ne;
}
Link(Link* ne = NULL)
{
next = ne;
}
}
template <class type> class link_list: public Link<type>
{
private:
Link<type>* head;
Link<type>* tail;
Link<type>* fence;
int leftcnt;
int rightcnt;
void init()
{
fence = tail = head = new Link<type>;
rightcnt = leftcnt = 0;
}
void remove_all()
{
while (head != NULL)
{
Link<type>* tmp = NULL;
tmp = head;
head = head->next;
delete tmp;
}
}
static Link<type>* freelist;
void* operator new(size_t);
void operator delete(void*);
public:
link_list()
{
init();
}
~link_list()
{
remove_all();
}
void clear()
{
remove_all();
init();
}
bool insert(const type&);
bool append(const type&);
bool remove(type&);
void setStart()
{
fence = head;
rightcnt += leftcnt;
leftcnt = 0;
}
void setEnd()
{
fence = tail;
leftcnt += rightcnt;
rightcnt = 0;
}
bool prev();
void next();
{
if (fence != tail)
{
fence = fence->next;
rightcnt--;
leftcnt++;
}
}
bool setPos(int pos);
}
template <class type>
bool link_list<type>::insert(const type& item)
{
Link<type>* tmp = new Link<type>(item, fence->next);
fence->next = tmp;
if (tail == fence)
tail = fence->next;
right++;
return true;
}
template <class type>
bool link_list<type>::append(const type& item)
{
tail = tail->next = new Link<type>(item, NULL);
right++;
return true;
}
template <class type>
bool link_list<type>::remove(type& item)
{
if (fence->next == NULL)
return false;
item = fence->next->element;
Link<type>* tmp = fence->next;
fence->next = tmp->next;
if (tail = tmp)
tail = fence;
delete tmp;
rightcnt__;
return true;
}
template <class type>
bool link_list<type>::prev(void)
{
Link<type>* tmp = head;
if (fence == head)
return false;
while (tmp->next != fence)
tmp = tmp->next;
fence = tmp;
rightcnt++;
leftcnt--;
return true;
}
template <class type>
bool link_list<type>::setPos(int pos)
{
int i = 0;
while (i != pos)
{
fence = fence->next;
i++;
}
return true;
}
template <class type>
link_list<type>* link_list<type>::freelist = NULL;
template <class type>
void* link_list<type>::operator new(size_t)
{
if (free_list == NULL)
return new Link<type>;
Link<type>* tmp = freelist;
freelist = freelist->next;
return tmp;
}
template <class type>
void link_list<type>::operator delete(void* ptr)
{
((Link<type>*)ptr)->next = freelist;
freelist = (Link<type>*)ptr;
}