Agree with your point about lists being linear so shorter ones being quicker to search than long ones Eglin. I was meaning that the pre-search code for list allocation becomes more significant in the total time. i.e. pre-search list allocation time makes things slower, especially when you have a large number of shorter lists. Conversely the pre-search time tends to be absorbed more into a lower number of 'longer list' searches.
That's the point I was trying to make, that a balance is needed - the ultimate step is to have n lists of length 1 where the id is a one to one allocator for the list holding the single element. I didn't express myself at all well though. (and still aren't sure that I have LOL)
Not a big issue really, I agree with you basically just didn't want you thinking I didn't know it takes longer to search a linked list of 1000 things than 10 things.
I'm sorta confused as to why a hashtable or any other kind of structure not being a standard container at this point should be a problem. Its nice if there is a standard implementation of some structure but there is nothing wrong with creating your own. As long as you do it in a disciplined way the cross-platform element isn't an issue.
That said, I absolutely agree your time is better spent elsewhere though - from experience its only worth messing with something this central if you have an explicit problem. Just noticed that nobody had addressed trumpcard's original question so thought I'd throw some thoughts in for what its worth
Anyway back to working through the code for me so I can discuss the issues a bit more intelligently.