CODEWITHSUNDEEP
c++dictionary
user11376749
user11376749

Reputation:

what is the space complexity of std::map in c++?

suppose I used a map data structure from std::map (c++) of N elements which is like the following:

map<int,bool>m;

what is the space complexity here(for N elements)? is it just 

O(N*(sizeof(int)+sizeof(bool)))

or something else adds up which I am missing?

Upvotes: 0

Views: 1966

Answers (1)

eerorika
eerorika

Reputation: 238311

what is the space complexity of std::map in c++?

The standard does not mandate spatial complexity of container implementations.

But in practice, the asymptotic space complexity (in number of bytes allocated) is O(N) for all standard containers in reasonable implementations.

Upvotes: 1

Related Questions