Thread: Explorations in Structs and sorting.

Originally Posted by jimtuv

However my personality tends to drift toward taking risks so I am inclined to try out things that I probably shouldn't. And the idea of using the stack is tempting.

The stack has a few natural limitations you should be aware of (and will become, one way or another):

1) You can't return a stack variable from a function, because the function's stack is eliminated when it completes -- as you note, it's return value is left around, but in the case of an array such a char string, that value is a pointer, but what it points to will be gone:

Code:

char * somefunc() {
       char array[32];  // stack variable
       return array;  
}

No good (your compiler will probably tell you that)! So in this case you must malloc:

Code:

char * somefunc() {
       char *array = malloc(32);  // heap variable
       return array;  
}

This returns a pointer into the heap, which is valid until explicitly freed().


2) The stack has a fixed maximum size set by the operating size, and it is comparatively small. Remember, local variables in main() are part of this. So if you have an array whose size is determined at runtime (not hardcoded) never put it on the stack (this is only possible with C99 anyway and pretty limited). You could play around and see at what point your program blows up because the stack is done, but of course, by doing that you limit the program -- if you want to use it on larger data sets later, you have to recode.

3) If the array size determined at runtime is not taken from command line arguments, you have to malloc it anyway. Syntax makes anything else impossible.


So while Elysia's point has some truth in it, in practice it is almost never of concern. Of course, you do not malloc everything. But for your primary data structures (such as the record array), the best practice is to do so. The fact that using stack memory is "faster" than allocating is completely mitigated by the fact that it is not big, whereas you can use all your RAM with the heap. This means in cases where the stack is an option, you are dealing with such a small amount of data that to malloc it would only require microscopic amounts of time -- not anything a normal person would consider at all relevant. The stack won't scale! The heap does.

Keep in mind that when using malloc, you introduce memory allocation bugs. You must free what you allocate. Making sure you always free the memory under all conditions can be tricky. That is another reason to avoid malloc if you can.
But now you know the advantages vs disadvantages, so it's up to you to choose what you need.

Originally Posted by jimtuv

The problem would be if the node to delete were at the beginning removing the node isn't the problem because the following node already has the pointer pointing to the correct node. It's the Head or list pointer that would have to be fixed as it would need to point to the second node not the first.

seems like you could do this recursively. By setting up the deletion function to return the pointer of the node. Just a thought maybe I am way off.

This is where pointers get slightly complicated. I'm not sure what you mean by "do this recursively", but with the delete you have two choices and you seem to have the first one:

1) Always return the head node in case it has changed (because the head was deleted). Here assume the node is identified using a char string, "val":

Code:

node *delete(node *head, char *val);  // function prototype
/* usage */
head = delete(head, "this one");

2) The other option is to pass in the address of the pointer which points to head:

Code:

void delete(node **head, char *val);  // function prototype
/* usage */
delete(&head, "this one");

This is called a "pointer to a pointer" and that's another important concept . It allows you to reassign head without using the return value -- so the return value could be reserved for something else, say an error code. Beyond that it's just a matter of style, but you should know how to do both for cases when you cannot use the return value in this way.

Originally Posted by Elysia

Keep in mind that when using malloc, you introduce memory allocation bugs.

Memory bugs are usually of this form:

Code:

char *ptr;
while (some loop) {
      ptr = malloc(123);
      [do something with pointer]
}

Since ptr was not freed or assigned to anything else in the loop, the memory to which it pointed (different memory for each iteration!) is still reserved for the duration of the program, but you now have no handle (pointer) to that memory, meaning you cannnot access or use it, or free it. This is called a memory leak.

So in general "memory bugs" are pretty simple and easy to prevent. The only thing which makes them more potentially troublesome than something which causes a crash or bad output is that you can fail to notice them. However, use of a simple memory profiler such as valgrind (on linux) can solve that problem.

That'd work. You see how this will get very expensive on a big array. Which is why if you need to do deletions, a linked list is usually a better choice. They are a pretty basic and essential data structure, once you understand them it is not hard to whip an implementation up in a few dozen lines.

C generally forces you to "hand-roll" any kind of data structure beyond an array (such as a linked list, which most other modern languages have a built in "list" type). There's an obvious disadvantage to this low level focus (it's work) -- the advantage would be that such things are almost always, by nature, more efficient than using generisized equivalents (like built-ins), esp. in terms of memory usage.

I'm curious. Give a reason why a hand-rolled out linked list would generally be more efficient in terms of memory than a generic built-in structure?

Fewer pointers, less indirection, is an educated guess, but in any case "the proof is in the pudding" -- you don't think the afforementioned mem use issue WRT to the STL is for no reason at all, do you?

I'm not saying that makes built-ins for dummies, since they do save a lot of time, and certainly I make a lot of use of that kind of thing in a number of languages on a daily basis. But when push comes to shove, if (eg) std::map uses 40% more memory than a customized hash table or tree, then the amount of data that can be handled given some upper limit (eg, 2Gb) is 40% greater for the custom structure.

In any case, you have tweak control of a hand-rolled structure, which pretty much by definition means there is more opportunity for optimization.

What I am implying is that if you add more complexity to your program, it will cause more bugs and get harder to maintain. This holds true for anything, not just malloc/free. The advice was that you shouldn't complicate the program unnecessarily. Don't use malloc/free unless you have to. Don't use scanf unless you have to.

Believe me, when you start making bigger programs, you will begin to see the problem. Lots of if conditions, lots of places that hold references to the same data (where should it be freed?). Excellent ways to cause memory leaks.

Originally Posted by jimtuv

I think that because C doesn't hand hold the programmer makes it potentially unsafe yet also extremely fast and powerful at the same time. This is some of what makes C so interesting to me.

Then you should try C++, because it's even more powerful in a sense while it still holds true to its roots from C.

I use the word potentially because with proper knowledge and careful application of that knowledge C should be and has proven to be very safe indeed.

I don't know if C has been proven to be safe. But you are right that if used properly, then it will indeed be safe.

Originally Posted by whiteflags

You're being a huge troll. You're lucky I'm not a mod.

Nonsense. I am stating, as I have been from the beginning, that putting malloc/free into your program instead of using the stack, will cause additional bugs.
I have nowhere said that the OP should not do it. In fact, this whole damn discussion began with the OP asking if pointers had to be used with malloc/free, and I answered, no, it doesn't have to be. It can be on the stack, if you want. It can also be malloc/free.
I repeat:
The OP is free to do whatever he wants, if what way he wants. I have merely stated some facts. This should not deter the OP from experimenting and learning things. This is mostly "useful information" that a programmer writing a real world application should worry about and not a student who is still learning the language.

That's a stupid statement. That's like saying "adding scanf to your program will cause bugs". No it doesn't. You not using it right causes "bugs". Hell, I could just as well say "using arrays causes bugs", or "using the stack causes bugs" (because I can blow the stack).


Quzah.