现在的位置: 首页 > 综合 > 正文

c/c++实现的一个动态分配内存的结构体数组(类似vector)

2013年04月24日 ⁄ 综合 ⁄ 共 6115字 ⁄ 字号 评论关闭

这个数组可以向里面插入任何类型,包括自定义类型, 程序只是实现了基本功能,还有待完善,

首先初始化,然后就可以插入数据了, 当储存单元不足的时候就自动增加储存单元

由于总的风格是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]到底是什么, 我郁闷了, 但是有谁知道的能给我留言吗

抱歉!评论已关闭.