C++ vector function implentation in C

[Monado_III]

I'm rewriting a program that uses several C++ exclusive functions and operators, such as new, vectors and vector functions (begin, end, push_back, at). I'm trying to implant the program in straight C and I'm not sure how to replace the vector functions (the vectors themselves I replaced with arrays), I've replaced the new with a malloc and push_back with realloc. Would that be the right way to do it? and How would I replace those other functions?

 

[spoonm]

I'm not familiar with vectors or C++ overall, but have you tried implementing other data structures? AFAIK, the vectors you're talking about are "dynamic arrays", lists, to which you can add or remove any element of the list type, right?

With linked lists in C, you can implement a data structure like this:

NULL <-> some node structs <-> NULL
some node structs -> NULL
NULL <- node *start <-> some node structs <-> node *end -> NULL

They can have a single link(meaning you'll navigate through it from one end, always going forward or backwards), two links(meaning you can navigate forwards and backwards), or n links(at which point you have something more complex than just a list).

Here is a double linked list implementation, made with "sentinel nodes", or node *start and node *end, that both don't really matter, but have the same memory fingerprint as a regular data-filled node:

C
#include <stdlib.h>

typedef struct list list_type;
typedef struct node node_type;

struct list
{
    node *start, *end;
    unsigned int length;
};

struct node
{
    node *next, *prev;
    data_type data;
};

int
create_list(list_type *l)
{
    if ((l->start = malloc(sizeof (node_type))) == NULL ||
        (l->end   = malloc(sizeof (node_type))) == NULL)
    {
        perror("Error allocating memory");

        /* Handle the error your way. This time I just return a non-zero value. */

        return 1;
    }

    /* You have to link the sentinel nodes, now. */
    l->start->prev = l->end->next = NULL;
    l->start->next = l->end;
    l->end->prev = l->start;

    l->length = 0;

    return 0;
}

int
insert_start(list_type *l, data_type dat)
{
    node_type *new;

    if ((new = malloc(sizeof (node_type))) == NULL)
    {
        perror("Error allocating memory for new node");

        /* Handle the error. This time I just return a non-zero value. */

        return 1;
    }

    /*
     * You have to copy the data into the new node. There are ways to do this if your data type
     * Is more complex than a basic data type or struct where you can simply make a shallow copy.
     */
    new->data = dat;

    /* Now change the list. */
    new->next = l->start->next;
    new->prev = l->start;

    l->start->next->prev = new;
    l->start->next = new;

    l->length++;

    return 0;
}

/* Functions go on and on... */

You can take advantage of pointers and make your own functions to have the list behave the way you want it to. As for the data type, you can use preprocessor directives to create templates. I did so for my data structures class months ago, but my templates sucked big time.

Here's a link to the repo where I put the template-y stuff I made: https://github.com/skewerr/dtstruct

 

[Monado_III]

I'm not familiar with vectors or C++ overall, but have you tried implementing other data structures? AFAIK, the vectors you're talking about are "dynamic arrays", lists, to which you can add or remove any element of the list type, right?

With linked lists in C, you can implement a data structure like this:

NULL <-> some node structs <-> NULL
some node structs -> NULL
NULL <- node *start <-> some node structs <-> node *end -> NULL

They can have a single link(meaning you'll navigate through it from one end, always going forward or backwards), two links(meaning you can navigate forwards and backwards), or n links(at which point you have something more complex than just a list).

Here is a double linked list implementation, made with "sentinel nodes", or node *start and node *end, that both don't really matter, but have the same memory fingerprint as a regular data-filled node:

C
#include <stdlib.h>

typedef struct list list_type;
typedef struct node node_type;

struct list
{
    node *start, *end;
    unsigned int length;
};

struct node
{
    node *next, *prev;
    data_type data;
};

int
create_list(list_type *l)
{
    if ((l->start = malloc(sizeof (node_type))) == NULL ||
        (l->end   = malloc(sizeof (node_type))) == NULL)
    {
        perror("Error allocating memory");

        /* Handle the error your way. This time I just return a non-zero value. */

        return 1;
    }

    /* You have to link the sentinel nodes, now. */
    l->start->prev = l->end->next = NULL;
    l->start->next = l->end;
    l->end->prev = l->start;

    l->length = 0;

    return 0;
}

int
insert_start(list_type *l, data_type dat)
{
    node_type *new;

    if ((new = malloc(sizeof (node_type))) == NULL)
    {
        perror("Error allocating memory for new node");

        /* Handle the error. This time I just return a non-zero value. */

        return 1;
    }

    /*
     * You have to copy the data into the new node. There are ways to do this if your data type
     * Is more complex than a basic data type or struct where you can simply make a shallow copy.
     */
    new->data = dat;

    /* Now change the list. */
    new->next = l->start->next;
    new->prev = l->start;

    l->start->next->prev = new;
    l->start->next = new;

    l->length++;

    return 0;
}

/* Functions go on and on... */

You can take advantage of pointers and make your own functions to have the list behave the way you want it to. As for the data type, you can use preprocessor directives to create templates. I did so for my data structures class months ago, but my templates sucked big time.

Here's a link to the repo where I put the template-y stuff I made: https://github.com/skewerr/dtstruct

Ok, thanks for the help, I think I'll do that

 

[spoonm]

C doesn't have a resource like "Vector<type>" to create a vector of a given type, but you can use preprocessor directives and a bit of fiddling to make something more generic. I think I failed to explain that in a way it'd be clear to you, so allow me to compensate: do you use Telegram? Skype? E-mail? If you're interested, I can help through those so I don't spam GBAtemp with impertinent posts. Instant messaging allows me to respond faster, and using e-mails allows me to reply to you when I'm not home.