6

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...

3
  • 8
    Just to make sure: you want 10000 vectors and to push the number 10 as the first element of the first 10 vectors? Dec 29, 2012 at 17:40
  • 2
    Clarify exactly what you want and what operations you require. All the operations vector provides?
    – Pubby
    Dec 29, 2012 at 17:40
  • No, only .push_back() and .size()
    – Alex
    Dec 29, 2012 at 18:09

8 Answers 8

8

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

2
  • Thx, but I want do it without additional external libraries
    – Alex
    Dec 29, 2012 at 18:05
  • 1
    I don't understand the intention of people who always want to eschew extra libraries. Why would you want to reinvent the wheel? Dec 11, 2015 at 0:42
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

1

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);
}
1
  • This is an implementation of vector . OP's code has an array of 10,000 of these, so the main will have to start off darray myarray[10000] = { 0 }; and then darray_append(&myarray[i], i); and so on. Pro tip, we can use aggregate initialization since all-zero is actually the creation state
    – M.M
    Dec 10, 2015 at 23:10
1

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

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++;
}
1
  • 1
    It should probably be pointers to a struct { int value; int size; } so you know the array bounds.
    – Pubby
    Dec 29, 2012 at 17:44
0

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
2
  • 3
    A class? In C? (obviously you can simulate classes with structs, is that what you mean?)
    – Pubby
    Dec 29, 2012 at 17:43
  • sorry, i really do need some sleep. Dec 29, 2012 at 17:43
0

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;
}
2
  • This doesn't do the same thing as the original code. That was a (conceptual) 2-D array, whereas your code is a 1-D array that you push two ints onto at a time.
    – M.M
    Dec 10, 2015 at 23:05
  • @M.M: Whoops, that's gonna be a little more messy Dec 10, 2015 at 23:43
0

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.

2
  • Note that calling realloc() before every single value-insertion is very inefficient -- in a real application, you'd probably want to allocate extra space in your realloc() call, so that you only have to call realloc() occasionally. Dec 2, 2018 at 4:12
  • The point of having a dynamic array is you also want to remove elements. You still need some way to keep track of empty slots in the block after elements have been removed. A block and realloc() is all well and good but you really need a data structure that features like a linked list.
    – user3091673
    Oct 3, 2019 at 23:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.