zList是一个C++的块状内存链表，特点：
1、对于某种类别需要申请大量指针，zList是一个很好的帮手，它能比new少很多内存。
2、它对内存进行整体管理，可以将数据和文件快速互操作
3、和vector对象存储对比，vector存储的对象不能使用其指针，因为vector内容变化时vector存储对象的指针会变化
4、zList也可以当做顺序的数组使用，它有自己的迭代器，可以遍历整个数组
下面是申请5千万个RECT指针对比结果：
zList申请五千万RECT指针内存占用：
直接new五千万RECT指针内存占用：
从对比看节省了724.6M的内存
下面是zList实现代码：
#include "stdafx.h"
#include <set>
#include <map>
#include <string>
#include <vector>
#include <windows.h>
using namespace std; template <class T>
struct zElem
{
zElem() { memset(this, , sizeof(zElem)); }
int has() //查找空闲的位置
{
return extra < ? extra : -;
}
bool empty() { return == size; };
bool full() { return == size; };
T *add(int i, const T &r)
{
bit[i] = ;
R[i] = r;
size++;
if (extra == i)//指向下一个位置
{
extra++;
while (extra < )
{
if (bit[extra] == )break;
extra++;
}
}
return R + i;
}
void remove(T *r)
{
int i = (int)(r - R);
if (i >= && i < )
{
bit[i] = ;
if (extra > i)extra = (unsigned short)i;
size--;
}
}
bool in(T *r)
{
int i = (int)(r - R);
return i >= && i < ;
}
T* get(int i)
{
int ind = getInd(i);
return ind == - ? NULL : R + ind;
}
int getInd(int i)
{
if (i >= && i < extra)return i;
int k = extra + , t = extra;
while (k < )
{
if (bit[k] != )
{
if (t == i)return k;
t++;
}
k++;
}
return -;
}
bool getInd(size_t &ind, size_t &off, size_t n)
{
if (ind + n < extra)
{
ind += n;
off = ind;
return true;
}
while (++ind < )
{
if (bit[ind] != )
{
n--;
off++;
if (n==)return true;
}
}
return false;
}
unsigned short extra;//指向当前空闲位置
unsigned short size; //当前已有数据个数
byte bit[]; //标记是否使用
T R[]; //数据存储
};
template <class T>
struct zList
{
struct iterator
{
T* operator *()
{
return p ? &p->head[ind]->R[zind] : NULL;
}
T* operator ->()
{
return p ? &p->head[ind]->R[zind] : NULL;
}
iterator& operator ++()
{
bool bend = true;
if (p&&p->head.size() > ind)
{
for (; ind < p->head.size(); ind++)
{
zElem<T>*a = p->head[ind];
if (zsize + < a->size)
{
a->getInd(zind,zsize,);
bend = false;
break;
}
zind = zsize = -;
}
}
if (bend)
{
ind = zsize = zind = ; p = ;
}
return (*this);
}
bool operator ==(const iterator &data)const
{
return ind == data.ind&&zind == data.zind&&zsize == data.zsize&&p == data.p;
}
bool operator !=(const iterator &data)const
{
return ind != data.ind||zind != data.zind||zsize != data.zsize||p != data.p;
}
explicit operator bool() const
{
return (!p);
}
size_t ind; //p的位置
size_t zind; //zElem中的R位置
size_t zsize; //zElem中zind位置所在的次序
zList *p; //指向链表的指针
};
zList() :size(), extra() { }
~zList()
{
for (auto &a: head)
{
delete a;
}
}
T *add(const T &r)
{
zElem<T>* e;
if (extra >= head.size())
{
e = new zElem<T>();
head.push_back(e);
}
else
{
e = head[extra];
}
int i = e->has();
T *R = e->add(i, r);
size++;
while (extra < head.size() && e->full())
{
e = head[extra];
extra++;
}
return R;
}
void remove(T *r)
{
if (r == NULL)return;
zElem<T> *rem;
size_t i = ;
for (; i < head.size(); i++)
{
rem = head[i];
if (rem->in(r))
{
size--;
rem->remove(r);
if (rem->empty())//删除当前节点
{
head.erase(head.begin() + i);
if (extra == i)
{
//往后查找空闲的位置
while (extra < head.size())
{
if (!head[extra]->full())break;
extra++;
}
}
delete rem;
}
else if(extra > i)
{
extra = i;
}
break;
}
}
}
T* get(int i)
{
for (auto &a : head)
{
if (i < a->size)
{
return a->get(i);
}
i -= a->size;
}
return NULL;
}
void clear()
{
for (auto &a : head)
{
delete a;
}
head.clear();
size = extra = ;
}
iterator begin()
{
iterator it = { ,,,NULL };
if (head.size() > )
{
int i = ;
for (;it.ind < head.size(); it.ind++)
{
zElem<T>*a = head[it.ind];
if (i < a->size)
{
it.p = this;
it.zind = a->getInd(i);
break;
}
i -= a->size;
}
}
return it;
}
iterator end()
{
iterator it = {,,,NULL};
return it;
}
size_t size; //个数
vector<zElem<T>*> head; //开头
size_t extra; //有空余位置的
};
使用方法如下：
int main()
{
zList<RECT> z;
for (int i = ; i < ; i++)
{
//1、申请内存
RECT r = { rand(), rand(), rand(), rand() };
RECT *p = z.add(r);
//2、可以对p进行使用...
//3、释放内存
z.remove(p);
}
getchar();
return ;
}
对zList进行元素遍历，迭代器方法：
int t = ;
zList<RECT>::iterator its = z.begin();
zList<RECT>::iterator ite = z.end();
for (; its != ite; ++its)
{
RECT *p = *its;
t = p->left;
}
对zList进行随机访问遍历，效率没有迭代器高：
int t = ;
for (int i = ; i < z.size; i++)
{
RECT *p = z.get(i);
t = p->left;
}