How to create a dynamic array vector without using stl?

Question

I have to create and do some operations with dynamic array "vector", but without using stl and malloc. It should be in c. I have no idea how to do it, I googled it but all what I found is information about "vectors" in stl and no malloc(

Answer 1

If I'm understanding the question correctly, you are being asked to implement a dynamic data structure (a vector) without relying on malloc or other library routine to manage dynamic memory.

This means you have to create and manage your own memory pool; basically, declare a large-ish array and "allocate" memory from it to build your vector. You'll need a secondary data structure to track those allocations somehow. Something like the following:

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

This is very simplistic, almost to the point of being useless, but it should get you thinking in the right direction. The hard bit is figuring out where to grab the next chunk of memory (best fit, first fit, etc.), how to deal with fragmentation, etc.

And this doesn't even get into building the vector itself!

Answer 2

Here is a small proof-of-concept program that uses file I/O. It stores the length of the vector as an unsigned int at the beginning of the file, with the int values following.

It can push and pop values, and has random access (get). Removing values from the middle or beginning of the vector is up to you (it involves shifting all the values around).

Beware that it does no (error) checking whatsoever, that too is left as an exercise to the reader.

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