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?
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
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 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.