• 11
• 13
• 12
• 10
• 11

# How do I keep relations between objects in vectors?

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

## 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 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 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 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 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 on other sites

stack of free indices

Ooh. Nice.

##### Share on other sites

stack of free indices

Ooh. Nice.

Thank you :) Pretty trivial really.

##### Share on other sites

Yeah, but there's all kinds of trivial things that don't occur to people until they get pointed out. It was valuable to me. ;)

##### 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