▲ 84 points
back
158 comments
> 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.
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.
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.
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.
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.
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.
It's always just one or two more features and before you know it - C++
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.
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.
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.
> 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 :).
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.
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.
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.
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++.
I want something like std::vector, but I don't want exceptions. How does C++ help in this case?
>This is a situation where C++ really shines
I agree but passing in the size is really not much of a deterrent.
More like the clusterfuck that the language is than the community.
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.
> Maybe approaching C++ as "C with Templates" is a more promising route.
Genius. I'm doing this from now on.
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.
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?
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.
> A possible approach is to use a macro
When macros start being used for metaprogramming in C, it's time to reconsider using C++.
When it's time to reconsider using C++, it's time to consider using something else :-)
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...
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.
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.
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.
The author could have just used glib.
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/...
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.
With the use of defer http://pastebin.com/EXZuRAdT you could create it w/o the need to use array_free.
AFAIK when the array is created, p->size should be set to 0, not to the size argument.
This mimics C++ vector, e.g.:
vector<int> vec(5);
vec.push_back(11);
vec.push_back(12);
0, 0, 0, 0, 0, 11, 12
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.
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
ARRAY(int,xs);
#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)
ARRAY(int,xs);
ARRAY_INIT(xs);
for(int i=0;i<100;++i)
ARRAY_ADD(xs,i);
ARRAY_DESTROY(xs);
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);
}
for(size_t i=0;i<xs_length;++i) {
printf("%d\n",xs[i]);
}
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
void FunctionThatTakesAnArray(ARRAY_PARAMS(T,*p));
ARRAY(T,myarray);
FunctionThatTakesAnArray(ARRAY_ARG(&myarray));
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.)
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.
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).
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))
> #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 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;
Why does array_push_back need three parameters? Couldn't the macro just use size_of on the second param?
Not without some serious modifications, see line 6 of the macro:
data_type *pp = arr->data;\
double *pp = arr->data;
char *pp = arr->data;\
memcpy(pp + (size - 1) * arr->size_of_data, &(x), arr->size_of_data);\You could add some function pointers to the struct initialize them and then you could do:
Array a; a.add(&a, item).
Is there a simple way to write the ARRAY_PUSH_BACK without a macro?
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.
Probably, if you use memcpy and store the size of the data type as an extra parameter in the containing struct.
for cases where malloc checks complicate the example it doesn't hurt to use assert instead.