CODEWITHSUNDEEP
c++
Simon
Simon

Reputation: 11

What is the big O memory usage of maps in C++?

I'm wondering what the big O memory usage of maps in C++ (like how arrays use O(n) memory). In the C++ documentation, it says

Constant for the empty constructors (1), and for the move constructors (4) (unless alloc is different from x's allocator). For all other cases, linear in the distance between the iterators (copy constructions) if the elements are already sorted according to the same criterion. For unsorted sequences, linearithmic (N*logN) in that distance (sorting,copy constructions).

but I'm having a hard time understanding what this means. Does this mean that maps use O(n*log(n)) memory? Thanks for your help!

Upvotes: 0

Views: 325

Answers (1)

prehistoricpenguin
prehistoricpenguin

Reputation: 6326

There are N nodes, so the memory usage is O(N).

For accuracy, its' N * sizeof(std::map<KeyType, ValueType>::node_type), and may plus one more node for the sentinel root node. Note that node_type is added since c++17.

node_type is larger than value_type, since it contains value_type and some more info(red-black tree colors and left-right child pointers for most implementations)

For the size comparison:

    std::cout << sizeof(std::map<int, int>::value_type) << std::endl;
    std::cout << sizeof(std::map<int, int>::node_type) << std::endl;

We may get 8 and 24. So map costs several times more memory than a vector of pairs, especially for small data types like int. Though they both have O(N) space complexity.

Maps are good, then how to save memory for small maps(And may also improve the performance since we may reduce the calling for memory allocation)? There are some existed solutions, we use a vector based map:

Boost.Container flat_[multi]map/set containers are ordered-vector based associative containers based on Austern's and Alexandrescu's guidelines. These ordered vector containers have also benefited recently with the addition of move semantics to C++, speeding up insertion and erasure times considerably. Flat associative containers have the following attributes

Upvotes: 3

Related Questions