Sign in to follow this  

How do I keep relations between objects in vectors?

This topic is 400 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Just getting started with C++ I still have some troubles getting my head around some basic concepts.

In the current case I am wondering how to keep relations between objects in vectors since iterators, references and pointers are invalidated on a simple `erase()` or if a size increase of the vector causes a reallocation.

 

Example: I have game pieces which can move around and game tokens which are stationary. Both may be added or removed during the course of the game. Now I would like to have inter-vector relations, e.g. for a game token keeping a reference to a certain game piece and have it change its state if the game piece comes close enough.

Also I would like to have intra-vector relations, e.g. one game piece simply following another.

I can not use pointers etc. because upon a simple erase they may (or may not) point to something else.

 

How are those relations kept in C++? Do I have to iterate every time anew and search for the related item? Is a sorted map a better choice than a vector in this case?

 

Cheers

Share this post


Link to post
Share on other sites

An associative container with UID keys (you can just count upwards from zero) may help: http://www.cplusplus.com/reference/unordered_map/unordered_map/

The keys won't change even if it reallocates or you erase elements.

 

Or you can stick with vector and invalidate instead of erasing, relying on indices instead of pointers or direct references. You can hold a parallel vector of bools indicating which objects are 'alive' and re-use 'dead' slots when allocating rather than always pushing to the back.

Edited by Khatharr

Share this post


Link to post
Share on other sites
The pointers to your objects won't be invalidated by erase if your vector us a vector of pointers e.g. std::vector<obj*>.

This does however have its own gotchas with regards to memory management and might not be the best solution.

In my experience it's best to store identifiers like pointers or other unique ids, with something like std::map unless you really need the objects stored consecutively with fast iteration across the set (basically what Khatharr said).

Share this post


Link to post
Share on other sites
store indices rather than iterators or pointers

 

The pointers to your objects won't be invalidated by erase if your vector us a vector of pointers e.g. std::vector.

One of these two. Both work fine for the purpose of "referring to an object", but they don't work equally well in every other situation.

 

Indices and a freelist ("Aardvark") are nice because incides usually take less storage (you don't have more than 4 billion elements in a vector, do you... most often, they might just be less than 64k, so indices will be 2 or 4 bytes only). On the downside, you must manage that extra freelist, but you will likely want to do that anyway to save on allocations.

 

Pointers ("braindigitalis") to objects have the advantage that you can very easily iterate over the vector of pointers and, at the cost of one indirection, apply a transformation to the entire set of objects. Sometimes, iterating over all valid objects is just what you need to do.

Cache coherency may not be perfect (though usually acceptable), but the approach is workable.

 

Using a vector that contains "holes" managed by a freelist, this is more difficult unless the transform has no side effects. If there are indeed no side effects and if the valid objects by far outnumber the "holes", you can just run the transform over the whole block of memory and screw the rest. And in that case, you're running way more cache-friendly than via a pointer indirection (to a set of possibly non-contiguous objects), too. This often makes up for the time you waste processing objects that are invalid.

The downside is, you just can't do it if there are side effects, and in case there are a lot of deleted objects, you are doing an awful lot of needless work.

 

Figuring out which objects to process (if processing invalid objects is prohibitive) is... ugh... painful. Unless you spend extra "money" on keeping a Is_valid boolean around per object, or something...

Edited by samoth

Share this post


Link to post
Share on other sites

Using a vector that contains "holes" managed by a freelist, this is more difficult unless the transform has no side effects.


If you don't care about the order the objects are in, you can add a level of indirection and maintain an "index map" that maps indices (handles, really) as seen by the outside world onto real indices in your underlying storage. Then when you erase an object, you can use the swap-and-pop idiom to keep your objects compacted together meaning that you wouldn't need to check which objects are valid when you iterate through the container. Whenever you move an object in the container, you just update the index in the index map. Edited by Oberon_Command

Share this post


Link to post
Share on other sites

Using a vector that contains "holes" managed by a freelist, this is more difficult unless the transform has no side effects. If there are indeed no side effects and if the valid objects by far outnumber the "holes", you can just run the transform over the whole block of memory and screw the rest. And in that case, you're running way more cache-friendly than via a pointer indirection (to a set of possibly non-contiguous objects), too. This often makes up for the time you waste processing objects that are invalid.
The downside is, you just can't do it if there are side effects, and in case there are a lot of deleted objects, you are doing an awful lot of needless work.

1) Sorry for the basic question, what exactly is meant by transform and what kind of side effects would be problematic.
 
 
2) The index based access with persistent objects that may be, well... soft deleted, sounds compelling. Right now I am using an attribute, set to true to use it in conjunction with remove_if, so I would not mind the extra field needed. Would it be another option to use an unordered map (fast key => value access) and a vector keeping the keys for fast iteration? Or would this just be a weird reimplementation of ordered map?
 
 
3) Thanks for the answers, that will give me quite some things to ponder. Yet the general problem does not seem to be too exotic. Are there no easily usable, unit tested, battle proven libraries for these things? Edited by wellnoidea

Share this post


Link to post
Share on other sites
what exactly is meant by transform and what kind of side effects would be problematic

Something that runs over many, or all elements in the container, like for(auto& elem : vec) do_something(elem); where do_something could be... pretty much anything, for example increase a unit's HP by one point if it is not at maximum, or collide it against terrain.

But it could also be something that has "side effects", such as allocate a string, load a resource, show "you're dead", play a sound.

 

If no such "side effects" can happen with whatever you do, then it is a valid thing to simply run over the whole block of memory and do whatever you do to every object, even objects that aren't valid. This can be big win because of cache coherency. Jumping around following indirections and only processing the objects that are actually "alive" is the more correct approach, but it might turn out slower (up to 10-20 times slower in the worst case). So, when it's not strictly necessary to be super correct, it's often worth just doing everything.

 

On the other hand, imagine the havoc of having AI decide to attack you, and bullets be created by units that died minutes ago! That would definitively be a "side effect" which you would want to avoid! You really only want to let units that are alive decide to shoot at you :)

 

 

I would not mind the extra field needed

An extra field is really only needed if you want to still process everything linearly (that is, not follwing indirections) but skip over invalid objects because processing them would have side effects that you don't want. If you follow indirections (either index or pointer, does not matter) then that is not an issue because you will never access an invalid object.

 

The only real downside follwing indirections is that you don't know in advance the memory access pattern. It might, in the (luckily rather unlikely) absolute worst case, have a cache miss on every item, which take about 20 times more time. Mind you, worst case. Processing everything linearly has no worst case, it guarantees (very obviously) that item 1 is processed first, then 2, then 3, and so on... you walk through memory linearly which is the perfect pattern for hardware prefetching. The impact of cache can be so large that sometimes it's faster to do twice as much work, if only that means you're walking over memory linearly.

 

 

 

Yet the general problem does not seem to be too exotic. Are there no easily usable, unit tested, battle proven libraries for these things?

Not exotic at all. The snippet of code that Aardvark posted is an "easily usable, proven library", if you will. It's really quite simple, no magic.

Edited by samoth

Share this post


Link to post
Share on other sites

I use a gigantic database to store the data of all of my objects. When I need to iterate over data, I use a vector of safe pointers to go through the entire object list. It won't matter if the vector has been resized or not, all the data for the objects exist elsewhere.

Share this post


Link to post
Share on other sites

@Tangletail the large store sounds intriguing too, reminds me of the "single source of truth" priciple in reactive programming, albeit you probably use it not in that way

@samoth: if I understand you right and linear iteration use hardware prefetching which makes them (most likely) is considerably faster than indirections it should rather stick with those
regarding the side effects, it seems easy enough to avoid them while still iterating over the objects likeso
 

for(GamePiece &gamePiece: gamePieces)
{
    if (gamePiece.isAlive)
    {
        gamePiece.update()
    }
}

Time for a design decision. I think I will stick with an extended version of Aardvajks solution. Let's see how this turns out :)

Share this post


Link to post
Share on other sites

This topic is 400 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this