动态数组

问题，用到一个顺序表，第一点是这个顺序表较大，而且为了维持最小的内存占用需要用动态数组实现，但是由于顺序表较大，所以realloc增长空间时，有可能会进行大量数据的迁移，费时费力，当然可以在realloc的时候不严格按照所需空间大小分配，而是按照设定好的步长增长，比如一次增加一倍长度，但这又不满足空间占用最小的要求，所以就很矛盾；第二点是这个顺序表中的一部分是稀疏的，就是很多的存储空间是没有存储元素的，而这些位置在表的中间部分，无法释放掉，强迫症就很矛盾。

所以使用简单的分块方式实现了这个顺序表：还需要实现空块的快速释放才好使。

#pragma once

#include <string.h>
#include <stdlib.h>

typedef unsigned char BYTE;

template<typename T>
class SeqListPlus {
public:
	SeqListPlus();
	~SeqListPlus();

	T* insert(T& elem, size_t index);
	void erase(size_t index);

private:
	BYTE** pool;
	size_t blockElemCount; /* 每块可容纳元素数 */
	size_t virtualBlockCount; /* 块索引表长 */

	size_t virtualLength();

	void addVirtualBlocks();
	void addBlock(size_t blockIndex);

	static const size_t BLOCK_SIZE = 1024 << 2; /* 每块大小4KB */
	static const size_t MAX_BLOCKS = 1024 << 8; /* 最大空间1GB */
};

template<typename T>
inline size_t SeqListPlus<T>::virtualLength()
{
	return virtualBlockCount * blockElemCount;
}

template<typename T>
void SeqListPlus<T>::addVirtualBlocks()
{
	size_t newVirtualBlockCount = virtualBlockCount + 1024; /* 块索引表扩容1024即虚拟块数增加1024 */

	if (newVirtualBlockCount >= MAX_BLOCKS) exit(1); /* 检查合法性 */

	BYTE** newPool = (BYTE**)realloc(pool, sizeof(BYTE*) * newVirtualBlockCount);
	if (!newPool) exit(1);
	pool = newPool;

	for (size_t i = virtualBlockCount; i < newVirtualBlockCount; ++i) *(pool + i) = NULL;
	virtualBlockCount = newVirtualBlockCount;
}

template<typename T>
void SeqListPlus<T>::addBlock(size_t blockIndex)
{
	if (blockIndex >= MAX_BLOCKS) exit(1); /* 检查合法性 */

	while (blockIndex >= virtualBlockCount) addVirtualBlocks(); /* 增加虚拟块 */

	if (*(pool + blockIndex)) return; /* 此块已分配 */

	/* 分配目标快 */
	*(pool + blockIndex) = (BYTE*)malloc(BLOCK_SIZE);
	if (!*(pool + blockIndex)) exit(1);
	memset(*(pool + blockIndex), 0, BLOCK_SIZE);
}

template<typename T>
SeqListPlus<T>::SeqListPlus()
{
	this->pool = NULL;
	this->virtualBlockCount = 0;
	this->blockElemCount = BLOCK_SIZE / sizeof(T);
}

template<typename T>
SeqListPlus<T>::~SeqListPlus()
{
	if (pool) {
		for (size_t i = 0; i < virtualBlockCount; ++i) {
			if (*(pool + i)) {
				free(*(pool + i));
				*(pool + i) = NULL;
			}
		}
		free(pool);
		pool = NULL;
	}
}

template<typename T>
T* SeqListPlus<T>::insert(T& elem, size_t index)
{
	size_t blockIndex = index / blockElemCount;
	size_t offset = (index % blockElemCount) * sizeof(T);
	
	if (blockIndex >= virtualBlockCount || *(pool + blockIndex) == NULL) addBlock(blockIndex);

	return (T*)memcpy(*(pool + blockIndex) + offset, &elem, sizeof(T));
}

template<typename T>
void SeqListPlus<T>::erase(size_t index)
{
	size_t blockIndex = index / blockElemCount;
	size_t offset = (index % blockElemCount) * sizeof(T);

	if (blockIndex >= virtualBlockCount || *(pool + blockIndex) == NULL) return;

	memset(*(pool + blockIndex) + offset, 0, sizeof(T));
}

本文地址：https://blog.csdn.net/gigggg/article/details/109016711