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.

Log in to reply