I'm writing my linked lists class. Its nodes point to actual element that was allocated outside the class. And i'd like to be able to deallocate both nodes and elements from inside the class.

What i have to do with it?
delete node->data; or delete[] (BYTE*) node->data;

I got Dev-C warning when delete void* directly! by deleting node->data. So I'm not sure I can do that.
[Warning] deleting `void*' is undefined

But casting to (BYTE*) and do delete[] stop compiler to complain anymore.

Does delete operator know the size of allocated memery point by void*? Below is a small part of my code.

I think yes.

But if you're writing this for anything other than academic purposes, I suggest you switch to STL.

Why to switch to STL? I know there are namespaces just for this, but if you write class on your own, you know how it works and you can easily modify it to whatever you want. For example I included linked list to object classes in my project. I cannot imagine what junk I'd have in my code when using STL. But anyway I'm not saying it's wrong. Whether to use it or not depends on circumstances. But one note - STL makes your programs a bit overweight.

Then why do you use Allegro? Why don't you write your own code for loading bitmaps, blitting them, playing samples, setting gfx mode, getting mouse and keyboard input, etc? If you did, you would know exactly how it worked.

Let me tell you why. Because someone already wrote that for you and it works. It has been tried and tested many times and there's no reason to reinvent the wheel.

I'm using Dev-C++. I still remember that using STL with MinGW results in a very large exe-file. So I avoid it if I don't use much of it.

I've ever used VC++ before and it doesn't have this STL issue.

Ok Miran you're right, but I'm talking about basic data structure. First it's good to know how it works, second it's better to write your own which will be suit you, third STL produces very large exe files. But again I'm not saying STL s wrong. But when you need simple linked list, then I don't see any need to include STL.

Proof? In my experience STL code is always highly efficient, except perhaps when you talk about speed of compilation. Maybe the exe gets so large because you use many different vector types, and forgot to strip symbols?

I have done some experiments on basic hello world code. It is an iostream part of STL that causes big exe files.

hello world                             19 KB
+ my owned linked list                  54 KB
+ std::iostream                        572 KB
+ std::list                             56 KB
+ std::vector                           61 KB

Well, I still need your advice on deleting void pointer. Dev C++ warning make me unsure that deleting void* will free allocated memory properly.

Going back to the original question:

Firstly, I don't think you can call delete on a void *. Delete needs to know the size of the allocated structure - in fact (at least with MS, anyway), if you step with the debugger inside of new/delete, you'll see that internally it uses malloc/free.

I think your code though is highly perilous ground - the point of C++ is to avoid pointer casting & void types and the inherent danger of the lack of type safety found in procedural C. I think what you're probably looking for is this: try making your linked list class a template class. In fact, this is exactly what STL does for its container classes.

Could you share the code, please? I did a simple hello world test myself and with simple std::iostream and std::list file size was ~25k, 5k when stripped, 4.5k when UPX'ed. Perhaps my test was too simple though.

Also, this was done under Linux with GCC 3.4.4. In theory I think there shouldn't be major difference between OS'es because the compiler is the same.

Though I noticed that with custom list you saved a whole two kB's
Is that enough to justify creating your own classes that you have trouble with? With STL list you wouldn't even have to make topics like this one.

As for deleting void*, I don't know. I haven't used them in my C++ projects because I haven't seen the need

With iostream included, my hello world grows to 465KB when compiled without debugging info. (Dev C++ v4.9.9.2 and MinGW32 v3.4.2)

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    printf("Hello World\n");
    return 0;
}

I just try to write my own class for fun. And if it turns to be simpler and smaller than STL I will use it in my game instead. Maybe iostream link size scared me out.

Bare main()                        -> 6KB
std::list with all function called -> 27 KB

Difference                         -> 21 KB

Delete should knows size (since in most cases it uses delete which takes void * anyway) but since type is unknown it doesn't know which destructor to call. Remember, object's destructor must be called when object is destroyed.

Why do you want a void*? Just use a char*, it works the same, as each char is 1 byte, and you can allocate + free it with no problems.

With that code you gave I got this:

#g++ linklist.cpp ; ls -l a.out
-rwxr-xr-x  1 hoho users 8187 Dec 27 14:16 a.out

#cp a.out a1.out
#upx -9 a1.out
#ls -l a1.out
-rwxr-xr-x  1 hoho users 4830 Dec 27 14:17 a1.out

#cp a.out a2.out
#strip a2.out
#ls -l a2.out
-rwxr-xr-x  1 hoho users 4420 Dec 27 14:17 a2.out

Perhaps mingw really does create bigger executeables under windows.

With a STL list test I got this result:

#g++ linklist.cpp; ls -l a.out
-rwxr-xr-x  1 hoho users 19057 Dec 27 14:24 a.out

#cp a.out a1.out ; upx -9 a1.out ; ls -l a1.out
-rwxr-xr-x  1 hoho users 8575 Dec 27 14:25 a1.out

#cp a.out a2.out ; strip a2.out ; ls -l a2.out
-rwxr-xr-x  1 hoho users 11060 Dec 27 14:25 a2.out

#upx -9 a2.out
ls -l a2.out
-rwxr-xr-x  1 hoho users 6084 Dec 27 14:25 a2.out

Not too bad. I guess the size difference might come from if programs under Linux are dynamically linked to libstdc++. You might want to try what UPX and strip can do for the executeables under Windows. I wouldn't be surprised if the 465kB gets reduced to <50kiB

There is nothing bad about writing your own classes but you might want to write them similar to STL by using templates so you wouldn't have such problems with void pointers.

Why are you trying to delete a void*? You can't new a void*.

This indicates a design error. You should be deleting the object in the same context as you're creating it. Otherwise memory leaks will be the least of your problems.

No, it does not need to know the size. The OS does, or the underlying allocation system, but delete does not.
The problem here is that delete wants to call a deconstructor for the data, and void does not have a deconstructor.

What is this data? How do you allocate it? What is it used for?

Quote:
Firstly, I don't think you can call delete on a void *. Delete needs to know the size of the allocated structure

Sorry - poor wording on my part. I think we're getting at the same thing - when you delete an object, internally, delete derives the size of the allocation that's being freed since it knows the struct size of the class that's being deleted. But it still calls free() with a given byte size. And as William points out, void is not a type, so you can't call its destructor.

Which brings me back to the problem: one shouldn't use a void pointer type in the first place. It's a skanky way to short-circuit a problem, and fraught with potential gotchas. Seriously: look at template classes. This is exactly what they're for:

Apologies in advance for the sparse example - I haven't run the compiler on this, so my syntax might be off somewhere, but you get the idea. The point is that you simply call delete on the node object now, since the compiler knows what T is when you instantiate the class - you're solid.

Thanks everybody.

Now I understand the concept of type safety and template. I think I'm going to read my old C++ book about data structure and algorithm again.

There are some good uses to void*. In my linked list class, I use void* to whatever data is to be stored in the list. You just have to cast it whenever you want to read/use the data.

However, deleting a void* is a no-no in my books. I like to think of the void* as if pointing to something with my finger. I wouldn't want to delete my finger (ouch), I want to delete the something that it is pointing at.

I never used void* since it didn't sound like something I would need, which also means I don't have any experience with it, but my programmer-sense says; if you create something whose size you will need later, then calc&store its size while you are creating it.

Typically, what happens is that C++ stores the exact size of the allocated memory block one word "before" the allocated memory block. For example:

complex* c = new complex(1.0, -1.0); // say complex is a struct with two 4-byte floats
// address  0xF0    0xF1    0xF2
// value    2       1.0f    -1.0f
// c == 0xF1
// size of allocated memory block (2 words) stored at 0xF0

char* str = new char[16];
strcpy(str, "Hello world!!!");
// address  0xF3    0xF4    0xF5    0xF6    0xF7
// value    4       Hell    o wo    rld!    !!\0[?]
// str == 0xF4
// size of allocated memory block (4 words) stored at 0xF3

Then when delete is called, it looks one memory space to the "left" of the allocated block to know how much to delete. This is how delete knows how much memory to free when given an array, even though you don't have to write delete[16] str;for example.

Thus, requiring the type pointed to by a void* pointer is a matter of type safety re: which destructor to call, and has nothing to do with how much memory is actually being deleted.

That's not a good use for void*. That's where you should use templates to make the code type safe.

And by the way, I bet no one can outperform STL in effiency, type safety and elegancy so why to invent the wheel over and over?

It's worked for me so far. Maybe I'm thinking of template in more of a general definition and you have a more technical explanation. Care to share an example of what you mean?

I don't doubt it. A lot of people tell me I'm "reinventing the wheel," but of course I am. I know there's a lot of things out there (like map editors, graphics libraries, etc.). It's not that I'm trying to make a better one or "reinvent" it, but rather understand it and learn from it.

You're assuming that the linked list contains only objects of a specific type. But it doesn't have to (the compiler doesn't force type safety) and if one of the elements isn't of a desired type, you'll likely get a crash (or undefined behavior at best).

Also what if you want to store ints, for example? You'd need one pointer dereference every time a value is accessed while that's not the case if you'd use a template.

What object can void* not point to?

And what's so bad about dereferencing? Also, void* and the next* is not all I store inside the linked list. I also store an int (ikey) for sorting purposes (or if you are simply storing ints) as well as a char* (ckey) if you need a char for some reason. Of course, this makes each node larger in size, but I don't think it's enough to make anything suffer.

It is.
That is to say, in C. In C++, one should (almost?) never need to use void pointers. If there's a situation where they seem nescessary it's probably a sign that you need to rethink your design.

That's my point indeed. When you need to access the data you need to know the real type of the objects. But you can't know it for sure because the type information is lost.

It's slower than a direct access.

Or you could store an object which contains all that data and a pointer to the real object or to store objects which inherit from the same virtual base class.

But the question was (indirectly) if there's any good use for void pointers in C++.

I wrote the linked list structure back in my C-hayday of early college years. When I gradually moved into C++, I just kept using it because it was easy to use. I guess I should rethink how to do it then...hmmmm...

Compared to not dereferencing it is dead slow and takes more memory.

When extreme performance is needed then there is a difference. On the other hand, if extreme performance is needed it is usually best to stay away from lists

[edit]

As I assume you already know how to code a linked list you might want to swich over to STL list. With that you automatically get all sorts of nifty things from <algorithm> header too. A slight speed improvement is also quite probable

I see. Well, I just got use to my class because it worked so well and I didn't really know I was losing that much performance. Of course, I never had a very big list so it's not like I'd notice a performance flaw anyway. My original concept of making the linked list structure was "store something in a generic list" (some_list->data = something) and "read information from the list" (dereference). Out of the few years I've been using it, I've never accidentally casted it to the wrong type when I dereferenced it. Of course, this is all old news now and I'm going to research STL and I guess, put my list to rest.

Done and done. I'm gonna tinker around with this when I get a chance. Is this a good site to start from?

Seems to be. Though I usually just use whatever is first result from Google

It was.

googling for "c++ iostream" or "stl vector" come up with totally different sites. I usually just google for specific stuff and use several different sites for reference

try "stl list"