Just so you know, I have no need for random access right now so I am still trying to get a simple list implementation going. All units are controlled by the players so far and are thus accessed through pointers (which are stored in a map tile structure). Anyway, as you may have guessed I''m running into pointer and iterator problems when a unit is destroyed. In certain cases it crashes the program and I am spending too much time trying to hunt down these lost pointers. Sigh. I loathe the thought of a developing a complex memory management scheme.

Abs

"Bulk e-mail is the most cost effective form of advertising
to date. That is why you receive them every day."

OK, a couple of points:
1) Yes, I meant list instead of map. I named the variable a list, and I wrote it like a list, but I declared it a map. It was late.
2) Yes, now it is even later. 2:30AM by my watch. But I had a thought, and had to post it. This is the final week of classes for me, final project due next week, so odd hours will be had and odd posts will be made--everybody make sure to triple-check my posts in the near future.
3) Dammit, JungleJim took half my thought. =) I was thinking, "why use a list when you''re only operating on the front and back? That screams deque". However, there''s a problem with deque:
-- when I ran speed tests on a deque of characters as a circular buffer, it was 10 times slower than my own memory routines
-- it still has some memory overhead; probably not as much as list, but some.

So, the answer, as JungleJim alluded, is a stack--but with a vector, not with a deque.

Remember way back when I said that insertions into a vector could be O(C) if you''re careful? Well, here''s how you''re careful:

vector<int> s_deadUnitIdxCont;//// in initialization// allocate memory for vector all at onces_deadUnitIdxCont.reserve (MAX_UNITS_PER_PLAYER * MAX_PLAYERS);for (int i=0; i<MAX_UNIT_PER_PLAYER * MAX_PLAYERS; ++i) s_deadUnitIdxCont.push_back (i);

The rest of the code is as I posted before, except you use back () and pop_back when getting a new index. There ya go, almost zero overhead (3 pointers in the whole vector) and you have all your operations in constant time. Whee!!

OK, really tired now, project will have to be finished tomorrow. Hope I was able to illuminate more than I obfuscated.

Of course, if you know up-front exactly how many units you will ever have in the vector, you almost might as well just use an array

Other assorted opinions:

Funny how the standard containers were designed to store objects rather than pointers: not to mention the fact that the auto_ptr, ideal for this task, doesn''t work within the containers. Yet in almost every real-world situation I''ve come across, it''s been pointers I''ve needed to store. Silly.

Unit IDs and lists: no reason it will need to be very slow. Traversing a list isn''t that bad. There are numerous ways you can optimise it. But I think you should (a) code it in the simplest way first, worrying about efficiency later, and (b) put a layer of abstraction between the calling code and the ''working'' code. That means not sprinkling your code with lots of calls to the standard library. Instead, you use something like "Cunit* GetUnitByID(int unitID)" throughout your code, and so if you need to change from a list to a vector or a map or a multimap or an auto-balancing doubly-linked binary skip list (yes, I know that''s made up ), you break none of your calling code and only need to make changes in 2 or 3 places.

Stoffel... you''re right to change to a vector from that list. Just using pop_back and push_back on a vector is nice as it saves you the overhead of all those individual list nodes. Also, if you have a fixed limit on the number of units, that vector can be preallocated, meaning absolutely no reallocations. Now that''s fast Another good reason to use a layer of abstraction: even people like Stoffel who know their stuff often decide to change the underlying algorithms and structures when a better idea comes to mind. So let that be a lesson to all up and coming coders!

A map is a better solution, because unit can come and go. So if a unit dies and it is located in the middle of the vector or the list, then you need to go get it.

Where with a map, you simply erase it with the key. There solution that takes more memory and that will be faster like the Stoffel example, but map is fast enough until it is not fast enough. And actually, all speed description in the STL is actually an upper bound that STL writers need to follow. So some compiler may provide O(C) insertion in a map.

I feel a map is easier and more flexible to use than an array solution.

And anyway, if in then end this is your bottleneck(which I doubt a lot), then you can create a container that uses a Stoffel like solution but uses the same interface than a map so you actually don''t need to modify your core code.

quote:

---

Original post by Gorg

A map is a better solution, because unit can come and go. So if a unit dies and it is located in the middle of the vector or the list, then you need to go get it.

Where with a map, you simply erase it with the key.

---

This all depends on the specific system, really. Is there a chance of 'dead' units being referenced? In which case, you can't re-use their slot, no matter what structure you use... they will need to be left NULLed in order for objects holding those references to know they are dead. On the other hand, if they'll never be referenced once they're dead (perhaps through some sort of broadcasting, or perhaps simply by never needing any persistent references), then vector is equally as good as a map. Remember, a vector is syntactically identical to a map with the key type as an int as far as access goes.

quote:

---

There solution that takes more memory and that will be faster like the Stoffel example, but map is fast enough until it is not fast enough. And actually, all speed description in the STL is actually an upper bound that STL writers need to follow. So some compiler may provide O(C) insertion in a map.

---

I agree in principle with choosing a working implementation first, and optimising it later, when you know you need to, and not before. Decide what you need to be able to do - decide on an interface for doing these things - pick the data structure that most closely models the interface and predicted usage patterns - implement the system behind the interface. 90% of the time, your first choice is more than adequate.

quote:

---

I feel a map is easier and more flexible to use than an array solution.

---

Again, what is a map, if not just a vector with a choice of key types? If you're going to use an integer for the key type, all you have is essentially the same system and interface except (a) you save memory on elements you're not using, and (b) you lose memory on elements you are using.

Edited by - Kylotan on June 5, 2001 8:42:17 PM