Why do std::set and set::map's default constructors require heap allocation?

Question

When I try this:

#include <functional>
#include <iostream>
#include <memory>
#include <set>

template<class T>
struct MyAlloc
{
    typedef std::allocator<T> Base;
    typedef typename Base::value_type value_type;
    typedef typename Base::pointer pointer;
    typedef typename Base::const_pointer const_pointer;
    typedef typename Base::reference reference;
    typedef typename Base::const_reference const_reference;
    typedef typename Base::size_type size_type;
    typedef typename Base::difference_type difference_type;
    Base a;
    MyAlloc() { }
    template<class U> MyAlloc(MyAlloc<U> const &) { }
    template<class U> struct rebind { typedef MyAlloc<U> other; };
    pointer allocate(size_type n, void const * = NULL)
    {
        std::cout << "Allocating " << n << " objects" << std::endl;
        return this->a.allocate(n);
    }
    void deallocate(pointer p, size_type n) { return this->a.deallocate(p, n); }
};

int main(int argc, char *argv[])
{
    std::set<int, std::less<int>, MyAlloc<int> > set;
}

I see Allocating 1 objects.

But I don't understand -- why is this heap allocation necessary? Stack memory is sufficient for default-constructing other containers (like std::vector), so why do set and map require heap allocation?

Answer 1

I think I figured it out myself. Visual C++ seems to be correct, and Clang and GCC seem to be wrong.

It's because swap should not invalidate iterators for std::set or std::map. If we try this code:

#include <set>
#include <iostream>
int main()
{
    std::set<int> a, b;
    std::set<int>::iterator end = a.end();
    a.swap(b);
    b.insert(end, 1);
    std::cout << b.size() << std::endl;
    return 0;
}

If the head of the tree was stored on the stack, then end would become invalidated after the swap.

Visual C++ handles it just fine, but GCC and Clang loop infinitely (at least on my versions).

Edit: The above may have been the reason until C++03 due to an ambiguity, but it is no longer the case since C++11 -- please see the comments below.

Answer 2

The C++ standard certainly doesn't mandate that memory is allocated for a default constructed object. Why an implementation might choose to allocate in the default constructor of a std::map<...> I don't know. One reason could be to make sure that it doesn't try to embed a potentially large allocator into the stack allocated object. You'd need to look at the implementation to see why it allocates memory on the heap.