Hi guys, I don't know if this is the right place to ask questions about STL. It seemed like a pretty basic problem so here I go. I'll write-up what I'm doing with this question so everyone will have a better view. Those who don't have the time to read through, just skip to the last line.

Right now I'm writing a simple rendering system for UI. The idea I had is to render all the UI I need within an std::list, let's call it 'RenderList'. As you probably figured out, whatever I add first, will be the back-most object on the screen etc. Anyway I'll get straight to the point:

Problem: What if I require to insert an object in the middle of RenderList. I have to actually iterate through everything to find the UI that I want it placed after and from there I use the std::list::insert function.

So the real problem I'm seeing now is that I am afraid that this 'inserting' process might recur very often during my game and thus I am concerned about the iterating and inserting speed of std::list. My friend told me that std::map is faster, but I didn't really like the idea of having an external string to identify my objects.

Furthermore, after some googling, I found this: http://www.velocityreviews.com/forums/t710288-map-vs-list-performance.html which states that map.find is slower than iterating through a list. But it's only one solitary source and I'm afraid to rely on it.

So bottom line: Is std::map::find/insert faster than iterating through std::list to insert an object? If so, how much faster/slow is it?

Thanks in advance,
Faylar.

My advice would be to implement it in the simple manner first (list i guess?), then go back and change it as necessary. I say this because it seems very vague how you intend to insert and read from this container, so making a choice on your data structure is impossible at this stage.

With regards to that link: in theory map should be faster. He doesn't post all of his code but perhaps his test harness was poorly set up and the linked list solution was in a best case scenario. Someone posted code later in the thread that refutes the OP's conclusion.

I've done the "list and linear search" thing before... for anything that has a decent amount of elements it can be prohibitively slow. Also, using a std::string as your key makes me cringe. Use an "int" if you can.

Maps are sorted by their keys. The iterator you pass to map::insert is only a "suggestion" telling it where to start searching for the correct insertion point. You probably want to use a list. Speed won't be an issue unless you plan to do thousands of insertions per second.

Quote:Original post by faylar
As you probably figured out, whatever I add first, will be the back-most object on the screen etc. My friend told me that std::map is faster, but I didn't really like the idea of having an external string to identify my objects.

If you were to use std::map, the key would not necessarily be a string, and it would not be "to identify the objects", but to indicate the Z-order position. The map can only impose one ordering. If it's alphabetical by name, it can't also be back-to-front (except by coincidence).

Quote:which states that map.find is slower than iterating through a list.

If you used a map, you would not be using .find() when you draw everything; you would iterate through the map to draw everything. If you wanted to find a specific element, you would use .find() on the map and iterate through (you could call std::find, but it would also iterate through; even if you sorted the list and used std::binary_search, it would be O(n) ) the list, which is slower than map.find() (assuming a decently large number of elements).

But why would you need to find a specific element?

The kinds of questions you are trying to ask simply cannot be answered without a clearer picture of your requirements.

Thanks for the replies everyone!

For the map::find, it is so that I can make an object render right after a certain object. So let's say hey, now I want this button to appear so I'm going to insert it in the list between Button X and Button Y. With map, I would just grab the iterator using map::find(whatever the ID Button X is) and map::insert right after it.

I could do the same with lists. So I guess the real question is, map::find vs iterating a list for an object with the right ID.

For now I'm just going to stick to list if given the choice. Using map could mean that I have to handle an ID that's outside the UI object, so it's kinda hard when I really want to use the ID for something since it's not within the UI itself. I COULD duplicate the ID of the map and have it within the UI itself, but it seems a bit messy and unnecessary.

Also, thanks for point out the string thing. I can't believe I didn't think about that. Enum/int/short could've been alot better.

I would personally use a child/sibling based hierarchy and just recursively traverse it from the root, drawing components as they are encountered.


By making components positions relative to their parents, things get alot more flexible and elegant.

A nice example would be a panel containing another panel containing a button.

Move panel, everything else tags along.
Move another panel, only it and its button move.


Recursion might not be that "fast" an approach, but it can be made iterative with little work if needed.

Quote:Original post by faylarSo let's say hey, now I want this button to appear so I'm going to insert it in the list between Button X and Button Y. With map, I would just grab the iterator using map::find(whatever the ID Button X is) and map::insert right after it.

std::map entries are sorted from lower to higher key. So if you got a button "4" and "8" and insert "5", the order will be 4, 5, 8, no matter where you try to insert it. So there's no point in using "find" before inserting.

If this is for a GUI where you also want to track which element is under the mouse cursor, it's probably a good idea to keep your controls in a quadtree or use spatial hashing (which can be done with the map).

Quote:Original post by faylar
With map, I would just grab the iterator using map::find(whatever the ID Button X is) and map::insert right after it.

No. That's what we've been trying to tell you.

You cannot control the order of elements inside a std::map, except by changing the keys. It doesn't matter that there's a version of .insert() that takes an iterator parameter. It doesn't do what you're expecting it to do.

Quote:You cannot control the order of elements inside a std::map, except by changing the keys. It doesn't matter that there's a version of .insert() that takes an iterator parameter. It doesn't do what you're expecting it to do.

Hmm, thanks for the heads up. I didn't really catch it. I was wondering why everyone was saying "you wouldn't use std::find" and i keep thinking that map is just a list with keys. Sorry, mind wasn't really working yesterday without sleep.

@rmed002: Used to do that. I was thinking if this method is better/cleaner.