Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 4 down vote favorite
1

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?

share|improve this question
This is more suited to SO. – The Communist Duck Jun 26 '11 at 9:29
@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. – Vijayendra Tripathi Jun 26 '11 at 10:19

3 Answers

up vote 12 down vote accepted

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.

share|improve this answer
The vector class 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 can reserve more 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. – Jonathan Connell Jun 26 '11 at 12:53
2  
@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 – Joe Wreschnig Jun 26 '11 at 13:33
Thanks for the explanation and the link. – Vijayendra Tripathi Jun 26 '11 at 14:17
up vote 1 down vote

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.

share|improve this answer
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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