c - 如何在不使用 stl 的情况下创建动态数组向量？

Question

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

Answer 1

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

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

#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
} 

这非常简单，几乎到了无用的地步，但它应该让你朝着正确的方向思考。难点在于找出在哪里获取下一块内存（最适合、最适合等），如何处理碎片等。

这甚至不涉及构建向量本身！

Answer 2

这是一个使用文件 I/O 的小型概念验证程序。它将向量的长度存储为unsigned int文件开头的an，int后面是值。

它可以推送和弹出值，并具有随机访问权限 ( get)。从向量的中间或开头删除值取决于您（它涉及移动所有值）。

请注意，它不会进行任何（错误）检查，这也留给读者作为练习。

#include <stdio.h>

/* read & write the length, return new length */
unsigned int updateLength(FILE * vector, int difference){
    unsigned int length;

    rewind(vector);
    fread(&length, 1, sizeof(unsigned int), vector);
    rewind(vector);
    length += difference; /* no error checking! */
    fwrite(&length, 1, sizeof(unsigned int), vector);

    return length;
}

/* append a value to the vector */
void push(FILE * vector, int value){
    unsigned int length = updateLength(vector, 1) - 1;

    /* write value */
    fseek(vector, length * sizeof(int) + sizeof(unsigned int), SEEK_SET);
    fwrite(&value, 1, sizeof(int), vector);
}

/* return the last element, can't actually remove it from the file, but the
length is updated */
int pop(FILE * vector){
    unsigned int length = updateLength(vector, -1);
    int value;

    fseek(vector, length * sizeof(int) + sizeof(unsigned int), SEEK_SET);
    fread(&value, 1, sizeof(int), vector);

    return value;
}

/* get a value from the vector, doesn't check if pos is valid! */
int get(FILE * vector, unsigned int pos){
    int ret;

    fseek(vector, pos * sizeof(int) + sizeof(unsigned int), SEEK_SET);
    fread(&ret, 1, sizeof(int), vector);

    return ret;
}

/* initialise the file: write the length (0) */
void init(FILE * vector){
    unsigned int length = 0;

    fwrite(&length, sizeof(unsigned int), 1, vector);
}

int main(){
    FILE * vector = fopen("vector.dat", "w+b");
    int v1, v2, v3;

    init(vector);
    push(vector, 12);
    push(vector, 123);
    push(vector, 1234);

    v1 = pop(vector);
    v2 = pop(vector);
    v3 = pop(vector);

    printf("%i %i %i\n", v1, v2, v3);

    fclose(vector);

    return 0;
}