c - stlを使わずに動的配列ベクトルを作成するには?

Question

動的配列「ベクトル」を使用していくつかの操作を作成して実行する必要がありますが、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、ファイルの先頭に として保存され、その後に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;
}