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.
| 1 | class Linked_Lists |
| 2 | { |
| 3 | public: |
| 4 | Linked_Lists(); |
| 5 | ~Linked_Lists(); |
| 6 | bool add(void *data); |
| 7 | bool remove_tail(); |
| 8 | bool first(); |
| 9 | bool last(); |
| 10 | bool next(); |
| 11 | bool prev(); |
| 12 | void* get_data(); |
| 13 | bool is_empty(); |
| 14 | int get_count(); |
| 15 | |
| 16 | protected: |
| 17 | struct Node |
| 18 | { |
| 19 | void *data; |
| 20 | Node *prev_node; |
| 21 | Node *next_node; |
| 22 | }; |
| 23 | Node *head; |
| 24 | Node *tail; |
| 25 | Node *current; |
| 26 | int count; |
| 27 | }; |
| 28 | |
| 29 | Linked_Lists::~Linked_Lists() |
| 30 | { |
| 31 | Node *node; |
| 32 | |
| 33 | if (head == NULL) return; |
| 34 | |
| 35 | first(); |
| 36 | do |
| 37 | { |
| 38 | node = current; |
| 39 | next(); |
| 40 | delete[] (BYTE*) node->data; |
| 41 | delete node; |
| 42 | } while (current != NULL); |
| 43 | } |
Does delete operator know the size of allocated memery point by void*?
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.
But if you're writing this for anything other than academic purposes, I suggest you switch to STL.
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.
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.
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?
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.
I have done some experiments on basic hello world code. It is an iostream part of STL that causes big exe files.
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
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.
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 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.
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:
| 1 | #include <list> |
| 2 | #include <iostream> |
| 3 | using namespace std; |
| 4 | |
| 5 | int main (){ |
| 6 | |
| 7 | list <int> l; |
| 8 | l.size(); |
| 9 | l.empty(); |
| 10 | l.push_back(1); |
| 11 | l.push_front(1); |
| 12 | l.front(); |
| 13 | l.back(); |
| 14 | l.begin(); |
| 15 | l.end(); |
| 16 | l.insert(0,1); |
| 17 | l.clear(); |
| 18 | l.push_back(1); |
| 19 | l.push_front(1); |
| 20 | l.pop_front(); |
| 21 | l.pop_back(); |
| 22 | l.remove(1); |
| 23 | l.sort(); |
| 24 | l.reverse(); |
| 25 | cout<<"Done"<<endl; |
| 26 | return 0; |
| 27 | } |
#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
I just try to write my own class for fun.
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*.
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.
Firstly, I don't think you can call delete on a void *. Delete needs to know the size of the allocated structure
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
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.
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:
| 1 | |
| 2 | template <class T> |
| 3 | class MyNode |
| 4 | { |
| 5 | public: |
| 6 | T* data; |
| 7 | MyNode<T>* prev_node; |
| 8 | MyNode<T>* next_node; |
| 9 | }; |
| 10 | |
| 11 | template <class T> |
| 12 | class MyLinkedList |
| 13 | { |
| 14 | public: |
| 15 | |
| 16 | //skipping over the bulk of it |
| 17 | |
| 18 | ~MyLinkedList_Lists() |
| 19 | { |
| 20 | MyNode<T> *node; |
| 21 | |
| 22 | if (head == NULL) return; |
| 23 | |
| 24 | first(); |
| 25 | do |
| 26 | { |
| 27 | node = current; |
| 28 | next(); |
| 29 | delete node; |
| 30 | } while (current != NULL); |
| 31 | }; |
| 32 | |
| 33 | private: |
| 34 | MyNode<T>* head; |
| 35 | MyNode<T>* tail; |
| 36 | MyNode<T>* current; |
| 37 | int count; |
| 38 | |
| 39 | } |
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.
Firstly, I don't think you can call delete on a void *. Delete needs to know the size of the allocated structure
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.
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.
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?
That's not a good use for void*. That's where you should use templates to make the code type safe.
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?
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?
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.
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?
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.
You're assuming that the linked list contains only objects of a specific type.
What object can void* not point to?
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.
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.
That's not a good use for void*
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.
What object can void* not point to?
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.
And what's so bad about dereferencing?
It's slower than a direct access.
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.
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.
It is.
That is to say, in C.
But the question was (indirectly) if there's any good use for void pointers in C++.
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.
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...
And what's so bad about dereferencing?
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]
I guess I should rethink how to do it then...hmmmm...
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
That's my point indeed.
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.
As I assume you already know how to code a linked list you might want to swich over to STL list.
Done and done. I'm gonna tinker around with this when I get a chance. Is this a good site to start from?
Is this a good site [msoe.edu] to start from?
Seems to be. Though I usually just use whatever is first result from Google
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"