CODEWITHSUNDEEP
c++dictionarystlstdmapspace-complexity
Harini Sj
Harini Sj

Reputation: 183

Analysing std::map - Why is using a map /hashset/hastable considered bad to use due to space complexity?

I have always heard that it is better to avoid using hash table/maps since they have large space complexity. How is the space complexity of maps different from that of a vector or an array of N elements? What would be an alternative to using a map? Would it be equally bad to use a map or a vector in terms of space complexity when number of elements is large? Why?

Upvotes: 0

Views: 50

Answers (1)

UweJ
UweJ

Reputation: 489

The guideline to prefer vector or array bases on the assumption, that the amount of items in a map is mostly very small (few KB). Using a map, the key has to be stored additionally. Then a verctor is smaller in memory and therfore more heap friendly. Using the heap memory efficiently can decrease the runtime a lot.

Reference: https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#slcon2-prefer-using-stl-vector-by-default-unless-you-have-a-reason-to-use-a-different-container

You also have to keep in mind the rules of the O-Natation. We only considere large large N-values. E.g. the term O(30N) is reduced to O(N). The 30 can be neglected for large large N-values. But if you use low N-values, than the "real" complexity is more important than the convergence-value.

Upvotes: 1

Related Questions