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

Question

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.

Answer 1

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