In the game I am creating I have a class which describes the units in my game: class Cunit { public: blah blah blah... }; Now, this is an RTS so the number of units can vary. So, I thought the best way to handle this was using a vector - makes sense right since I need an array that can change length dynamically. So, I turned to STL and I now have these globals: vector unitlist; vector::iterator itor; Basically, a list of pointers to the units currently in the world. And, if I want to add a unit to the list I do this (maybe inside a function such as make_unit(): Cunit *temp=new Cunit(); unitlist.push_back(temp); This seems to work, but I have some doubts. Should I get rid of the *temp and is this causing memory leaks? Anyway, I can now call the member functions of Cunit using unitlist->method(); However, my problem is removing units from this list and deleting the memory reserved for them. Right now I use a function such as this: void unitlist_remove(Cunit * c) { for(itor=unitlist.begin();itor!=unitlist.end();++itor) { if(*itor==c) { unitlist.erase(itor); break; } } } Basically, I just search through the list until I find what I am looking for and then use the built in STL function erase to remove it from the list. Now where should I call delete and how should I do it? This is some crazy pointer shuffling here and I am just worried about memory leaks mainly. Can anybody give some advice? Abs "Bulk e-mail is the most cost effective form of advertising to date. That is why you receive them every day."

What is this list for? The units a player controls? The type of units in the world?

If it''s a list that changes dynamically, it shouldn''t be a vector. It''s extremely inefficient to insert or remove anywhere but from the _end_ of a vector. Only use vectors if the size of your array changes infrequently and only by adding or removing items at the end.

As far as inserting dynamic objects, you''re doing it the right way. In fact, you don''t even need temp*, you can just do:
unitlist.push_back (new Cunit);

Since you have a vector of pointers, this is correct. You just have to be sure when the last reference to the unit is removed from the vector, you also delete it. You are not doing this; erase merely removes the item from the list. You need to "delete *it", then "unitlist.erase (it)". As it is, you''re currently leaking all over the place.

Reevaluate your use of vector over list, or even map, and delete things before you erase them from the container--should be fine then.

Thanks. Yes this is obviously causing a memory leak and that was the question. I was just wondering if it made sense to delete it before or after I erased it. These are units for player control right now, but the number of units can vary quite a lot. Also, the reason I was using a temp variable is because there were some member variables and function calls I would like to set/make before I added it to the list. Although, since I add units to the end of the vector I guess I can just use unit_list[end index] to access it. It does the same thing either way.

I will look into the other STL data types. It is just that I have used the vector class before so I am familiar with it.

Abs

My advice is to use the list container if you have to erase a lot of elements that are not in the front or end. Also, I would suggest inserting objects rather than pointers and let STL do all the memory management.

//Insertingunitlist.push_back( Cunit() ); //and deletingunitlist.erase( find( unitlist.begin(), unitlist.end(), c ) ); 

If you do that you wont have to worry about memory leaks..

Edited by - snale on June 3, 2001 5:49:46 PM

Ya I probably will go with a list, but I am still going to store pointers. The Cunit class is huge and I don''t want the overhead of all of that object copying.

Abs

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

Just FYI, I use STL a lot and find myself using containers of pointers about 99% of the time. On very rare occassions, when the objects are not large or when changes to the container are not happening often, I use a container of objects instead of pointers. Containers of pointers are generally needed because:
- inherent object copying--at least one on insertion, possibly many more with vector and deque containers
- it''s the only way to store polymorphic objects
- you can do cross-referencing and/or have the same "object" contained in different lists.

Only when these rules don''t apply do I ever not use a container of pointers.

Incidently I''m also working on a strategy game and faced the same problem of deciding between array and list. Lists suffer in terms of being limited to sequential access. You won''t be able to use unit IDs due to very slow process of retreaving pointers to them. This means you''ll have to keep references to other units by storing pointers to them. And this is definately not a good solution. Without reference counters you''ll soon run into serious problem of calling an object that''s been deleted long time ago (KIA). But using counters is also not pretty, you''ll have hard time keeping increment/decrement functions synchronized. The best solution is to use both arrays and lists! Although you''ll have to update both structures, if you do it in an efficient way, the overhead is minimal. I''m not going to explain it in detail, but I''ll give you a few hints. You''ll have to allocate a static array with the number of elements greater than the number of units in your game in any given time. When you create units give them an ID number which corresponds to the array index they are stored in. Just make sure you never assign the same number twice. When scanning for free space to insert a unit do not start from 0 index, start from the index you inserted your last unit into. The chances are the unit in the next cell will be dead by now. Of course, before inserting check if the unit is alive, and if not delete it. Updating corresponding linked list should be much simplier. Implementing this data structure will provide you with efficient random and sequencial access.

Just responding to that last post. I am still new to STL, but I believe that the map data type will do what you are describing. I believe it is a tree structure with near heap-like access times. Just a consideration.

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

It''s too bad AP posted this as a reply rather than a new topic--if I knew who it was, I''d write a private email & ask the poster to do so.

Regardless, this is a really great problem. Heck, I might even use it in an interview (if I could figure out a way to make it not game-related, since I don''t work in a game company).

What you need to have in front of you is a good idea of what the efficiency is for operations on STL containers:
vector: insertions = O(N) [O(C) in special conditions], random access = O(C)
list: insertions = O(C), ''random'' access = O(N)
map: insertions = O(log N), search = O(log N)

For the uninitiated, "O(N)" is called "Big-Oh" notation, and specifies the order (i.e. without constants or multipliers) of the number of operations required to perform a task. O(N) means that there is a linear relationship between the length of the container (N) and the time to do the op. O(C) means it happens in constant time--the best by far. O(log N) means it takes log (base 2) the length of the container to do something.

It''s a little tricky relating these because your access to each of these containers is completley different. Random access to a vector is obviously just getting the Nth element. For a list, we''re assuming for this problem that each element in the list has a unique index value, or that we''re searching for the Nth element in the list. Either way, it takes O(N) time. And for a map, of course, we''re talking about finding a matching key, which takes O(log N) time in a red-black tree (standard implementation for STL).

Back to the problem:
You assume that we''re going to have a static master vector of structures (pointers I assume?) equal to the size of the most simultaneous units allowed in a game. My initial reaction is that this is a fair assumption--most multiplayer games have a limit on units to keep things manageable and for gameplay balance. The problem lies in knowing which slots in this array are in use.

Now, the AP''s idea was to keep a lastUnit index around, and start searching from there in the array for the next open spot. Here''s a problem:
--when your vector becomes full, i.e. not sparse, i.e. end of game, finding an empty space actually takes O(N) time. In fact, the odds are you''ll have to traverse the entire vector, and you need code in place that always checks for the end of the vector to wrap around to the beginning.

Absolution astutely pointed out that a map might be appropriate; any time you see ''lookup by index'', map should be something that pops into your head. Maps do kick ass in no uncertain terms, but I don''t think they''re appropriate here. If you know the element you''re looking for, you can retrieve it in O(log N) time. But if you''re trying to ''find'' and empty spot in the map? How do you go about doing it? It''d basically be the same way as with the vector--start from some number, and start sequentially checking whether that element exists. Again, when the container (map) now becomes full, you have to do this N times, making the operation now take O(N*log N), which is worse than with a vector. Unless there''s another way to use the map that I''m not seeing, this wouldn''t be a good solution.

Here''s a solution I thought of; it''s a memory hog, but it should get you crazy efficiency:

vector<Unit*> s_liveUnits (MAX_NUM_PLAYERS * MAX_UNITS_PER_PLAYER);map<int> s_deadUnitIdxList;//// during game initializationfor (int i=0; i<s_liveUnits.size (); ++i) s_deadUnitIdxList.push_back (i);//// to add a unit to the gameif (s_deadUnitIdxList.empty ()) throw runtime_error ("Unit limit reached");const int unitIdx = s_deadUnitIdxList.front (); // get first index from lists_deadUnitIdxList.pop_front (); // remove it from dead lists_liveUnits[unitIdx] = new Unit (); // initialize & use//// to remove a unit from the gamedelete s_liveUnits[unitIdx]; // assuming unitIdx was passed into funcs_deadUnitIdxList.push_back (unitIdx);

I think this is pretty spiffy, though it''s my first shot at something like this. The obvious drawback is that you''re using a lot of memory (3 ints * size of array) to track this indices, but it''s bounded and it''s actually at a maximum at the beginning of the game. You can shave a byte or two off if you want to make it a short (assuming you have less than 2^16 possible units in the game).

Benefits are:
-- O(C) time to find next index
-- O(C) time to put an index back into the index list
-- Easy check to see if you''ve saturated your unit list

You could also, in a similar manner, create a list of live unit indices for the purpose of game upkeep: drawing units, removing dead units, etc. This would be more efficient in the beginning of the game than traversing the entire vector since it''s most definitely sparse. The cost would be the extra maintence of a second container.

Anyway, just my ideas from the hip. BTW, this is somewhat based on a scheme I''ve seen used for embedded communications systems: you allocate a certain amount of memory, split it up between M packets, and you drop each of those packets into an "empty" list. Each time you want to send a message, you take the packet from the "empty" list and put it in the "used" list. When the next layer''s done with the packet, remove it from the "used" list and put it in the "empty" list. All of your memory allocation is on startup and it cannot grow without bounds--very important for embedded apps.

Stoffel, I assume you meant something else than a map in the code you posted? A map maps a key to data, so map<int> is not possible. Also, map does not provide pop_front and push_back.

A deque is more approriate here: it provides constant time insertion/deletion at both the beginning and the end of the container. If you''d use vector, pop_front would be very expensive, as all other elements are shifted one place to the left.

You could also use a stack: at initialisation, push all available indices in the unit vector. When a unit is initialised, the top of the stack is popped. When a unit is deleted, the index associated with that unit is pushed to the stack. The STL stack class is actually an adaptor class that uses the deque container internally.

HTH