doubt with map
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?
| 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.
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.
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.