Comment Re:About maps... (Score 1) 1046
You are confusing things.
Time bounds on hash tables are even better than maps. It's constant time lookup. You don't even have to amortize to get the constant time. It's really constant, each and every time.
Where you do have to amortize is when you decide to resize the table. But, with amortization, hash tables are still constant time insert and lookup.
So, why are sorted containers implemented with red-black trees? Because they are sorted. Hash tables have no notion of relative order. Your item is there, or it's not. It is quite difficult to find the next higher or lower item. When you want efficient, but sorted data, you need a tree datastructure of some sort.
Michael
Time bounds on hash tables are even better than maps. It's constant time lookup. You don't even have to amortize to get the constant time. It's really constant, each and every time.
Where you do have to amortize is when you decide to resize the table. But, with amortization, hash tables are still constant time insert and lookup.
So, why are sorted containers implemented with red-black trees? Because they are sorted. Hash tables have no notion of relative order. Your item is there, or it's not. It is quite difficult to find the next higher or lower item. When you want efficient, but sorted data, you need a tree datastructure of some sort.
Michael
