I am writing some UI stuff for my games in C++. Basically its a very common problem, but I dont know the best answer yet. Suppose inside my UI Library I have a view class which renders 2D/3D scene. This view can contain many subviews. I needs a container which allows me to iterate over these views fast and also insert/delete subviews. I am not sure which container is best for the job - list, vector or something else?
\$\begingroup\$
\$\endgroup\$
2
-
\$\begingroup\$ This is more suited to SO. \$\endgroup\$– PrettyPrincessKitty FSCommented Jun 26, 2011 at 9:29
-
\$\begingroup\$ @The Communist Duck - Yes, I thought of putting this question to StackOverflow rather then here, but I made this choice as I might get some feedback based on my particular case of games. Choosing containers always depends on what kind of thing you are trying to achieve. In case of games, I thought I might get a better answer considering a GUI views might be heavy as they contain texture data etc, I believe person answering my question would make this assumption and answer me accordingly. \$\endgroup\$– VijayendraCommented Jun 26, 2011 at 10:19
Add a comment
|
3 Answers
\$\begingroup\$
\$\endgroup\$
2
Chances are you'll be iterating over your collection a lot more than inserting/deleting screens, so vector is probably the best choice. Sure, inserting and removing things from the middle of vectors is "slow" if you just look at "Big O", but in practice it's actually really fast simply because your elements are contiguous in memory. It's highly unlikely that you have so many screens that it becomes an issue.
Then again if you ask me I'll say never use list unless there's a really, really good reason to and benchmarks show that it's faster for that particular use case.
I'll point to my answer in the when should vector/list be used question to go into more detail.
Also, if you end up using map, make sure your keys are something that's fast to compare (i.e. not strings). If you must use string keys, use a hash map like unordered_map.
-
\$\begingroup\$ The
vectorclass also becomes slow when resizing (adding more elements than max_size), because the max-size is changed and everything is copied to a new address in memory. You canreservemore memory though, if you know you will have a certain amount of elements in you GUI, in which case you have the advantages of a normal array. \$\endgroup\$ Commented Jun 26, 2011 at 12:53 -
2\$\begingroup\$ @3nixios: On the other hand adding elements to a std::list is also slow because each new element will generally trigger a new allocation, and the cost of allocation will totally dominate the cost of a copy for reasonable sizes and PODs. Really, it's all in the question Tetrad linked \$\endgroup\$– user744Commented Jun 26, 2011 at 13:33
\$\begingroup\$
\$\endgroup\$
Vector is a great choice- very fast iteration. You'd need an extremely high amount of Scenes to make inserting one, even at the beginning, to be slow for a vector. This is especially true if you're storing pointers rather than values.
\$\begingroup\$
\$\endgroup\$
List is probably a good choice here. A linked list is fast to delete and insert elements into the middle, the front, and the end. You can iterate over it, but you cannot do random access (i.e. myList[3] for the 4th element).
Arrays could be good if you have a fixed number of GUI subviews.
Vector is less of a good choice. It's implemented as a resizable array, so deletion/insertion anyway except the back of the vector requires shifting the elements along. You can iterate over it just as easily, and you have random access if you need it. For a GUI, I doubt you will.
The other option is Map. This is almost certainly not a good idea unless you need to store them by keys.
answered Jun 26, 2011 at 9:32