这个数组可以向里面插入任何类型,包括自定义类型, 程序只是实现了基本功能,还有待完善,
首先初始化,然后就可以插入数据了, 当储存单元不足的时候就自动增加储存单元
由于总的风格是c, 所以看着很是别扭, 有空了把全部改成c++风格的;
说有空就有空了,改成了c++风格了, 至于新的功能感觉有困难, 主要要是自定义类型的查找问题,如果查找问题解决了就一切搞定,c++版的新增加了查找功能,但是感觉没什么用处, 我觉得应该像key-> value那样就好了,如果哪天想到怎么做了再补上
下面是全部代码:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cassert> using namespace std; const int inCrement = 100; //每次增加的内存大小 typedef struct CStashTag { int size; // 单个储存单元的大小 int quantity; //储存单元的个数 int next; //指向storage数组最后的一个元素 unsigned char * storage; // 储存数据的数组,别误以为只能存char型额 }CStash; typedef struct TestTag //向CStashTag里面插入的数据类型 { int i; char c; double d; TestTag(int i, char c, double d):i(i), c(c), d(d){} }Test; #define ElementType Test //向CStashTag里面插入的数据类型 const int Size = sizeof(ElementType); //单元大小 void ininialize(CStash *s, int size); int add(CStash *s, const void *element); void* fetch(CStash *s, int index); void inflate(CStash *s, int inCrease); void cleanup(CStash *s); void initialize(CStash *s, int size) { s->size = size; s->next = 0; s->quantity = 0; s->storage = 0; } int add(CStash *s, const void *element) //添加元素 { if(s->next >= s->quantity) //内存不足就分配内存 inflate(s, inCrement); int startBytes = s->next * s->size; unsigned char *e = (unsigned char *) element; for(int i = 0; i < s->size; i++) //将数据写到数组末尾 s->storage[startBytes + i] = e[i]; s->next++; return s->next - 1; } void* fetch(CStash *s, int index) //返回数组下标为index的指针 { assert(0 <= index); if(index >= s->next) return 0; //printf("%d\n",*&s->storage[index * s->size]); return &(s->storage[index * s->size]); } void inflate(CStash *s, int inCrease) // 当数组的大小不能储存新增加的元素的时候增加increase个储存单元 { assert(inCrease > 0); int newQuantity = s->quantity + inCrease; int newBytes = newQuantity * s->size; int oldBytes = s->quantity * s->size; unsigned char *e = new unsigned char[newBytes]; for(int i = 0; i < oldBytes; i++) //将老数据拷贝到新的数组中 e[i] = s->storage[i]; delete[] s->storage; s->storage = e; //首地址指向新数组首地址 s->quantity = newBytes; } void cleanup(CStash *s) // 清空 { if(s->storage != 0) cout << "freeing storage" << endl; delete []s->storage; } int main() { CStash *s = new CStash(); initialize(s, Size); ElementType tmp = ElementType(1, 'c', 12); ElementType *p = &tmp; //add(s, p); //ElementType *p2 = (ElementType *)fetch(s, 0); //cout << *p2 << endl; for(int i = 0; i < 26; i++) { ElementType v = ElementType(i, 'c', 1); p = &v; add(s, p); } for(int i = 0; i < 26; i++) { ElementType *p2 = (ElementType *)fetch(s, i); //cout << *p2; printf("%d %c %llf\n", p2->i, p2->c, p2->d); } cout << endl; cleanup(s); return 0; }
方法(类的内部叫方法)的功能和上面的函数功能是一样的,所以就不注释了
下面是c++版的, 新增加了一个查找功能, 但是这个功能却不能查找自定义类型的数据,我无法解决结构体内存分配时的偏移地址问题,
代码如下:
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; #define ElementType int const int UnionSize = sizeof(ElementType); const int increase = 100; template<class T> class equal { public: virtual void* find(T f) { return NULL; } }; template<class T> class CStash:public equal<T> { private: char *storage; int quantity; int next; int size; void inflate() { int newQuantity = quantity + increase; int newBytes = (quantity + increase) * size; int oldBytes = next * size; char *e = new char[newBytes]; for(int i = 0; i < oldBytes; i++) e[i] = storage[i]; delete storage; storage = e; quantity = newQuantity; } public: CStash() { storage = 0; quantity = 0; next = 0; size = UnionSize; } void push_back(T *element) { if(next >= quantity) inflate(); int startBytes = next * size; unsigned char *e =(unsigned char *) element; for(int i = 0; i < size; i++) storage[startBytes + i] = e[i]; next++; } void * fetch(int index) { if(index > next || index < 0) return 0; else return &storage[index * size]; } virtual void* find(T f) //查找元素f { unsigned char * e = (unsigned char *) &f; for(int i = 0; i < next * size; i += size) { bool ok = true; for(int j = 0; j < sizeof(f); j++) { if(storage[i + j] != e[j]) { ok = false; break; } } if(ok) { return &storage[i]; } } return NULL; } void cleanup() { next = 0; quantity = 0; delete[] storage; storage = 0; } }; int main() { ElementType t = 120; ElementType *p = &t; CStash<ElementType> *cs = new CStash<ElementType>(); cs->push_back(p); t = 20; cs->push_back(p); t = 33; cs->push_back(p); t =12; cs->push_back(p); ElementType *tt = (ElementType *)cs->fetch(1); printf("%d\n", *tt); tt = (ElementType *)cs->find(33); printf("%d\n", *tt); tt = (ElementType *)cs->find(11); if(tt == NULL) puts("NULL"); cs->cleanup(); return 0; }
下面是我定义了一个自定义类型插入到Cstash里面, 但是查找的时候是会出错的, 我暂时也解决不了这个问题
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int increase = 100; typedef struct TestTag { int i; char c; char c2; char c3; //char c4; TestTag(int i, char c):i(i), c(c),c2(c), c3(c){}//, c4(c){} }Test; #define ElementType Test const int UnionSize = sizeof(ElementType); template<class T> class equal { public: virtual void* find(T f) { return NULL; } }; template<class T> class CStash:public equal<T> { private: unsigned char *storage; int quantity; int next; int size; void inflate() { int newQuantity = quantity + increase; int newBytes = (quantity + increase) * size; int oldBytes = next * size; unsigned char *e = new unsigned char[newBytes]; for(int i = 0; i < oldBytes; i++) e[i] = storage[i]; delete storage; storage = e; quantity = newQuantity; } public: CStash() { storage = 0; quantity = 0; next = 0; size = UnionSize; } void push_back(T *element) { if(next >= quantity) inflate(); int startBytes = next * size; unsigned char *e =(unsigned char *) element; for(int i = 0; i < size; i++) storage[startBytes + i] = e[i]; next++; } void * fetch(int index) { if(index > next || index < 0) return 0; else return &storage[index * size]; } virtual void* find(T f) //查找元素f { unsigned char * e = (unsigned char *) &f; for(int i = 0; i < next * size; i += size) { bool ok = true; for(int j = 0; j < sizeof(f); j++) { if( storage[i + j] && e[j] && storage[i + j] != e[j]) { ok = false; break; } } if(ok) { return &storage[i]; } } return NULL; } void cleanup() { next = 0; quantity = 0; delete[] storage; storage = 0; } }; int main() { ElementType *t = new ElementType(122, 'c'); CStash<ElementType> *cs = new CStash<ElementType>(); cs->push_back(t); ElementType *tt = (ElementType*)cs->fetch(0); ElementType t2 = ElementType(122, 'c'); tt = (ElementType *)cs->find(t2); cout << tt->i << " " << tt->c << endl; /* ElementType t = 120; ElementType *p = &t; cs->push_back(p); t = 20; cs->push_back(p); t = 33; cs->push_back(p); t =12; cs->push_back(p); ElementType *tt = (ElementType *)cs->fetch(1); printf("%d\n", *tt); tt = (ElementType *)cs->find(33); printf("%d\n", *tt); tt = (ElementType *)cs->find(11); if(tt == NULL) puts("NULL"); */ //cs->cleanup(); return 0; }
不错在写程序的时候发现了一个好玩的问题, 亲身体会到了结构体在分配内存的时候内存偏移现象, 这个现象导致了很多问题,切记小心呀
由于结构体是先一个int型,后面3个char型, 那么可以看见sizeof(f)是8, 这个时候的最大单元是int型为4, 也就是说最小需要两个4, 所以是8;
那么就是说如果我的结构体只有3个char型, 那么一共开了8个byte, 也就是说int占领了前四个, 而char只能栈4 - 6(从0开始的), 那么最后一位byte怎么办呢,
可以从图上卡到storage[i+j] 的值是一个问号, 代表什么都不是,什么都没有,当然也不是NULL(你要是问谁是NULL, 我告诉你storage[1 - 3]是NULL,因为一个储存单元只认识首地址storage[0]) , 其实我也不知道storage[7]到底是什么, 我郁闷了, 但是有谁知道的能给我留言吗