🔒 Locked

Adding to a "newed" pointer

Started by RaptorZero Jul 14, 2004 at 8:00 AM 23 replies 3.8k views

Original Post

Jul 14, 2004 at 8:00 AM

Hey there, this post has something to do with game programming but I think it's more general programming so here it is: I'm programming a game and in it: I have a class defined somewhere: class CEntity { ... }; I have a pointer of its type somewhere else: CEntity *pEntIndex; I "new" this pointer to an array of 5 CEntity's: pEntIndex = new CEntity[5]; Then, in the middle of the game I want to "extend" this array as if I had "newed" it as a 6 element array (I think that's not possible). How can I get arround that problem, does anyone knows? I've heard of something like linked lists, is that a good idea? That's all, thanks in advance for your help!

rypyr

Jul 14, 2004 at 8:03 AM

It's not possible with a standard C++ array (unfortunately).

What you can do is :

1) create a new array of 6 entities and copy the first 5 of the old array over to this new array, then add a 6th entity

or

2) use a container of some kind that has extensible properties. An example of this is a list (better for adds/inserts) or a vector (better for random access):

std::list<CEntity*> AllEntities;AllEntities.push_back(new CEntity); // AllEntities now contains 1 entityAllEntities.push_back(new CEntity); // AllEntities now contains 2 entityAllEntities.push_back(new CEntity); // AllEntities now contains 3 entity

Regards,
Jeff

gryfang

Jul 14, 2004 at 8:12 AM

If the array itself is public (or you have the appropriate methods to control it) you can extend an array by basically making a bigger arry and filling it with the original's values and then writing over the original's scope (I don't know if it's possible in C++, but it is in JAVA TMK), but I have never liked this approach. Another was you can handle this is to have a Linked List, or vector instead of just and array. For the linked list you can do a good amount of work ahead of time to make it act like an array (including indexes and all) so you basically have a memory hog array that's redily expandable, but that can be to much work. Another approach is to do a queue and use a recursive method (or looped one) in order to treat it like an array (count the number of times you dequeue into a temp queue).
One last approach is to make a new class and inherit from queue (or stack) and array and try to polymorph into a good clas... I REALLY THIS THIS IS A BAD IDEA.
I hope my ramblings helped, if not tell me what you are wanting to try.

RaptorZero

Author

RaptorZero

Jul 14, 2004 at 8:19 AM

Rypyr, I think your first metod is kind of ... IMPOSSIBLE :)
The 5 elements array was just an example, I think that if I copy a 200 element array holding 50Mb of data in the middle of the game, the player will notice a slight fps drop like to 1 frame each 10seconds :)

As for the second metod I didn't understand quite well. What is "std::list"? Could you explain it better?

I was thinking of creating a stucture like:
struct EntNode
{
CEntity Entity;
EntNode *pNextNode;
};

so that everytime I want to add a CEntity I search for the last node and "new" the pNextNode pointer. Will that work (and will that be fast)?

Thanks for your help...

RaptorZero

Author

RaptorZero

Jul 14, 2004 at 8:29 AM

Gryfang, despite not knowing whats a "recursive method" or a "polymorphic class" (sorry I'm not an expert programming, I started like at the begining of this year, I'll google thoose things :)) I could get a picture of what you said.

All I want is a dynamic place to hold all the entities in my game so that I can add or delete them whenever I want. Like if a glass breaks I want to be able to create entities to hold its pieces and delete them when their lifetime runs out, without having to copy the other entities (the player, the enemies, the doors, ...). I don't need anything complex like "recursive polymorphic arrays of list pointers".

Thanks anyway!

--
-- Ohh time to go to school, I'll be back later
--

nyStagmus

Jul 14, 2004 at 8:35 AM

Like rypyr wrote in his example: Use std::list You can find more info on its member functions on msdn. It's very easy to use and fulfulls your requirements.

Qw3r7yU10p!

Jul 14, 2004 at 8:40 AM

The standard library that comes with C++ has container classes and other things too.

Some of it used to be refered to as the STL (the Standard Template Library) and that is where the containers are. There are lists, dynamic arrays, maps double-ended queues and other useful things.

std::list is possibly what you need. If you are storing pointers to objects instead of the objects themselves, deque or vector will probably be fine (and it seems that is what you will be doing too). Lists are good because you can take sections out and splice them into other lists without having to copy the elements.

See the STL documents at sgi.com/tech/stl

[Edited by - petewood on July 14, 2004 9:40:09 AM]

Enigma

188

Enigma

Jul 14, 2004 at 9:01 AM

Depending on your access patterns you may be better with std::deque. In either case it should be a containter of CEntity* or boost::shared_ptr(CEntity) (or equivalent reference-counted smart pointer class). There are two reasons for using a container of pointers or pointer-like wrappers:

1. It looks to me like CEntity is a base class intended to be inherited from (i.e. you will later create a CPlayer class which inherits, directly or indirectly, from CEntity). If you try to place a CPlayer into a container of CEntity the CPlayer will be 'sliced' and will lose it's CPlayer-ness. Any information that was unique to the CPlayer class and not in the CEntity class will be lost.

2. It sounds like your objects are going to be fairly large. For large objects it is usually more efficient to access them via a pointer rather than copying them around. Of course one obvious solution to this problem is to slim your objects down a bit.

If you decide to use containers of raw pointers then be aware that your will need to delete the objects manually. Clearing the container will deallocate the pointer but not the object being pointed to. Also, do not try to use a container of std::auto_ptr.

Finally, I would recommend that you read this article on Hungarian Notation. It might not change your mind about whether you choose to use it or not, but it will at least make you aware of some of the arguments against it (as well as being a good read regardless).

Enigma

rypyr

Jul 14, 2004 at 10:56 AM

Original Poster: The first technique is not impossible, but may be impractical depending on your particular situation. Anyway, read up on the Standard C++ library. Particularly focus on the list container (denoted by std::list).

Regards,
Jeff

yaroslavd

Jul 14, 2004 at 11:03 AM

Quote:
Original post by RaptorZero
As for the second metod I didn't understand quite well. What is "std::list"? Could you explain it better?

I was thinking of creating a stucture like:
struct EntNode
{
CEntity Entity;
EntNode *pNextNode;
};

Actually, the structure you thought up is exactly what std::list is.

King of Men

126

King of Men

Jul 14, 2004 at 11:36 AM

One way is to declare the array to be 1000 elements in the first place (ie, more than you can possibly need) and keep track of how many elements are initialised.

Or, this being C++, you can use pointer arithmetic to write beyond the end of your array. I don't recommend it, though. ;-)

rypyr

Jul 14, 2004 at 12:16 PM

Quote:
Or, this being C++, you can use pointer arithmetic to write beyond the end of your array. I don't recommend it, though. ;-)

Gah!

Sneftel

297

Sneftel

Jul 14, 2004 at 12:37 PM

This bears repeating:

For small datatypes, it often faster in the long run to grow a std::vector than a std::list.

RaptorZero, what you need to understand about dynamic arrays as implemented by std::vector is that while they have to grow by copying, they don't grow by one element at a time. On most implementations, every time the vector runs out of space, its allocated size is more or less doubled. This means that as you add things to the vector, allocations become less and less frequent.

The STL, in fact, guarantees that back-insertions to vector are "amortized constant time". That means that in the long run, it won't get slower as your container gets bigger.

snk_kid

132

snk_kid

Jul 14, 2004 at 12:42 PM

Quote:
Original post by yaroslavd
Quote:
Original post by RaptorZero
As for the second metod I didn't understand quite well. What is "std::list"? Could you explain it better?

I was thinking of creating a stucture like:
struct EntNode
{
CEntity Entity;
EntNode *pNextNode;
};

Actually, the structure you thought up is exactly what std::list is.

Not quite, a list is an abstract data type it can be implementated with a number of different structures but in almost every case it's implementated with a doublely linked-list with STL's list type.

RaptorZero by the sounds of things (like everyone else has said) you probably need a list and the C++ standard library provides one, if CEntity is a concreate abstraction (meaning your not going to sub-type from it) i would say store CEntity intances rather than pointers to CEntity just make sure you have an appropriate default, copy constructor, deconstructor & assignement operator if CEntity has any pointers to avoid any problems with shallow copies, actually you may aswell start getting into the habbit of providing them anyways.

Also when you go to querying/modifying the state of an instance contained in the list, get the instance by reference to avoid redundant copies, if your not going to use the iterator to do it directly.

With this in mind & if CEntity is a concreate type, then this is the outline your need to have CEntity to for-fill the type requirements of the STL's containers:

entity.hpp

class Entity {  int _e;public:  //default constructor  Entity(int e = 0): _e(e) {}  //copy constructor  Entity(const Entity& en): _e(en._e) {}  //assigmenet operator  Entity& operator=(const Entity& en) {      if(this != &en) {          _e = en._e;      }      return *this;  }  int get_e() const { return _e; }  //to-do: add operations of entity};

Very simple example usage of list of entites:

#include "entity.hpp"#include <list>int main() {   std::list<Entity> list_of_entities;   Entity an_entity(3);   list_of_entities.push_back(an_entity);   an_entity = Entity(10);   list_of_entities.push_back(an_entity);   an_entity = Entity(6);   list_of_entities.push_back(an_entity);   //now iterator through the list and print values   for(std::list<Entity>::const_iterator itr = list_of_entities.begin();      itr != list_of_entities.end();      ++itr) {      //get using pointer notation      std::cout << itr->get_e() << '\n';            //get using reference notation      std::cout << (*itr).get_e() << '\n';      //another way is using entity reference types explicitly, no copies made      const Entity& en_ref = *itr;      std::cout << en_ref.get_e() << '\n';    }    return 0;}

More information about STL containers such as what operations are available for a particular type, you can look at SGI's docs

hplus0603

Mod

3,014

hplus0603

Jul 14, 2004 at 12:54 PM

As a programmer, it's your responsibility to choose the right algorithms and right data structures for the data that you manage. If you continually add and remove items of megabyte size to a container during runtime, you should use something like a list or hash map, rather than vector. Or use a vector of smart pointers, rather than a vector of items.

I recommend that you learn the STL container classes. They are pretty well designed, they are well debugged, and they are available everywhere; it'll save you a lot of time if you can use them where appropriate, and it'll remove a bunch of bugs from your programs.

gryfang

Jul 14, 2004 at 2:03 PM

With what you are intending to do I'd also recommend a list they are incredibly functional in your case.

A recursive method (or algorithm) is one that calls on itself
A crude example

int addREC(int sum, int addend)
{
if(addend== 0)
{
return sum;
}
else
{
if(addend< 0)
{
return (addREC((sum-1),(addend+1)));
}
else
{
return (addREC((sum+1),(addend-1)));
}
}
}

Removed polymorphism for lack of evidence (It's probably my mistake sorry) I'm trying to find where I found that out first at though

[Edited by - gryfang on July 14, 2004 7:03:11 PM]

snk_kid

132

snk_kid

Jul 14, 2004 at 5:06 PM

Quote:
Original post by gryfang
A class that is polymorphed is simply one that inherits (is a subclass) of two objects.

Either i didn't understand that statement or its not quite write. The meaning of polymorphism is quite general in the context of programming languages there is more than one form of polymorphism.

The one your most likely describing is subtype polymorphism which doesn't have much to do with a class extending two objects!?!? which isn't possible.

Basically its tool that allows you to defer/override the implementation of an operation in a abstract type to concreate sub-types.

If a client of the type needs to be able to handle all sub-types thats are not known at compile time then they can use a reference/pointer to the abstract type when an particular operation is called the correct implementation is called for derived type it refers/points to.

Keep in mind this is just one form of polymorphism there is more, ad-hoc types of polymorphism which are overloadding, coercion. universal types of polymorphism which are parametric polymorphism and subtype polymorphism just described.

SpaceDude

Jul 14, 2004 at 5:48 PM

Quote:
Original post by RaptorZero
Rypyr, I think your first metod is kind of ... IMPOSSIBLE :)
The 5 elements array was just an example, I think that if I copy a 200 element array holding 50Mb of data in the middle of the game, the player will notice a slight fps drop like to 1 frame each 10seconds :)

As for the second metod I didn't understand quite well. What is "std::list"? Could you explain it better?

I was thinking of creating a stucture like:
struct EntNode
{
CEntity Entity;
EntNode *pNextNode;
};

so that everytime I want to add a CEntity I search for the last node and "new" the pNextNode pointer. Will that work (and will that be fast)?

Thanks for your help...

Yeh i tend to do this... Always implement my linked lists manually rather than using std stuff... Something like this:

struct EntNode{    CEntity Entity;    EntNode *pNextNode;    EntNode() pNextNode(NULL) {};};CEntNode* g_pHeaderNode;// AddNodeCEntNode* pSaveNode = g_pHeaderNode;g_pHeaderNode = new CEntNode;g_pHeaderNode->pNextNode = pSaveNode;// DeleteNodeListCEntNode* pDelete;while (g_pHeaderNode){  pDelete = g_pHeaderNode;  g_pHeaderNode = g_pHeaderNode->pNextNode;  delete pDelete;}// Go Through Node ListCEntNode* pCurrent;for (pCurrent = g_pHeaderNode; pCurrent; pCurrent=pCurrent->pNextNode){  // Do something with pCurrent}

gryfang

Jul 14, 2004 at 7:05 PM

Edited a previous post because of a previous misunderstanding I had ... I'm looking for the source of my misunderstanding though.

RaptorZero

Author

RaptorZero

Jul 14, 2004 at 8:25 PM

Wow! I just got back from school and when I got here I saw 18 replies to my topic ... I didn't expect that! Thanks :)

Well, let's start:
Firstly, I'm sorry for not providing enough information, what generated some doubts

My class is not exactely CEntity, its CBaseEntity. Then you ask "What difference does it makes?". Well it means that this class wont be used anywhere, it is the base for all the other entity types wich will inherit from it (if you've ever seen Half-Life SDK you must know what I'm talking about)

And other thing is that I'll be using pointers only, unless it's much worse than instances (because it's my programming style. Some people put dashes in variables names, some people put spaces between variables and operators, I like working with pointers, so what!? haha :)) and, just like SpaceDude, I'dont like using pre-made functions if I can create my own (you can call it bullshit, you can call it superstition, I call it "NotBeingLazy" ... ok, it wasn't funny).

Anyway, I'll sure take a look at all theese ideas (std::list, vector, deque and so on). Thanks everyone for all the answers.

Ohh, I almost forgot, Enigma said something that I hadn't noticed before. From CBaseEntity there will be many other inherited classes ... how could I hold different classes in an array? Will I have to create an array (linked-list or std::list) to each of the many "child" classes from CBaseEntity?
How can I get arround this other problem (problems, problems and more problems)
If I have a pointer like this:

CBaseEntity *pGenericPointer;

can I make this:

pGenericPointer = new CDerivedEntity;
?

Thanks everyone and sorry for being a pain in the ass!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.