19 replies to this topic

[StoneMask]

Say I have an enemy class that I have multiples of, and I want to repeat actions with them by cycling through them in a (circularly?) linked list.
Is it acceptable to make them nodes in a linked list, executable code and all?
I asked one of my friends about it, and he told me to look up function pointers.

Could someone explain this to me in detail?

[Yrjö P.]

Your explanation of the situation is confusing. Do you mean you are storing the enemies in a list, or that you want to store "actions" in a list? What kind of "actions" are we talking about? When are they supposed to be ran? Do they affect all enemies, or just some?

In any case, I'm pretty sure this is not a problem you need function pointers for.

Edited by Stroppy Katamari, 15 December 2012 - 08:04 PM.

[StoneMask]

I mean, can I organize my enemy class in a linked lists where each enemy object is a node that has data, as well as actions that they can execute. I looked it up, but all the literature I found doesn't say anything about nodes using functions, only storing data.

[dmatter]

I mean, can I organize my enemy class in a linked lists where each enemy object is a node that has data, as well as actions that they can execute. I looked it up, but all the literature I found doesn't say anything about nodes using functions, only storing data.

Sounds like you're thinking of making an Enemy class that both acts as its own linked-list node and as an enemy character. Based on The Single Responsibility Principle I would advise against that.

Instead, think of it this way: An enemy object *is* the data in a linked-list node.
In C++ this is actually really easy to do since there is already a linked-list container:

std::list<Enemy> linkedListOfEnemies;

Edited by dmatter, 15 December 2012 - 08:19 PM.

[StoneMask]

So I just have to make a linked list of enemies?
I just didn't really know if the object was considered data or not. So it's perfectly fine right?

And how would I implement it without the standard container, from scratch?

[StoneMask]

Nevermind, I understand now. The data the node holds should be an enemy object, right.

[Xai]

Nevermind, I understand now. The data the node holds should be an enemy object, right.

Exactly.
And yes, in an OO language (like C++) an "object" is valid data to be in a variable or list ... and the fact that you can call that data object's methods is totally normal.

[Servant of the Lord]

Why not just keep your enemies in a vector, and keep track of an the current enemy in the vector?

std::vector<Enemy> enemies;
unsigned currentEnemy = 0;

enemies[currentEnemy].DoSomething();
currentEnemy++;
if(currentEnemy >= enemies.size()) currentEnemy = 0;

You certainly could have enemies in a linked list, but what are you hoping to get out of that?

What are you wanting to do, that std::vector can't do for you? Dynamic arrays (like std::vector) have their pros and cons, and linked lists have their pros and cons. It most situations, though, the cons of std::vector are so minor that unless you are trying to hyper-optimize something, or are dealing with a staggering amount of data, it really doesn't make sense to not use it.

[StoneMask]

Well, would there be a particular drawback to having enemies in a linked list versus a vector?

[Servant of the Lord]

Well, std::list<> is a standardized linked list, so if you used that, then the drawbacks would be very few. If you are making your own, there are more. Which is fine if making a linked list for personal education and practice, and not for real project code.

One drawback is element access speed - random access to an array is very very fast. Random access to a linked list is very very slow.

The benefits of linked lists are:
A) Fast inserting/removing in the front, back, or the middle.

The cons are:
B) Slow random-access.

The benefits of a vector are:
A) Fast inserting/removing from the back, with an occasional reallocation cost.
B) Fast random access.

The cons of a vector are:
A) Slow inserting/removing to the front or middle.

Each are equally good at "iterating in a loop" - in theory; though in reality I wouldn't be surprised if a vector outpaced the list.

However, if the real Pro vs Con is, "optimized for resizing, moving, removing" verses "optimized for accessing", then you have to ask yourself, how frequently do you insert/remove verses how frequently do you access or iterate?

If you add and destroy 200 enemies a frame, then a list might be preferable (though I'd still use a vector, personally, and just flag 'dead' enemies for reuse).
But more than likely, you add/destroy an enemy occasionally, but iterate over multiple enemies every frame.

It's really not a big deal whichever you go with, and overthinking it would be premature optimization... but the "proper" choice, if I'm understanding what you are wanting, is a vector - and it's good to know when to use what tool, and why it's better or worse in what situations.

Again, if your only reason for using a linked list is for circular iteration, then here is a circularly iterating vector:

myVector[index %= myVector.size()].DoSomething();

[StoneMask]

The intent is for a project that is intended for education and practice. So I want to utilize as much stuff as possible into a project that uses each of the things I implement the best ways I can.

The maximum amount of enemies on screen will be somewhere around 20, but no greater, I think. Only one enemy can die at a time; it is not possible to kill two at once. They are first flagged dead, then deleted, and it happens with a "death freeze frame", as in, all action freezes to let the enemy's dying animation play out, so computing time will probably not be noticably affected by moving data around. There is nothing graphics-intensive, as it is all run in command prompt and all sprites are character-based. I have no graphics to worry about. I will never have to worry about randomly accessing them because they're moved in sequence.

I made another thread about my enemies' data management and the people in the thread told me that I should not just flag the enemies dead, which is what I did before, and that I should delete enemies when they've been killed. So I've been working with that intent in mind. If you can convince me to do otherwise, then I'll change my method.

[Servant of the Lord]

If for education purposes as you say, it sounds like a good plan.

You probably don't need to mark and delete enemies, you can just delete them without marking them in a list (unless you need them marked for unrelated reasons).
If using vectors, you can mark them without deleting them, or using the "swap to end" trick if element ordering is insignificant.

[EddieV223]

Read this if you really want to understand the question, Vector or List?
http://www.baptiste-wicht.com/2012/11/cpp-benchmark-vector-vs-list/

[Álvaro]

I am late to the game, but I wanted to mention that the first few times I read a description of what objects are, I was as confused as the OP. "An entity that encapsulates data and the code that acts on it together", or something like that is a horrible description. An object is just the data. Then we provide a bunch of functions that act on the data, and we put that in the same block as a way of mentally organizing things, but when you compute the size of an object, you only get the size of the data, not the code. When you write an object to a file, only the data is written. It would be good to be clear about this when introducing someone to objects.

[rip-off]

To clarify:

An object is just the data. Then we provide a bunch of functions that act on the data, and we put that in the same block as a way of mentally organizing things, but when you compute the size of an object, you only get the size of the data, not the code. It would be good to be clear about this when introducing someone to objects.

Not quite. If you have a C++ object that has virtual functions, the size of the object is more than just the data. It isn't that the code is included in the object, but typical implementations include an indirect reference to the code (usually via a VTable pointer).

When you write an object to a file, only the data is written.

You cannot, in general, sensibly write non-POD types to a file directly.

[StoneMask]

Well, maybe I said my intentions wrong. This is for self-education, but it's going to be a finished product I distribute to people, and I don't only want to know how to do things like this, but have them used in my programs appropriately. So really what I'm kind of asking is what the best thing would be to do for something like this problem. I'm leaning more towards a vector now, because as I see it, its qualities really only shine through when there is a large amount of data being used, and the objects I'm using definitely don't approach a kilobyte.

Edited by StoneMask, 17 December 2012 - 11:46 AM.

[Servant of the Lord]

The way I see it is that std::vector<> is the default container type one should go to. It'll be the best solution in the majority of circumstances. Only when someone needs specialization for different purposes do you reach for another container type (whether it be a linked list like std::list, or a quadtree or something of that nature).

However, it is of very significant benefit to roll your own containers for learning experience - so don't let me discourage you from that! But at the same time, you have to be willing to discard your own containers and go back to the tried and true, heavily optimized, heavily debugged standard containers after you practice with your own. This is hard for alot of people, because they want to use their own after all the work they put into it ("And why not, after I spent two weeks on it?"), and sometimes, overtime, they get caught into NIH and YAGNI - both which leads to not actually finishing projects, and instead just working on the sub-projects without actually releasing anything real - of which programming culture is far too filled with.

That is my personal opinion - other people's opinion will vary. You are intelligent enough to analyze the data yourself (now that you know there is data to analyze) and then decide what, in your personal and unique circumstances, is the best option at the present situation, and the best option for future situations. My (and everyone's) armchair guesses at what's best for your current project should always be taken as counsel but not law, as it may be flawed from us not having all the details that you alone possess.

[Álvaro]

To clarify:

An object is just the data. Then we provide a bunch of functions that act on the data, and we put that in the same block as a way of mentally organizing things, but when you compute the size of an object, you only get the size of the data, not the code. It would be good to be clear about this when introducing someone to objects.

Not quite. If you have a C++ object that has virtual functions, the size of the object is more than just the data. It isn't that the code is included in the object, but typical implementations include an indirect reference to the code (usually via a VTable pointer).

When you write an object to a file, only the data is written.

You cannot, in general, sensibly write non-POD types to a file directly.

I seem to have a problem lately when I try to keep things simple: Someone will come and pick my statements apart, instead of trying to understand what I am saying.

There is a common way to introduce objects out there as something comprising both data and code. At the same level of detail of that statement, I propose an alternative ("Objects are only data, but we write the code that manipulates the data in the same block to keep things neatly organized") to help beginners have some intuition as to what's going on.

When talking to a beginner that is confused enough to think that you store code in a linked list, I think your clarifications hurt more than they help. But yes, they are correct.

[EddieV223]

(list) qualities really only shine through when there is a large amount of data being used, and the objects I'm using definitely don't approach a kilobyte.

http://www.baptiste-wicht.com/2012/11/cpp-benchmark-vector-vs-list/

This is true. You should use vector.

Often people argue that if you doing lots of random insertion and deletion that you should use a list. This is clearly not true ( according to the link provided above ), unless you are using LARGE data structures atleast 1KB each and thousands of them. This is because vector's memory is continuous and uses the cpu's cache MUCH more efficiently than a list ever could.

Also if you use the vector properly then you can cut down on some of its bottlenecks. For example in an unsorted vector you should always push_back(), and if you are deleting an object you can switch it with the last one and then delete the last one, this prevents the vector from having to move every element after the one you were going to delete. Also you can reserve memory for a vector so the vector doesn't have to resize itself.

Edited by EddieV223, 17 December 2012 - 01:36 PM.

[Yrjö P.]

If you make your own container (such as list) for learning purposes, I'd suggest building it with the exact same interface as the standard library's corresponding container (or actually, its subset which only contains the critical features you need).

Then, if you have some separate project of your own, you can normally use the standard library container (which will be faster and more reliable than your own), but you can swap in your own container for testing purposes or for the hell of it. You'll increase your understanding of the standard interface, and good interface design, at the same time.

Just typedef it somewhere in your project and you can switch between your own container and standard container with ease.

Edited by Stroppy Katamari, 19 December 2012 - 10:45 PM.