C++ vector equivalent in C

Question

I have a code (C++) that looks like this

vector<int> values[10000];

int i, j; 
while (.....) {
    scanf("%d%d", &i, &j);
    values[i].push_back(j);
    values[j].push_back(i);
}

but I want to rewrite this code to C. How can I do this?

I researched the opportunity to make the own stack, but maybe have more lightweight way to rewrite this code, maybe two-dimensional arrays. So far I can not think how this remake, I hope that someone more experienced tell me how to do it :)

Sorry guys, added a more advanced example...

Answer 1

Instead of rolling your own, you may want to try a C container library, e.g. http://code.google.com/p/ccl/

Answer 2

You can use Gena library. It closely resembles stl::vector in pure C89.

You can check it out here:

https://github.com/cher-nov/Gena

Answer 3

A rough equivalent of a C++ vector would be a resizing C array (to account for more elements than available).

Ergo, the equivalent of an array of vectors would be an array of pointers (an array of arrays wouldn't cut it because of the resizing constraint).

int* values[1000];

You'll need to account for the sizes though, so you could either do that externally or wrap the logic inside a structure.

int sizes[1000];
int noElements[1000];
// all sizes and noElements initially 0

for (int i = 0; i < 10; i++) {
    if ( noElements[i] >= sizes[i] )
    {
        // allocate more memory for values[i];
        // copy old contents into the new memory
        // update sizes[i]
    }
    values[i][noElements] = 10;
    noElements++;
}

Answer 4

Something like this:

#include <stdio.h>
#include <stdlib.h>


typedef struct _darray
{
    size_t size;
    size_t actual_size;
    int *content;
} darray;


void darray_create(darray *d)
{

    d->actual_size = d->size = 0;
    d->content = NULL;
}

void darray_append(darray *d, int v)
{
    if (d->size+1 > d->actual_size)
    {
    size_t new_size;
    if (!d->actual_size) 
    { 
        new_size = 1;
    }
    else
    {
        new_size = d->actual_size * 2;
    }
    int *temp = realloc(d->content, sizeof(int) * new_size);
    if (!temp)
    {
        fprintf(stderr, "Failed to extend array (new_size=%zu)\n", new_size);
        exit(EXIT_FAILURE);
    }
    d->actual_size = new_size;
    d->content = temp;
    }
    d->content[d->size] = v;
    d->size++;
}

const int* darray_data(darray *d)
{
    return d->content;
}


void darray_destroy(darray *d)
{
    free(d->content);
    d->content = NULL;
    d->size = d->actual_size = 0;
}


size_t darray_size(darray *d)
{
    return d->size;
}


int main()
{
    int i;
    darray myarray;
    const int *a;

    darray_create(&myarray);

    for(i = 0; i < 100; i++)
    {
    darray_append(&myarray, i);
    }
    a = darray_data(&myarray);
    for(i = 0; i < darray_size(&myarray); i++)
    {
    printf("i=%d, value=%d\n", i, a[i]);
    }
    darray_destroy(&myarray);
}

Answer 5

You can try something like this:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct vector
{
    int len;
    int allocated;
    int step;
    int *data;
};


#define INIT_SIZE 1


void init_vector(struct vector *v)
{
    v->len = 0;
    v->allocated = 0;
    v->step = 2;
    v->data = NULL;
}


int append(struct vector *v, int item)
{
    if (!v->data)
    {
        v->data = malloc(INIT_SIZE * sizeof(int));

        if (!v->data)
            return -1;

        v->allocated = INIT_SIZE;
    }
    else
        if (v->len >= v-vallocated)
        {
            int *tmp = realloc(v->data, 
                        v->allocated * v->step * sizeof(int));

            if (!tmp)
                return -1;

            v->data = tmp;
            v->allocated *= v->step;
        }

    v->data[v->len] = item;
    v->len++;

    return 0;
}


int delete(struct vector *v, int index)
{
    if (index < 0 || index >= v->len)
        return -1;

    memmove(v->data + index, v->data + index + 1,
                      (v->len - index - 1) * sizeof(int));
    v->len--;

    return 0;
}


void print(const struct vector *v)
{
    printf("Array:\n");

    for (int i = 0; i < v->len; i++)
        printf("%d ", v->data[i]);

    printf("\n");
}


int main(void)
{
    struct vector v;
    int rc;

    init_vector(&v);

    rc = append(&v, 1);
    assert(rc == 0);

    rc = append(&v, 2);
    assert(rc == 0);

    rc = append(&v, 3);
    assert(rc == 0);

    rc = append(&v, 4);
    assert(rc == 0);

    rc = append(&v, 5);
    assert(rc == 0);

    print(&v);

    rc = delete(&v, 2);
    assert(rc == 0);

    print(&v);

    free(v.data);

    return 0;
}

Answer 6

There is no C standard equivalent to the c++ vector, though you could create a struct based off of the vector in c++. The struct would

• Resize itself if the array bounds are passed the max size
• perform the operations similar to that of a vector

OR

• Create a linked list stack struct that simulates that of a c++ vector

Answer 7

I'm affraid you'll have to work with heap memory in 80's fashion in the plain C.

typedef struct tagArrayDesc {
  int* arr;
  size_t top;
  size_t reserved;
} ArrayDesc;

#define EC(NAME, T) size_t ensure_capacity##NAME##(size_t size,            \
                                                   T** vec,                \
                                                   size_t reserved)        \
{                                                                          \
  size_t new_reserved;                                                     \
  new_reserved = reserved;                                                 \
  if (reserved < size) {                                                   \
    if (reserved != 0) {                                                   \
      new_reserved *= 2;                                                   \
    } else {                                                               \
      new_reserved = 0x10;                                                 \
    }                                                                      \
  }                                                                        \
  if (new_reserved < size) {                                               \
    new_reserved = (size * 4) / 3;                                         \
  }                                                                        \
  if (new_reserved > reserved) {                                           \
    *vec = realloc(*vec, sizeof(**vec) * new_reserved);                    \
    memset((*vec) + reserved, 0, sizeof(T) * (new_reserved - reserved));   \
  }                                                                        \
  return new_reserved;                                                     \
}

EC(_int, int)
EC(_array_desc, ArrayDesc)

int main()
{
  ArrayDesc* rows = NULL;
  size_t rows_size = 0;
  size_t rows_reserved = 0;
  while (true) {
    int i, j;
    scanf("%d%d", &i, &j);
    rows_reserved = ensure_capacity_array_desc(i + 1, &rows, rows_reserved);
    rows[i].reserved = ensure_capacity_int(j + 1, &rows[i].arr, rows[i].reserved);
    rows[i].arr[j] = 42;
  }
  return 0;
}

Answer 8

You have to work with dynamic memory allocation. It's not hard. Every time when a new item must be inserted just use realloc. Somethink that looks like this:

#include <cstdlib>

typedef struct { } UserType;

int currentSize = 0;
UserType* values;

/// Add new value to values method
void addValue(const UserType& newValue)
{
    ++currentSize;
    values = static_cast<UserType*>(realloc(values, currentSize));
    if (values == NULL)
        // memory allocation filed, place fix code here
        *(values + currentSize) = newValue;
}

Remember, u have to use free for free memory of the values. Also, you may don't free allocated memory if will end work right now.