Variable size array

Question

I am working on my first big project and I need variable size arrays (Or giant fixes sized arrays, I am basically creating a new programming language 'so yeah')

I would like at least these functions:

ARRAY_NEW(type, arr) // Or something else for the arguments: Be creative :)
ARRAY_FREE(arr)
ARRAY_PUSH(arr, item)
ARRAY_POP(arr)
ARRAY_SIZE(arr)
// Optional, but would increase performance
ARRAY_ADD(arr, index, item)
ARRAY_REMOVE(arr  index)
ARRAY_SPLIT(arr, index, length)
ARRAY_MAP(arr, lambda) // Macros suck? You suck!

I have used a couple of methods to implement these variable sized arrays:

Macro's for creating a _length suffix for every array name (I called this one ARRAY)

#define NEWARRAY(type, name) (type* name = NULL; size_t name ## _length = 0;)
NEWARRAY(int, array);

Macro's for storing length in array - cells - 1 where cells is the number of cells needed to store a size_t: (Called ARRAYLIST)

char[] array:
0 0 0 1 4 97

Would be a array with length 1 and value ['a'] (array[0] would return 'a' with my implementation, which is what I like) Note: So far this is my only data type with ARRAY_ADD and ARRAY_REMOVE implemented

Storing all arrays in a custom data type: (How about ARRAYTYPE?)

struct ArrayType {
    int length;
    void** values;
}

I'm currently experimenting with chunked arrays (new memory allocated every few PUSHes) (Lets call it CHUNKEDARRAY I think it will store length like I did with a ARRAYLIST.

I mostly use 2, and sometimes 1 (Since 2 is 100% safe where 1 will fail if the name_length is already declared (Making it... 99% safe) I don't really use 3 alot unless peformance is a issue, because typing array.values[0] takes more time to write and looks worse)

Can you give me some more tips 'n tricks on making variable sized arrays easier? What do you use? Any comments on my current approach? Any more datastructures that are variable size and implementable in C? I am struggeling with variable sized arrays for quite a while now.

score 0 · Answer 1 · edited May 23 '17 at 12:22

Fist of all there would be a linked list. Simple:

----------        ----------
- Data   -        - Data   -    
----------        ----------   
- Pointer- - - -> - Pointer-  
----------        ----------

but you can also use a double-linked list.

Then there would be a heap data structure. Those are very efficient for sorting and/or data access in O(log(n)) time.

You can use a linked list or a heap as a substitution for simple arrays. You can sort them with various algorithms in e.g. O(n log(n)) time and they don't have a lot of computational overhead when it comes to resizing them (add/remove) - that's quite different to classic arrays which always have to be copied as you might already know.

Then my favorite: The don't re-invent the wheel(especilly not for "big" projects)-data-structure or "library" like some people call it.

Of course there are hash-maps/sets/tables too one might find useful to have data access in O(1) time.

Variable size array

1 Answers1