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:
Code:
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