c++dictionarycontainersstdmapmax-size

How is the std::map::max_size() return calculated?


I have the following map:

std::map<int, std::string> map;

and my output when i call:

std::cout << map.max_size() << std::endl;

is 128102389400760775 on my linux system(wsl2). I am searching for an alternative way to reach this result without std::numerical_limits.

So far i came up with the following wrong approach, which worked for vector:

std::map<int, std::string>::allocator_type a_type_map;
std::cout << a_type_map.max_size() << std::endl;

Probably it has something to do with the Nodes, which take additional storage or something.


Solution

  • I could not find anywhere in the C++ standard a statement that affirms clearly how max_size() can be calculated.

    On GCC/libstdc++ implementation, max_size is defined on include/bits/stl_map.h as

          /** Returns the maximum size of the %map.  */
          size_type
          max_size() const _GLIBCXX_NOEXCEPT
          { return _M_t.max_size(); }
    

    where _M_t is of type std::_Rb_tree and defines max_size() in include/bits/stl_tree.h as

          size_type
          max_size() const _GLIBCXX_NOEXCEPT
          { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
    

    So this says this limit is basically the maximum number of elements that the allocator itself can create.

    The _Alloc_traits::max_size is defined in include/bits/alloc_traits.h as

        typedef std::allocator_traits<_Alloc> _Base_type;
        ...
        using _Base_type::max_size;
    

    Of course the allocator is whatever you use in your container but the default implementation boils down to include/ext/new_allocator.h:

    size_type max_size() const
    {
        return size_t(__PTRDIFF_MAX__) / sizeof(_Tp);
    }
    

    The above was cleaned up a bit for macros etc.

    Type type _Tp is defined as std::_Rb_tree_node<std::pair<int const, int> >, which is basically

    struct _Rb_tree_node {
        struct __aligned_membuf<std::pair<const int, int> > _M_storage;
        ...
        // from _Rb_tree_node_base 
        _Rb_tree_color  _M_color;
        _Base_ptr       _M_parent;
        _Base_ptr       _M_left;
        _Base_ptr       _M_right;
    };
    

    So for std::map<int32_t,int32_t> that will be 40 bytes - 3 pointers at 8 bytes plus 4 bytes color plus 4 bytes padding plus 8 bytes of the std::pair.

    which means this is the theoretical maximum possible you can ever have regardless of amount of memory or any other limiting factors.

    Godbolt test: https://godbolt.org/z/vME5qvTGP