c - 如何在不使用STL的情况下创建动态数组 vector ？

Question

我必须使用动态数组“vector ”创建并执行一些操作，但不使用 STL 和 malloc。它应该在c中。我不知道该怎么做，我用谷歌搜索了它，但我发现的只是有关 STL 中“vector ”的信息，没有 malloc(

Answer 1

如果我正确理解了这个问题，那么您将被要求实现动态数据结构( vector )，而不依赖于 malloc 或其他库例程来管理动态内存。

这意味着您必须创建和管理自己的内存池；基本上，声明一个大型数组并从中“分配”内存来构建 vector 。您将需要一个辅助数据结构来以某种方式跟踪这些分配。类似于以下内容:

#define MEMORY_SIZE ...
#define MAX_ALLOCS ...

static unsigned char memory[MEMORY_SIZE];

struct allocation_record {
  unsigned char *start;
  size_t length;
  struct allocation_record *next;
};

struct allocation_record *allocs;

void *myalloc( size_t size )
{
  // create a new allocation record
  // find the next available chunk of "memory" that
  //     can satisfy the request
  // set the allocation record to point to that chunk of "memory"
  // add the allocation record to the allocs list
  // return the start pointer in the allocation record
}

void myfree( void *ptr )
{
  // search the list of allocation records for one with a
  //    start member that matchs ptr
  // mark that memory as available *or* remove the allocation
  //     record from the list
} 

这非常简单化，几乎到了无用的地步，但它应该让你思考正确的方向。困难的地方是弄清楚在哪里获取下一 block 内存(最适合、最先适合等)、如何处理碎片等。

这甚至没有涉及构建 vector 本身!