Deciding which Container to use for a Manager Class.

[Ruckamongus]

Hello all,

I'm not sure if this is the proper section; sorry if it isn't. My questions is about C++ more than SFML. Basically, I have a few different managers in my game engine (InstanceManager, SoundManager, and SpriteManager). Currently, their implementations use a vector for storage, as vectors have fast lookup time. However, I'm wondering if a different container is more appropriate. I'm using C++11 so I'm open to the newer containers as well. I'm looking for the "best" container that balances rapid lookup with quick deletion from a non-terminal end. I haven't had any formal classes on data structures or containers so I don't know the inner workings of more advanced containers. (I've written my own singly/doubly linked lists, a primitive vector class, and a queue though.)

I'm sorry if this isn't appropriate for the SFML forums, but I figured since I'm storing sf::stuff I might as well ask some more seasoned programmer their opinions.

My current managers are pretty simple, and look something like:

class SomeManager
{
     public:
          bool Add(sf::something* Address);

     private:
          std::vector<sf::something*> m_Somethings;

};
 

The use of pointers is to avoid copying and such. I know that manual memory management is frowned upon with unique pointers, but it seems unnecessary when the manager deletes everything for you anyway (in its dtor).

Would a unordered_map be a good alternative?

Thanks!

[eXpl0it3r]

I'm looking for the "best" container that balances rapid lookup with quick deletion from a non-terminal end.

Asking for "the best" way is mostly always the wrong question. There simply is no "the best" way. Everything is relative and highly depended on what the code should do and for what it should be laid out. I mean there's a hugh difference between having to handle 100 textures or 100'000 textures, but not only the use case matters but also the integration and location within the project matters.
So to figure out what's "a very good" way of doing things "for your project", it'd probably best to read more on your own on the topic of different containers.

The use of pointers is to avoid copying and such.

Well if you use pointers then the containers to not matter that much, because the containers will essentially just store the pointers and not the actual data. So look up and deletion will often be very similar.

The STL is built to guarantee high performance with the correct use of the containers, thus up to a certain point it doesn't matter that much which one gets used. Also i most cases you should choose the container by it's use case and not by it's 'performance' (otherwise you'd always have to choose a plain array/std::array). So if you want to use indices for your data, then go with a std::vector. If you want to have key->value matching and it should be ordered the go with std::map, if the order doesn't matter then go with std::unordered_map.  If you run into performance issues caused by your manager(s), then you could reconsider the choice.

I know that manual memory management is frowned upon with unique pointers, but it seems unnecessary when the manager deletes everything for you anyway (in its dtor).

I really advise you to reconsider that decision and read a bit more about the actual problem with manual memory management (e.g. read this thread fully).
Keep in mind though that shared_ptr might be more appropriate for 'manager' classes, since you most probably will share the resource rather than transfer the ownership (what unique_ptr does).

[Ruckamongus]

Asking for "the best" way is mostly always the wrong question. There simply is no "the best" way. Everything is relative and highly depended on what the code should do and for what it should be laid out. I mean there's a hugh difference between having to handle 100 textures or 100'000 textures, but not only the use case matters but also the integration and location within the project matters.
So to figure out what's "a very good" way of doing things "for your project", it'd probably best to read more on your own on the topic of different containers.

That's the reason I said "best" and not best. I understand that these things should be project specific, but I was asking for a general idea of STL container speeds. Most games aren't really going to have 100,000 textures, so I was looking for a container that may be "better" than a vector. By "better" I mean one that would balance adding and removing from a non-terminal point and being able to quickly find a value. Vectors are very fast at iterating from the start to end, but removing something in the middle can be heavy. Consider adding are removing instances nearly every step. (Obviously, there are very few times when this is even a good idea, but I know a vector is not the best container for this scenario.) I'm writing the managers to implement the most balanced solution for any generic scenario.

Well if you use pointers then the containers to not matter that much, because the containers will essentially just store the pointers and not the actual data. So look up and deletion will often be very similar.

The STL is built to guarantee high performance with the correct use of the containers, thus up to a certain point it doesn't matter that much which one gets used. Also i most cases you should choose the container by it's use case and not by it's 'performance' (otherwise you'd always have to choose a plain array/std::array). So if you want to use indices for your data, then go with a std::vector. If you want to have key->value matching and it should be ordered the go with std::map, if the order doesn't matter then go with std::unordered_map.  If you run into performance issues caused by your manager(s), then you could reconsider the choice.

I haven't yet had any performance issues and order doesn't matter. However, I haven't really tested with a lot of objects either. The method of looking up the content isn't all that important, I just care mainly on efficiency and being balanced; the look up will be handled the same way for the end user regardless of what container the manager uses.

I really advise you to reconsider that decision and read a bit more about the actual problem with manual memory management (e.g. read this thread fully).
Keep in mind though that shared_ptr might be more appropriate for 'manager' classes, since you most probably will share the resource rather than transfer the ownership (what unique_ptr does).

I don't mind implementing auto pointers, it just doesn't seem necessary. What's wrong with:

Object* Instance = new (std::nothrow) Object;
if (Instance != nullptr) {/*do stuff*/}
else
{/*do error stuff*/}
 

Attachments and other options

[eXpl0it3r]

That's the reason I said "best" and not best. I understand that these things should be project specific, but I was asking for a general idea of STL container speeds. Most games aren't really going to have 100,000 textures, so I was looking for a container that may be "better" than a vector. By "better" I mean one that would balance adding and removing from a non-terminal point and being able to quickly find a value. Vectors are very fast at iterating from the start to end, but removing something in the middle can be heavy. Consider adding are removing instances nearly every step. (Obviously, there are very few times when this is even a good idea, but I know a vector is not the best container for this scenario.)

Okay this gives us a bit more to work with.
Unfortunately this list is missing C++11 containers.
If you want (amortized) constant (O(1)) look up, insertion and deletion then you might want to take a look at std::unordered_map, although it's not guaranteed by the standard (afaik) it will probably mostly get implemented as actual hash table.
std::map on the other hand is often implemented as red-black tree and thus is also quite fast but since things have to get sorted it's 'only' O(log n).
A std::list won't be such a good choice, since the look up, insertion and deletion are in O(n).

For the O-notation see here.
TL;DR: Smaller is better: O(1) < O(log n) < O(n)
And if you got too much time on your hand and are interested in data-structures you can take a look at this.

I'm writing the managers to implement the most balanced solution for any generic scenario.

And there I thought you've understood it.
Stop writing stuff for 'any generic scenario' and start writing code that's needed by your game.
Writing a generic game engine isn't really something you should target and it's something that's very rare in the wild, e.g. first there was Quake then there was the quake engine or first there was Half Life and then there was the source engine, etc.

I don't mind implementing auto pointers, it just doesn't seem necessary. What's wrong with:

Object* Instance = new (std::nothrow) Object;
if (Instance != nullptr) {/*do stuff*/}
else
{/*do error stuff*/}
 

Smart pointers not auto pointers (std::auto_ptr is depreciated).
I'm sure it doesn't cover all the possible failures. Like I said read the linked post or at least take a look at this example.

[Ruckamongus]

Hmm... There are a lot more data structures than I thought! I've been considering using a unordered_map and I think I'll give it a try and see how I like it. (I primarily use GCC and and their implementation does use a hash map, from what I've read.) I'll use the smart pointers I suppose; maybe I'll even grow to like them!

Thanks for the help, eXpl0it3r.

[Rosme]

For a list of containers (with C++11): http://en.cppreference.com/w/cpp/container

[cire]

Vectors are very fast at iterating from the start to end, but removing something in the middle can be heavy. Consider adding are removing instances nearly every step. (Obviously, there are very few times when this is even a good idea, but I know a vector is not the best container for this scenario.)

A vector or deque should be considered the container of choice until you know that you need the qualities of another container.

Removing something from the middle of a vector can be quite cheap if the element is say, a pointer, and the relative order of elements in the vector isn't important.  Just swap it with the back one and erase the end (or resize if you prefer.)  And, you won't find faster insertion/deletion than at the ass-end of  a vector or either end of a deque.

[eXpl0it3r]

A vector or deque should be considered the container of choice until you know that you need the qualities of another container.

Removing something from the middle of a vector can be quite cheap if the element is say, a pointer, and the relative order of elements in the vector isn't important.  Just swap it with the back one and erase the end (or resize if you prefer.)  And, you won't find faster insertion/deletion than at the ass-end of  a vector or either end of a deque.

I can't full agree. Because swapping a to delete mit the back element only works if you're not working with the indices but for managers thos is very likely (you nees to know which resource to return when requested).
So if you can't swap the entries the deletion is essentially O(n) which is slower than the O(1) of a hashtable or the O(log n) of a black-red tree.

[cire]

I can't full agree.

Sure you can.  You noted a possibility that the relative order of elements in the vector may be important...  so did I.

and the relative order of elements in the vector isn't important

The OP was making a blanket statement that deletion from vectors was always expensive, which isn't true.  Considering he was using a vector of pointers, it seemed worth pointing out.

[eXpl0it3r]

I can't full agree.

Sure you can.  You noted a possibility that the relative order of elements in the vector may be important...  so did I.

Me not fully agreeing, does not only related to that part.

and the relative order of elements in the vector isn't important

The OP was making a blanket statement that deletion from vectors was always expensive, which isn't true.  Considering he was using a vector of pointers, it seemed worth pointing out.

But he's right. Because you shouldn't compare deletion of pointer elements to deletion of data elements, but you have to compare deletion of pointer elements in a vector to deletion of pointer elements in another container.
And if you can't use the swapping trick, the deletion of a vector will take O(n) and for others it might only take O(log n) (heap/tree) or even better O(1) (hash table).

What I do agree on is that vectors are in many cases the best choice. The main advantage that a vector has, is that the data is stored in a continuous memory block and thus iterating over it, will make use of the CPU's cache, which is quite a nice accelerator.
So as we see the use cases of a vector are where you store the actual data in the vector (not just the pointers, since this will give you more of a jumping table) and if you have to iterate a lot over it.
Neither of which are the case for the given problem, so if you actually want to point out things independently from the actual topic, you should make this very clear.

[cire]

Because you shouldn't compare deletion of pointer elements to deletion of data elements

It doesn't matter whether they're pointers or not.  The only thing that matters is whether relative order must be preserved (provided objects are copyable/moveable, of course.)

but you have to compare deletion of pointer elements in a vector to deletion of pointer elements in another container.

If I'm speaking about the performance of a vector in a circumstance compared to the performance of a vector in another circumstance, I don't see that the performance of another container is germane.

Neither of which are the case for the given problem, so if you actually want to point out things independently from the actual topic

Wasn't.  The specific remarks I made were tailored specifically to the OP's code in the first post and the following posts (all of which mentioned pointers in some way.) So, in fact, I was pointing out something dependent on the actual topic and posts therein.

I'm just a little bit confused why when I say "If A, then B" you have to come back and say "But A is not a given." If.

At any rate, I don't feel like discussing this further is likely to be productive, so there will be no further discussion from me on this subject.

[Nexus]

Ruckamongus, you should specify which operations you exactly need, and how often you need them. Otherwise you get always these generic "there is no best, it depends on circumstances" answers.

Do you access all objects via integral indices? If so, what have you done until now when an object of a std::vector has been removed?