2
\$\begingroup\$

I'm working on a prototype 'life simulation' game which incorporates any number of objects / entities that may exist in the game.

Up until this point I had been working with vectors of the objects, with every object that gets instantiated gets automatically copied into a vector that allows for some very simple all encompassing functions like:

physics_manager()
{
    for(std::size_t i = 0; i < all_objects.size(); i++)
        all_objects[i].do_physics();
}

However, I've run into a problem when it comes to using pointers. Previously I used pointers to elements within vectors to interact with objects like this:

class object
{
    //Attributes of object
    object * other_object_to_interact_with;
    std::vector<object*> carried_objects
    //etc
}

I've now realised that changing the size of the vector (a frequent occurrence in this simulation) causes all pointers to elements within that vector to point to some random piece of memory.

I've considered using some form of unique ID for this (e.g. an int assigned to each object, then searching the vector for an object with that int to identify the right one), but this feels like an inefficient and ultimately wrong way to do things.

My question is, is there a container similar to the std::vector that:
a) can be iterated through easily for functions such as the above
b) can hold an arbitrary number of objects that changes during program running
c) is safe to use pointers to elements within it even if the container changes size

Alternatively, is there a way to use vectors to achieve the above without using pointers?

UPDATE: An additional thought - would the issue below be present if instead of vectors containing actual objects, I used vectors containing pointers to objects? Presumably then any pointers to objects outside of the vector would be to the objects themselves - how well would C++ memory manage this or would this lead me into new / delete territory?

FURTHER UPDATE: I migrated to lists rather than vectors, which was surprisingly easy. My most commonly used code snippet was:

for(std::size_t i = 0; i < vector.size(); i++)

This was very easily changed to:

for(auto & i : list)

With 'i' now pointing to an actual object of the list rather than an int that can be used to access the vector with vector[i]. No perceptible performance hit so far with approximately 20000 objects being iterated through.

Additionally, when there is a need to use an 'int' as a reference to one of the objects within the list, that's as simple as:

int j = 0;
for(auto & i : base_class_vector)
{
    if(j == desired_number)
    {
        //Do whatever's needed here
        break;
    }

    j++;
}
\$\endgroup\$
  • \$\begingroup\$ You should consider iterators. This SO topic seems to have some interesting info as well stackoverflow.com/questions/2447392/… \$\endgroup\$ – Coburn Oct 6 '16 at 14:04
  • \$\begingroup\$ @Coburn Assuming that the vector does not only changes size but also contains elements that will be removed, the iterators will become invalidated, so it's not really solution. It is if the vector is never deleted from, though. \$\endgroup\$ – Vaillancourt Oct 6 '16 at 14:09
  • 1
    \$\begingroup\$ Why use pointers to positions in the vector and not pointers to the objects in the vector? Another option is a map<id,object> where the id is a unique id across all objects. \$\endgroup\$ – ndenarodev Oct 6 '16 at 14:29
  • 1
    \$\begingroup\$ Maybe this is what you want seanmiddleditch.com/… \$\endgroup\$ – concept3d Oct 6 '16 at 15:53
  • 1
    \$\begingroup\$ plflib.org/colony.htm is another library that might meet your needs \$\endgroup\$ – amitp Oct 8 '16 at 2:11
0
\$\begingroup\$

The simplest container that fulfills the requirements you stated is std::list.

In this particular case, you shouldn't be using vectors, not just because adding new elements may invalidate references and iterators, but (and I am surprised no one mentioned it in the comments) because as you insert new elements, you are repeatedly re-allocating memory for the whole vector, which is inefficient.

Please have a look here to learn more about std::list. In fact, I would recommend familiarising yourself with the remaining STL containers (vector, list, set and map is all you need to make "informed" choices when deciding on what container to use, other containers are either their variation or are fairly specialised).

\$\endgroup\$
  • \$\begingroup\$ Thanks for this suggestion - std::list looks good, my only reservation would be the need to access arbitrary elements within the list (i.e. elements from the middle rather the front or back). Does this have a significant impact on performance compared to doing the same for a vector? \$\endgroup\$ – nathanburns Oct 6 '16 at 19:50
  • 2
    \$\begingroup\$ std::list does not support accessing random elements as such, you can, however, obtain a pointer to an element after it's been inserted and then store it (as you intended to do with vector elements in the question). When accessing an element by pointer, it makes no difference what container it is stored in in terms of performance (it does make a difference, in that a pointer to a list element will remain valid for as long as that element is not removed). \$\endgroup\$ – user91745 Oct 6 '16 at 21:00
  • \$\begingroup\$ Thanks wildQuoll - looks like lists are the best thing for this. I'm unfamiliar with some of the intricacies (e.g. iterators) but the fact that they don't reallocate memory on change of capacity is key. Also props to @concept3d for an alternative that appears to be a workaround to the vector memory reallocation issue \$\endgroup\$ – nathanburns Oct 7 '16 at 9:51
  • \$\begingroup\$ @wildQuoll An iterator to the object in the list would also be ok, no need to carry a pointer to it. \$\endgroup\$ – Vaillancourt Oct 25 '16 at 11:08
0
\$\begingroup\$

http://en.cppreference.com/w/cpp/container/deque std::deque

You still get a operator[] for random access, and can do deque[5] without needing to search through your container.

Your pointers are memory stable (auto* j = &deque[5]; deque.push_back(); *j; is always valid.)

Memory linearity is better then std::list, since it organizes in buckets rather then a pointer to every element.

At the end of the day, std::vector or even std::array is always going to be better performing.

So I do recommend trying to vector.reserve(MAX_OBJECTS); if you have a max amount of objects.

By calling reserve, you will both have memory stable pointers to those objects until pushed over the limit and you'll only have one memory allocation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.