C99/C11 dynamic array that mimics C++'s std::vector

https://solarianprogrammer.com/2017/01/06/c99-c11-dynamic-array-mimics-cpp-vector/

by AlexeyBrin • 10 years ago

84 158 10 years ago

tines15• 10 years ago

What if we want to be able to store more than integers in our dynamic array ? [...] The array_push_back function also needs to be refactored in order to account for the size and type of what we store in the data buffer. A possible approach is to use a macro, instead of the original function:

This is a situation where C++ really shines: you can use C++ with templates and not only have much cleaner code, but also avoid forcing the compiler to inline every single call to array_push_back. And you don't even need to use anything more than structs and functions, you don't need to go "full OO".

I wish C programmers would be more open to C++ but it seems like they're for the most part pretty closed. That's probably the C++ community's fault, but I'm not sure how to make amends.

noselasd• 10 years ago

In that regards, I also think C++ programmers should be more open to C programmers that just needs a few new language constructs.

It is not an all or nothing approach. It's fine to write code that looks and feels mostly like C, but still takes advantage of a few nice C++ features.

tines15• 10 years ago

I agree, which is why I mentioned that you can do what this article suggests without using anything except functions and structs. No classes or class features required.

blub• 10 years ago

There are perfectly legitimate use-cases for such a "C+" style. The disadvantage is that it won't be considered "good C++ style" and would limit the attractiveness of the project to C++ programmers that enjoy modern C++.

If one would include vector, string, array, smart pointers and maybe simple template code in C+ it would already have a big safety advantage over plain C.

Vindicis• 10 years ago

That's pretty much how I use C++. Granted, my knowledge of it is very minimal. I was forced into C++ because of my Broker's api so...

One of my largest gripes making the switch, is the OO paradigm. I get it, I understand it, and I really want to love it. But the theory of it vs. the implementations that I've seen, ugh. And the number of ways you can initialize variables etc... just makes no sense to me. It's like they just keep adding new ways to do things, for no other reason than because they can. What's wrong with only have one way to do simple things like that?

I don't know, maybe it's just me but I strive to keep my code as simple, concise as I possibly can. I have enough complexity to deal with solving problems than having to wrestle with my language on top of it. Just to note, I'm strictly talking about having to use other people's code merged with my own. If it was solely me writing, I'd just use C++ for some of the nice things built in and toss classes and all that into the fire. YMMV.

pjmlp6• 10 years ago

The thing is, we get dispointed when the code just looks like "C compiled with C++ compiler", with all security exploits that entails.

A good example is how Turbo Vision, Object Windows Library, Visual Components Library, Qt look like and the concessions Microsoft had to make to Afx so that it got rebranded into MFC and appealed to the Windows C developers.

1wd4• 10 years ago

The term "C with classes" is almost used as an insult in some circles. I wonder if "C++ without classes" would be a better idea.

CyberDildonics3• 10 years ago

It's always just one or two more features and before you know it - C++

cefstat• 10 years ago

Yes, despite all the problems in C++ it's just a much better language than C for defining new types that are on par with "native types". std::vector has so many benefits over any possible C implementation that there is no real comparison. Genericity is one, no need to remember to free after use is another.

By the way, why is this C implementation something that requires C99 or C11 features? It looked just like standard old-fashioned ANSI C to me.

pskocik7• 10 years ago

I like my C alternative better. I pass growth factors/increments as parameters to the vector macros so that I can affect how it grows on capacity exhaustion during each call and I have macros for creating and closing uninitialized gaps. C++ loses on many potential optimizations by insisting that its types always be in fully well-defined states except inside methods. Moreover the particular GNU implementation of the STL on Linux completely fails to turn certain vectors methods into memsets, memcpies and memmoves where it could, which pesimizes those particular ops by like two decimal orders of magnitude. The insistence on using new/delete based allocators instead of reallocs is a significant pessimization too. Reallocs perform, on average, several tens of percents better than new allocs followed by copies. An even more noticable pessimization is in the compilation times. Including `<vector>` adds good chunks of a second to the build time of an average-length translation unit. In comparison, working with C, even with all my generics included, on top of a good build system makes me feel as if I was working with a scripting language. No lags.

necessity• 10 years ago

More like the clusterfuck that the language is than the community.

pskocik7• 10 years ago

In my codebase, I use expression macros (with a little bit of __typeof__-based type checks) to do it fully generically. Much of what you think you need C++ for can be done almost just as succinctly on top of plain C (I'm talking automated scope cleanups, semi-automated error handling, many generic things) and the compile times fly. I agree C++ has had some good ideas. In fact, I originally wanted to use it. But I came to the conclusion that it's too bloated, and more importantly, fundamentally broken in certain ways (RAII, exceptions, even templates and namespaces), and I ended up emulating what I think the good parts of C++ are on top of plain C. When C++ programmers think C, they usually think lack of generics and lots of explicit manual, micromanagement and pointer arithmetic, but it can be a lot more than that.

tines15• 10 years ago

I'm not familiar with this approach, but I think it would entail code size increase for each use of the macros, and a runtime overhead for the typeof checks, correct?

If so, C++ has a nice advantage in that all the type checks are at compile-time so you don't pay any more for those, and also you don't duplicate binary code with macros.

paxcoder• 10 years ago

Unfortunately __typeof__ is non-standard. Despite its usefulness it always gets left out of the standard (and with weird excuses, I think last time it was lack of implementations - despite the fact that eg. both GCC and LLVM implement it).

Interestingly, C11 defines _Generic selection, a kind of a switch for types, but its usefulness is hindered by the fact that it cannot be used in conjunction with sizeof.

hendzen3• 10 years ago

What is fundamentally broken about RAII? To me that is one of the killer features of C++ over C, which requires manual goto statements to achieve something approaching RAII.

72deluxe8• 10 years ago

I hope this comment is some sort of weird joke.

What's broken about namespaces? If I create a class named Bitmap whilst using Windows.h, will I conflict with GDI::Bitmap???

RAII - how can you possibly guarantee safe lifetimes of objects without RAII?

Templates - do you like writing the same thing a million times and having to update it and fix it in those million places?

throwaway89121• 10 years ago

I want something like std::vector, but I don't want exceptions. How does C++ help in this case?

ensiferum2• 10 years ago

std::vector is a container in a c++ standard library. C++ is a language. You're mixing apples and oranges.

What I'm saying is that you can use C++ without having to use STL and you can use C++ just fine to implement your own exceptionless container if you want (and many such implementations exist already).

And you can also compile with exceptions disabled. Should your code throw it will terminate the process.

tines15• 10 years ago

It will help you either use std::vector with a custom allocator that does not throw exceptions, or else write your own non-throwing vector class with templates, which would, I hope, be more maintainable and easier to use correctly than an equivalent written in C.

hendzen3• 10 years ago

Compile with -fno-exceptions

72deluxe8• 10 years ago

You can use any part of C++ without having to use the rest of it. For example, you don't have to write your own std::allocator to use std::vector, nor do you have to use exceptions.

You can use which bits of C++ that you want - that's its great strength, permitting low-level behaviour whilst supporting high level abstractions (and as simple or as complex as you like).

jokoon2• 10 years ago

A solution might be a minimal subset of C++, so with STL containers, some syntactic sugar, easier and faster to compile (modules), etc.

Basically what go and rust have achieved, except you keep most of the C/C++ syntax "taste", and you remove too high level stuff like templates and inheritance. Honestly I don't think templates are so useful, since most programmers already re-use STL containers, which are templates, but nobody really write relevant template classes.

That's probably the C++ community's fault

The problem with C++ is backward compatibility with C and big corporations trying to not break their codebase. It makes it very hard to make the language evolve. For example D is a very good language, but it can't gain momentum as long as it doesn't have a real way to gain presence. We just have to wait that corporation clean their codebase to make room for C++ compilers to adapt, and then things should improve.

tines15• 10 years ago

You can't have the STL containers without templates though. If you want to special-case them in the compiler, then what about the algorithms library? If you want to keep the algorithms library, then what about your own code that implements a higher-level algorithm using the lower-level ones in the algorithms library? Without templates you have to write your algorithm once for every type of container, or else use indirect function calls which would not be good. So this won't really work well I think.

For me, the only selling point of C++ is templates, and I've never written a nontrivial program that didn't use them (and I like to think that I don't just use them frivolously).

72deluxe8• 10 years ago

You do realise that STL containers fundamentally rely on templates, right?

We use loads of template classes at where I work. Our code would not be maintainable without them.

mtdewcmu2• 10 years ago

The chief benefits to pure C IMO are that it's more portable, compiles faster, and it's a simple and stable language.

Writing C takes more effort in some cases, so it's a trade-off.

maxlybbert3• 10 years ago

It's goofy, but one of the reasons I'll pick C for a quick program is that both Windows and Linux will give better error messages for standard functions that fail and set errno than for equivalent C++ code that throws an exception.

This isn't a question about the language, it's definitely a quality-of-implementation issue for standard exceptions to have what() give a useful message.

Just to clarify perror will generally give a better error message in:

    FILE* fh = fopen("foo.txt", "w+");
    if (!fh) {
        perror("unable to open foo.txt");
        return 1;
    }

Than what() will in:

    std::fstream fs;
    fs.exceptions(std::ifstream::failbit | std::ifstream::badbit);
    try {
        fs.open("too.txt");
    }
    catch (const std::exception& ex)
    {
        std::cerr << "unable to open foo.txt: "
           << ex.what() << '\n';
    }

(Ignoring other issues such as whether exceptions are better than return codes, etc.)

rkv• 10 years ago

This is a situation where C++ really shines

I agree but passing in the size is really not much of a deterrent.

AlexeyBrin7• 10 years ago

you can use C++ with templates and not only have much cleaner code, but also avoid forcing the compiler to inline every single call to array_push_back

Actually, you really, really, really want to inline every call to push_back for std::vector. Here is a relevant presentation by Chandler Carruth https://www.youtube.com/watch?v=s4wnuiCwTGU . But, hey, you don't want to make the compiler work for you :).

aceperry• 10 years ago

I gave up on C++ right after I learned it. At the time, this was before the STL was part of the standard, it looked really cool but I could tell that it was easy to get into trouble and it would take years and years to be really good at it. When Java became popular, it looked like it solved a lot of the problems that I was afraid of with C++. But it was slow and really verbose compared to C++ and C. Recently, I heard someone say that today's C++ is not your grandfather's C++ and the speaker made some interesting comments about how much better it was. So I'm intrigued by it and definitely open to looking into the new C++.

Joky3• 10 years ago

Yep, worth giving another look: I couldn't stand C++ before C++11, and now I can't stand C anymore :)

jagger11• 10 years ago

With the use of defer http://pastebin.com/EXZuRAdT you could create it w/o the need to use array_free.

kzrdude3• 10 years ago

The dynamic memory allocation of the array's fields itself does not mimic std::vector, it's an extra indirection that C++ does not pay for. You can make it a non-opaque struct in C and copy it around.

tines15• 10 years ago

std::vector does indeed have at least one pointer member (otherwise you couldn't have a std::vector with automatic storage duration because the size would be unknowable) so there is some indirection. Maybe you're thinking of std::array?

kr72• 10 years ago

kzrdude is referring to the allocation of the Array struct on the heap. It should be something like this instead:

    Array array_create(size_t size, size_t sizeof_data) {
        Array result;
        result.size = size;
        result.capacity = size;
        if(size) {
            result.data = malloc(size * sizeof_data);
        } else {
            result.data = NULL;
        }
        return result;
    }

kzrdude3• 10 years ago

This C code is more like `std::unique_ptr<std::vector<T>>`, so now you might see where the extra indirection is located.

im3w1l• 10 years ago

Probably more efficient to store the data array inline, with a flexible array member. That way creating takes only one malloc, and destruction only one free.

krylon5• 10 years ago

Those are great. I haven't used C a lot in a long time, but I remember back when I wrote C code for a living that I ran into the exact situation flexible array members are made for around the time I also learned of them.

"That will solve my problem elegantly", I thought, but unfortunately, the compiler we used only understood C89, so my hands were tied.

userbinator3• 10 years ago

but unfortunately, the compiler we used only understood C89, so my hands were tied.

You can do it in C89 too, just allocate sizeof(header) + n * sizeof(element).

AlexeyBrin7• 10 years ago

Yes, but you can't use flexible array members with a void array. So you will need to have a specialized structure for every data type (or use some macro system to generate these).

It is an excellent alternative for numerics when you usually work with simple types like int and double.

to3m5• 10 years ago

This sort of approach is a pain to use, because you keep having to cast when you're in the debugger, and there's zero type safety. And I'm afraid I don't have much positive to say about something like "((Vector2i * )arr3->data)[0].x = 333".

You can do better than this!

What is an array? It's 3 variables: base, length and capacity. So why not decide that an array is just that. 3 variables of the right size and type.

    #define ARRAY(T,S) T S;size_t S##_length;size_t S##_capacity

Then you can make one like this:

    ARRAY(int,xs);

You'll also need to initialise and these destroy array "objects".

    #define ARRAY_INIT(S)     \
        do {                  \
            S=NULL;           \
            (S##_length)=0;   \
            (S##_capacity)=0; \
        } while(0)

    #define ARRAY_DESTROY(S) \
        do {                 \
            Array_Free(S);   \
            ARRAY_INIT(S);   \
        } while(0)

Add you'll probably want to add an item to an array too.

    #define ARRAY_ADD(S,X)                     \
        do {                                   \
            if((S##_length)>=(S##_capacity)) { \
                S=Array_Grow(S,                \
                             sizeof *S,        \
                             &(S##_length),    \
                             &(S##_capacity)); \
            S[S##_length++]=(X);               \
        } while(0)

So you might use them like this:

    ARRAY(int,xs);
    ARRAY_INIT(xs);
    for(int i=0;i<100;++i)
        ARRAY_ADD(xs,i);
    ARRAY_DESTROY(xs);

Array_Free is very simple, and Array_Grow is barely more complicated (however I wrote it off the cuff, so of course it could still be wrong). Both of these mainly exist just to keep stdlib.h out of the header.

    void Array_Free(void *p) {
        free(p);
    }

    void *Array_Grow(void *base,size_t stride,size_t *length,size_t *capacity) {
        *capacity+=*capacity/2;
        *capacity=MAX(*capacity,MAX(MIN_CAPACITY,*length));
        return realloc(base,*capacity*stride);
    }

Array accesses and iteration and the like are just done in the traditional way:

    for(size_t i=0;i<xs_length;++i) {
        printf("%d\n",xs[i]);
    }

Even performs nicely with -O0.

For a full implementation you'll probably also need a way of generating a static array. (I mainly found myself needing this for test code, which uses globals for convenience; most arrays I create normally are locals, or parts of structs.)

You'll also need a parameters list for use in a function declaration or definition, and a macro that expands to all 3 variables.

    #define ARRAY_PARAMS(T,S) T *S,size_t S##_length,size_t S##_capacity
    #define ARRAY_ARG(S) S,S##_length,S##_capacity

Like then you might have a function that takes a pointer to an "array":

    void FunctionThatTakesAnArray(ARRAY_PARAMS(T,*p));

And you call it like this:

    ARRAY(T,myarray);
    FunctionThatTakesAnArray(ARRAY_ARG(&myarray));

(I found this cropped up often enough that I needed the macro, but it was less common than I thought.)

There's more you can do, but the above is the long and the short of it.

This might all look terrible - or perhaps it sort of looks OK, but you're just not sure that it would actually work - but I've used this in a prototype project and thought it worked out well. (I've been using C for 20+ years, so hopefully even if I've got no taste, I've at least got a rough feel for what works out OK and what's going to end up a disaster.)

tines15• 10 years ago

This gets messy in a couple of ways; for example, what if you want to pass two of them to a function? Then the names of the parameters generated by the ARRAY_ARG macro will clash and you'll have to add a counter to it, etc. (Also I'm not sure that you can concatenate `* p` with `_length` in `S##_length` where `S` is `* p`, and the same thing for the other, but I understand what you meant.) You'll also have potentially very confusing errors for the users of your library when they happen to create a variable whose name collides with one that the macro generates. And those are just the cursory observations.

gravypod• 10 years ago

This is what the macros expand to.

From:

    $ cat test.c
    #define ARRAY(T,S) T S;size_t S##_length;size_t S##_capacity
    #define ARRAY_INIT(S)   \
            do {                \
                S=NULL;         \
                S##_length=0;   \
                S##_capacity=0; \
            } while(0)

    #define ARRAY_DESTROY(S) \
            do {                 \
                Array_Free(S);   \
                ARRAY_INIT(S);   \
            } while(0)
    #define ARRAY_ADD(S,X)                                 \
            do {                                               \
                if(S##_length>=S##_capacity)                   \
                    S=Array_Grow(S,sizeof &S,&S##_length,&S##_capacity); \
                S[S##_length++]=(X);                           \
            } while(0)


    void Array_Free(void *p) {
    	free(p);
    }

    void *Array_Grow(void *base,size_t stride,size_t *length,size_t *capacity) {
    	*capacity+=*capacity/2;
    	*capacity=MAX(*capacity,MAX(MIN_CAPACITY,*length));
    	return realloc(base,*capacity*stride);
    }

    #define ARRAY_PARAMS(T,S) T *S,size_t S##_length,size_t S##_capacity
    #define ARRAY_ARG(S) S,S##_length,S##_capacity


    void test(ARRAY_ARG(p), ARRAY_ARG(a))
    {
    }

    int main() {
    	ARRAY(int, myarray);
    	ARRAY(int, ourarray);
    	test(ARRAY_ARG(myarray), ARRAY_ARG(ourarray));
    }

To:

    $ gcc -E test.c
    # 1 "test.c"
    # 1 "<built-in>"
    # 1 "<command-line>"
    # 31 "<command-line>"
    # 1 /usr/include/stdc-predef.h" 1 3 4
    # 32 "<command-line>" 2
    # 1 "test.c"
    # 22 "test.c"
    void Array_Free(void *p) {
        free(p);
    }

    void *Array_Grow(void *base,size_t stride,size_t *length,size_t *capacity) {
        *capacity+=*capacity/2;
        *capacity=MAX(*capacity,MAX(MIN_CAPACITY,*length));
        return realloc(base,*capacity*stride);
    }

    void test(p,p_length,p_capacity, a,a_length,a_capacity)
    {
    }

    int main() {
        int myarray;size_t myarray_length;size_t myarray_capacity;
        int ourarray;size_t ourarray_length;size_t ourarray_capacity;
        test(myarray,myarray_length,myarray_capacity, ourarray,ourarray_length,ourarray_capacity);
    }

Looks like fairly reasonable code.

Edit: I would like to see it take a type in the Params and a __typeof__ while passing the args to make sure you know what is going where.

to3m5• 10 years ago

ARRAY_PARAM (as I assume you mean?) has no problem with two arrays. You just give them different names. Suppose you do this:

    void CopyIntArray(ARRAY_PARAMS(int,*dest),ARRAY_PARAMS(int,src))

Now you end up with this:

    void CopyIntArray(int **dest,size_t *dest_length,size_t *dest_capacity,
                      int *src,size_t src_length,size_t src_capacity);

And you can call it like this:

    ARRAY(int,xs);
    ARRAY(int,ys);
    CopyIntArray(ARRAY_ARG(&xs),ARRAY_ARG(ys))

Your point about token pasting with * p is a very good one, and I don't think that had occurred to me... but neither clang, gcc or VC++ seems to mind (and I used a number of different versions of each). I need to go and look up what the C standard has to say about this now.

I do note that I didn't use ARRAY_PARAM or ARRAY_ARG all that much in my code, though - but I don't remember whether this is because I found some problem with them in practice, or whether it just ended up that way.

(I'm on OS X right now and I just tried my code with clang. Probably-relevant compile flags were "-std=c1x -Wall -Wuninitialized -Winit-self -pedantic -Werror=implicit-function-declaration -Wsign-conversion -Wunused-result -Werror=incompatible-pointer-types -Werror=int-conversion -Werror=return-type -Wno-overlength-strings -Wunused-parameter".)

tom_mellior2• 10 years ago

#define ARRAY(T,S) T S;size_t S##_length;size_t S##_capacity

I don't understand why you don't wrap this in a struct, something like (not tested):

    #define MAKE_ARRAY_T(T) typedef struct array_##T { T data; size_t length; size_t capacity; } array_##T;

(This could be generalized for types that don't paste cleanly with ##, requiring the user to specify an extra type name.)

This would buy you several advantages:

- shallow copies of arrays using =

- easier parameter passing

- easier declarations due to real type names: array_int my_integer_array;

tines15• 10 years ago

This way you either have to declare every type you want to use this with at file scope (which is fine and some people do this, but it's a little irksome), or not be able to pass them as parameters to functions. Also it doesn't solve the problem of function genericity.

to3m5• 10 years ago

Shallow copies aren't important to me, and after years of using C++ templates and C# generics I've come to quite like having the type where I can see it!

As for why I didn't use this approach in general, a couple of reasons:

- I often have arrays of pointers. Now you need a second parameter, to give the struct its name...

- You need to decide in advance all the possible array types you're going to have, and keep the list up to date. I wanted this to feel a lot more like using std::vector

- You can't redeclare a struct, even with the same declaration. So if you have MAKE_ARRAY_T(int) in one header, because your object has an array of int, and MAKE_ARRAY_T(int) in another, because ditto, you can't include both headers from the same file. So again you need to be able to give the type a name

- Structs can't be mixed and matched as flexibly as variables. So say you've got MAKE_ARRAY_T(int,Module1Ints) in the header for module 1 and MAKE_ARRAY_T(int,Module2Ints) in the header for module 2 - both are arrays of ints, and you avoid the naming problems I described above. But now you can't use one in place of the other, even when this would make sense

It also doesn't help with passing your arrays into your generic array functions, since you don't have a single type that you can pass around. So you're restricted to passing in the 3 individiual pieces, or inlining snippest of code via macro, like mine does.

Something I did try in the past was using anonymous structs:

    #define ARRAY(T) struct { T *p; size_t len, cap; }

However, anonymous structs are always different, even if they're structurally equivalent, so... no go. (I also dimly remember Visual Studio not even being able to show you the struct in the debugger!) But I guess trying that out was probably a stepping stone on the way to my thinking of the code I've put here.

tines15• 10 years ago

I think the main drawback for every C implementation, including this one, is that you still have to write a new version of every algorithm for every type that you want to use your array struct with, unless you put all your functions in macros too. And even then, they'll only work with pointers, not with other data structures like the C++ algorithms will, unless you start doing dynamic dispatch which is what we want to avoid.

I think C++ solves this in a neater way (not saying it's good, just better) with templates, the iterator idea, and the algorithms library because you only write things once and the code is only generated for each type (not each use of the function like it would with macros).

1wd4• 10 years ago

Instead of putting it all in macros you could write the algorithms once in a "template include file" array_template_impl.h:

    #define CONCAT2(a, b) a##b
    #define CONCAT(a, b) CONCAT2(a, b)
    #define ARRAY CONCAT(array_,ARRAY_ELEMENT_TYPE)
    #define ARRAY_FUNC(name) CONCAT(CONCAT(array_,ARRAY_ELEMENT_TYPE), CONCAT(_,name))

    typedef struct {
        size_t size;
        size_t capacity;
        ARRAY_ELEMENT_TYPE *data;
    } ARRAY;

    ARRAY *ARRAY_FUNC(create)(size_t size) {
        ARRAY *p = malloc(sizeof(ARRAY));
        p->size = size;
        p->capacity = size;
        if(size) {
            p->data = malloc(size * sizeof(ARRAY_ELEMENT_TYPE));
        } else {
            p->data = NULL;
        }
        return p;
    }

    //...

    #undef ARRAY
    #undef ARRAY_FUNC
    #undef ARRAY_ELEMENT_TYPE

Then you can use them with the #include code generation trick like this:

    #include <stdlib.h>

    #define ARRAY_ELEMENT_TYPE int
    #include "array_template_impl.h"

    #define ARRAY_ELEMENT_TYPE float
    #include "array_template_impl.h"

    int main() {
        array_int *ai = array_int_create(0);
        array_float *af = array_float_create(0);

        for(int i = 0; i < 10; ++i) {
            array_int_push_back(ai, i);
            array_float_push_back(af, i * 0.3f);
        }

        array_int_free(ai);
        array_float_free(af);
        return 0;
    }

(In practice you might want even more indirection files: Put #define and #include in array_int.c. and array_float.c, and create also array_int.h, array_float.h and array_template_decl.h with just the usual declarations.)

phs2501• 10 years ago

I think it's cleaner to allocate the header information before the actual pointer (or, conversely, to return the pointer sizeof(array_header) into the allocation). Then it's trivial to pass around.

  struct vec_header_t {
      size_t length;
      size_t capacity;
  };

  static inline struct vec_header_t *vec_to_header(void *vec)
  {
      return ((struct vec_header_t *)vec) - 1;
  }

  #define _vec_length(vec) (vec_to_header(vec)->length)

  static inline void vec_free(void *vec)
  {
      if (vec)
          free(vec_to_header(vec));
  }

  #define vec_foreach(vec, iter) \
      for ((iter) = (vec); (iter) < ((vec) + vec_length(vec)); ++(iter))

It's slightly more cognitive overhead when, for example, debugging, but the vast improvement in usability (no special macros for normal/static declaration, trivial passing to functions, etc) is worth it IMHO.

to3m5• 10 years ago

Compared to the code in the linked post, I guess I'm a lot more strongly in favour of type safety, which this solution has too. But as a bear of very little brain, I really must insist on no extra cognitive overhead while debugging!

Sadly there's no really good way of doing this in C, so whatever you do there's a tradeoff somewhere. You just have to decide what type of crap you want to put up with, and code accordingly ;)

(If you're working on your own, I do say this is a fair argument for at least giving C a go when you might otherwise have gone with C++. If you can come up with some stuff that doesn't annoy you in any way you care about, and you don't mind the fact that C lacks a few of C++'s creature comforts, you'll reap the benefit of hilariously better build times.)

piker• 10 years ago

Is there a simple way to write the ARRAY_PUSH_BACK without a macro?

AlexeyBrin7• 10 years ago

Probably, if you use memcpy and store the size of the data type as an extra parameter in the containing struct.

inlined3• 10 years ago

I was thinking about that but I don't know what to do with the type of the param you're accepting. Could you do a const void* ref? Might just be easier to make it variadic.

inlined3• 10 years ago

If you have a pointer-only array you could just make it based on void*. Primitives and by-value arrays make it a lot harder.

krylon5• 10 years ago

I wrote pretty much this exact implementation of a dynamic array once. For several data types.

And I had that same idea, let's use macro to fake generic programming. But while I admire the trickery some people pull off using the C preprocessor, I admire them from afar. My coworkers would not have let me get away with that, anyway.

I am not a C++ programmer, but templates are immensely powerful, and after learning about them (a little, at least), I found statically typed languages without some form of type-generic programming to be very bothersome.

Looking at C++ as "C with Templates" instead of "C with Classes" gives a very different picture (plus, Classes and such are still around in case they are needed, anyway). Every other year or so, I try to get my C++ up to usable standards, but I do not need it for work (except for that one time about three years ago), so I eventually lose interest. Maybe approaching C++ as "C with Templates" is a more promising route.

tines15• 10 years ago

Maybe approaching C++ as "C with Templates" is a more promising route.

Genius. I'm doing this from now on.

akkartik• 10 years ago

For many years now I treat C++ as "C with destructors and the STL". Examples:

1. RAII: https://github.com/akkartik/mu/blob/61fb1da0b6/010vm.cc#L484

2. STL: https://github.com/akkartik/mu/blob/61fb1da0b6/020run.cc#L50

I really don't use anything else.

ensiferum2• 10 years ago

The author could have just used glib.

krylon5• 10 years ago

Also, if one is not restricted because of license conditions, the Judy Array comes to mind: https://en.wikipedia.org/wiki/Judy_array

The API is very easy, and it's really fast.

samfisher83• 10 years ago

You could add some function pointers to the struct initialize them and then you could do:

Array a; a.add(&a, item).

faragon• 10 years ago

I wrote a similar thing for C99 [1], but "safe" (bound-checked), having both stack and heap allocation, and many other array/vector functions [2], including integer-optimized sort (in-place MSD binary radix sort -wich is availabe in typical C++ sort implementations, but not in C, as default qsort() relies on sorting functions-). With some benchmarks, too [3]

[1] https://github.com/faragon/libsrt

[2] https://faragon.github.io/svector.h.html

[3] https://github.com/faragon/libsrt/blob/master/doc/benchmarks...

wollstonecraft• 10 years ago

https://github.com/attractivechaos/klib/blob/master/kvec.h

halayli• 10 years ago

for cases where malloc checks complicate the example it doesn't hurt to use assert instead.

antirez3• 10 years ago

AFAIK when the array is created, p->size should be set to 0, not to the size argument.

AlexeyBrin7• 10 years ago

This mimics C++ vector, e.g.:

    vector<int> vec(5);
    vec.push_back(11);
    vec.push_back(12);

Now you have in vec:

    0, 0, 0, 0, 0, 11, 12

But your suggestion is better from an API point of view.

antirez3• 10 years ago

Oh... thanks! I was not aware.

antirez3• 10 years ago

PS please note that there is no memset nor any other mean to zero initialize the elements. So the code appears to have a bug anyway.

crossroads1112• 10 years ago

I wrote something similar in C99 as well for another project. Initially, I used the same form used in this blog post however it's easy to see that the ergonomics for accessing the data are pretty terrible.

I eventually moved to a solution where I prepended the capacity and size to the block returned to the caller and then wrote helper functions that accessed/modified these values. This way the caller can access values in the returned array just as they would one returned from malloc.

The code (note, the `vec` type is just a typedef'd `void*`): https://github.com/crossroads1112/marcel/blob/master/src/ds/...

WalterBright4• 10 years ago

A possible approach is to use a macro

When macros start being used for metaprogramming in C, it's time to reconsider using C++.

wott• 10 years ago

When it's time to reconsider using C++, it's time to consider using something else :-)

Ace17• 10 years ago

Like the D programming language? :-)

inlined3• 10 years ago

Why does array_push_back need three parameters? Couldn't the macro just use size_of on the second param?

AlexeyBrin7• 10 years ago

Not without some serious modifications, see line 6 of the macro:

    data_type *pp = arr->data;\

this is expanded to something like (when data_type is double):

    double *pp = arr->data;

You can get rid of the third parameter. Just store the size of the data type in the container struct and use memcpy. Something like this (probably slower than the original):

    char *pp = arr->data;\
    memcpy(pp + (size - 1) * arr->size_of_data, &(x), arr->size_of_data);\

kev009• 10 years ago

I would recommend David R. Hanson's "C Interfaces and Implementations: Techniques for Creating Reusable Software (Addison-Wesley Professional Computing Series, 1997, ISBN 0-201-49841-3).

https://github.com/kev009/cii/blob/master/src/array.c - this leaves resizing on the caller, but that could be retrofitted in. Most importantly is how the book explains everything.

knorker• 10 years ago

Ugh. Multi-line macro.

how about #define PUSH_BACK(a,x,t) push_back(a,&x,sizeof(t))

No multi-evaluation problems or other madness.

Edit: Actually that won't work for expressions. So

#define PUSH_BACK(a,x,t) do { t tmp = x; push_back(a,&tmp,sizeof t) } while(0)

slightly better.

C99/C11 dynamic array that mimics C++'s std::vector

Related Stories