C++ Map



  • Why is the time complexity of insertion and deletion for unordered_map is less than that of ordered maps in C++?


  • Mod

    Because you can save time by not having to preserve order. In more detail: In unordered_map you can directly compute where an element should be, and that result does not depend on the other elements in the map¹. In an ordered_map you have to search for the place where an element should be, and that place depends on the other elements in the map.

    ¹: Except when you have a collision. In this case, the time complexity of an unordered_map can become worse than the ordered case.



  • It is because unordered maps are implemented using hashing techniques while our ordered maps are based on self balancing trees which has a insertion and deletion time complexity of O(logn) while in hashing it is O(1) here they have discussed much more in detail comparison between maps and unordered maps.