Proggraming question

[Tim Stirling]

I know this is isn't an opengl question but I know most good programmers here can tell me what to do( no pun intended).

If I have an array of say vertices, the size of which is different everytime a file is loaded ( yes I am loading a file). I set the array with new. i.e scenevertices = new VERTEX[numvertices];. Where VERTEX is a structure of type vertex (i.e vertex.x, .y ,.z). This is fine but what I want to do is sometime in the program add vertices. I can't use new again and set numvertices to the new number as this will wipe out the previous data. I want to append on to the end. I think this is done with linked lists but I can't find any help on the matter and it is nothing I have done before and so I don't have a clue what to do.
I am sure this isn't a big question, simply how do I add a member to list making a dynamic list. At the moment I simply make the array huge to start with but this is obviously stupid and a waste of mem.

Yes, linked lists is a way to do it, or you can just create a new array with the new size, copy all the stuff from old array into new array, and so on.

Then for every vertice you want to add, just hook it on. If you want to remove vertices, then use a double linked list, which keeps track of everything before and after the link. There are many examples of linked lists on the net, use google, you will find LOTS of hits.

[Tim Stirling]

Thanks, one question: with a double linked list is it possible to remove items from the middle of the list? Double linked lists seem to be quite complex and are usualy put into a big fancy class?, oh well.

[imported_Rob]

You might want to take a look at the STL (Standard Template Library). In case you're not familiar with it, the STL is a bunch of container template classes for lists, sets, vectors, stacks, etc.

I have heard some people complain about the speed of the STL, but in my experience, if used correctly, it is plenty fast.

There are a lot of new concepts to get your head around and so the learning curve can be a little steep at first, but I highly recommend taking the time to learn STL. It is *extremely* useful for a very wide range of programming tasks.

And the STL is now a part of the C++ standard, so you don't need any special libraries, nor do you compromise compatibility by using it.

[This message has been edited by Rob (edited 03-13-2001).]

[zed]

yes its possible to remove objects from the middle of a list
theyre not complicated my code for addition removal of a linked list item is about 10lines, i can post it if u want

[Deiussum]

This is probably a bit off-topic, but has anyone ever found a use for the placement new operator that is in the most recent ANSI standards? If you're not familiar with it, you basically use it to set the address that the memory is allocated at. I was thinking that maybe this could be used for resizing arrays, thought I can see some potentially serious issues with this. I don't even recall the exact syntax for it offhand and I don't have my ANSI standards book handy. It's one of those rarely used features that not many people know about.

There's also a nothrow new operator. According to the latest standards, if you try to use new and there isn't enough memory, an exception should be thrown rather than returning NULL, as was originally the case. The nothrow operator will cause new to return NULL instead of throwing an exception.

Anyway, it's some interesting, little-known C++ trivia.



[This message has been edited by Deiussum (edited 03-13-2001).]

[EricK]

I am a big fan of STL so I would recommend using the list or vector class from it.

However, a linked list is not too complicated. If you call your structure (or class) VERTEX then add to it's definition a pointer to a VERTEX and call it next. This is the "link" in linked list.
struct VERTEX{
GLfloat x,y,z;
struct VERTEX *next;
};

You also need a pointer to the first VERTEX and a pointer to the last VERTEX. That is all you need to define to create a linked list. The remaining work is just bookkeeping to make sure the next pointer points to the next VERTEX in the list.

When you add to the linked list create a new VERTEX, point the next pointer of the last VERTEX at the new VERTEX and then change the last pointer to point to the new VERTEX as well.

For a double link list just add a VERTEX *previous pointer to the VERTEX struct. This allows you to traverse the list forwards and backwards but it does not allow you to remove an item from the middle of the list. That is, you can remove an item from the middle of a single linked list as easy as a double linked list. You just need to keep a pointer to the previous item. When you remove a VERTEX structure from the list then repoint the previous VERTEX next to point at the next VERTEX then delete the element.

Linked lists are really not hard to figure out.

[Tim Stirling]

Thanks for your replies. I have found a very good and easy example, and I must say it does now sound simple. The complicated code I saw was becuase it was all put into classes and a load of fancy extras put in. Now I just need to implement, I don't actualy have a list of vertices ( this was to simplify the questions and answers). I am actualy making a level editor and so lists to polys are needed but I can and want to figure it out myself now.

[This message has been edited by Tim Stirling (edited 03-14-2001).]