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!
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 (http://en.sfml-dev.org/forums/index.php?topic=9359.0) 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
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 (http://www.cplusplus.com/reference/stl/) 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 (https://en.wikipedia.org/wiki/Hash_table).
std::map on the other hand is often implemented as red-black tree (https://en.wikipedia.org/wiki/Red%E2%80%93black_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 (https://en.wikipedia.org/wiki/Big_O_notation).
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 (https://en.wikipedia.org/wiki/List_of_data_structures). :D
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 (http://en.sfml-dev.org/forums/index.php?topic=9359.msg63566#msg63566).