please wait
doubt with map
Jun 19, 2012 at 7:04pm
They say the <key, value> pair in map are stored in a sorted order, hence we need to give an valid comparison operator on keys while creating the map.But then, wont the insertion be O(log n), defeating the purpose of using map?
Jun 19, 2012 at 7:18pm| defeating the purpose of using map? |
The fact that insertion is only O(log n) is one of the reasons why one might decide to use a map (the real reason is usually that you want to map stuff to other stuff), not the other way round. If you don't need the elements to be sorted, you can use unordered_map.
Jun 19, 2012 at 7:36pm
If you want linear insertions with a key you can use a hash table, the only problem here is that you usually need to allocate more space for the table than you actually use. It's a memory vs speed trade-off situation. Also, a good hash function is hard to write.
Jun 19, 2012 at 8:17pm
yes,
The purpose of using hash is to have insertion O(1), and retrieval too. So, with this stl map, we are not achieving that, right?
The purpose of using hash is to have insertion O(1), and retrieval too. So, with this stl map, we are not achieving that, right?
Topic archived. No new replies allowed.