Memory allocation of internal types used by the containers

Question

C++11 standard has following lines in General Container Requirements.

(23.2.1 - 3)

For the components affected by this subclause that declare an allocator_type, objects stored in these components shall be constructed using the allocator_traits::construct function and destroyed using the allocator_traits::destroy function (20.6.8.2). These functions are called only for the container’s element type, not for internal types used by the container

(23.2.1 - 7)

Unless otherwise specified, all containers defined in this clause obtain memory using an allocator

Is it true or not, that all memory used by container is allocated by specified allocator? Because standard says that internal types are constructed not with allocator_traits::construct, so there should be some kind of call to operator new. But standard also says that all containers defined in this clause obtain memory using an allocator, which in my opinion means that it can't be ordinary new operator, it has to be placement new operator. Am I correct?

Let me show you example, why this is important.

Let's say we have a class, which holds some allocated memory:

#include <unordered_map>
#include <iostream>
#include <cstdint>
#include <limits>
#include <memory>
#include <new>

class Arena
{
public:
        Arena(std::size_t size)
        {
                size_     = size;
                location_ = 0;

                data_ = nullptr;
                if(size_ > 0)
                        data_ = new(std::nothrow) uint8_t[size_];
        }
        Arena(const Arena& other) = delete;
        ~Arena()
        {
                if(data_ != nullptr)
                        delete[] data_;
        }
        Arena& operator =(const Arena& arena) = delete;

        uint8_t* allocate(std::size_t size)
        {
                if(data_ == nullptr)
                        throw std::bad_alloc();

                if((location_ + size) >= size_)
                        throw std::bad_alloc();

                uint8_t* result = &data_[location_];
                location_ += size;
                return result;
        }

        void clear()
        {
                location_ = 0;
        }

        std::size_t getNumBytesUsed() const
        {
                return location_;
        }

private:
        uint8_t* data_;
        std::size_t location_, size_;

};

we also have custom allocator:

template <class T> class FastAllocator
{
public:
        typedef T value_type;

        typedef T*       pointer;
        typedef const T* const_pointer;

        typedef T&       reference;
        typedef const T& const_reference;

        typedef std::size_t    size_type;
        typedef std::ptrdiff_t difference_type;

        template <class U> class rebind
        {
        public:
                typedef FastAllocator<U> other;

        };

        Arena* arena;

        FastAllocator(Arena& arena_): arena(&arena_) {}
        FastAllocator(const FastAllocator& other): arena(other.arena) {}
        template <class U> FastAllocator(const FastAllocator<U>& other): arena(other.arena) {}

        //------------------------------------------------------------------------------------
        pointer allocate(size_type n, std::allocator<void>::const_pointer)
        {
                return allocate(n);
        }
        pointer allocate(size_type n)
        {
                return reinterpret_cast<pointer>(arena->allocate(n * sizeof(T)));
        }

        //------------------------------------------------------------------------------------
        void deallocate(pointer, size_type) {}

        //------------------------------------------------------------------------------------
        size_type max_size() const
        {
                return std::numeric_limits<size_type>::max();
        }

        //------------------------------------------------------------------------------------
        void construct(pointer p, const_reference val)
        {
                ::new(static_cast<void*>(p)) T(val);
        }
        template <class U> void destroy(U* p)
        {
                p->~U();
        }

};

This is how we use it:

typedef std::unordered_map<uint32_t, uint32_t, std::hash<uint32_t>, std::equal_to<uint32_t>,
                           FastAllocator<std::pair<uint32_t, uint32_t>>> FastUnorderedMap;

int main()
{
        // Allocate memory in arena
        Arena arena(1024 * 1024 * 50);
        FastAllocator<uint32_t> allocator(arena);
        FastAllocator<std::pair<uint32_t, uint32_t>> pairAllocator(arena);
        FastAllocator<FastUnorderedMap> unorderedMapAllocator(arena);

        FastUnorderedMap* fastUnorderedMap = nullptr;

        try
        {
                // allocate memory for unordered map
                fastUnorderedMap = unorderedMapAllocator.allocate(1);

                // construct unordered map
                fastUnorderedMap =
                        new(reinterpret_cast<void*>(fastUnorderedMap)) FastUnorderedMap
                        (
                                0,
                                std::hash<uint32_t>(),
                                std::equal_to<uint32_t>(),
                                pairAllocator
                        );

                // insert something
                for(uint32_t i = 0; i < 1000000; ++i)
                        fastUnorderedMap->insert(std::make_pair(i, i));
        }
        catch(std::bad_alloc badAlloc)
        {
                std::cout << "--- BAD ALLOC HAPPENED DURING FAST UNORDERED MAP INSERTION ---" << std::endl;
        }

        // no destructor of unordered map is called!!!!
        return 0;
}

As you can see, destructor of unordered_map is never called, but memory is freed during destruction of arena object. Will there be any memory leak and why?

I would really appreciate any help on this topic.

Answer 1

An allocator is supposed to provide 4 functions (of interest here):

• 2 are used for memory management: allocate/deallocate
• 2 are used for objects lifetime management: construct/destroy

The these functions in your quote only apply to construct and destroy (which were mentioned in the previous sentence), and not to allocate/deallocate, thus there is no contradiction.

Now, regarding memory leaks, for an arena allocator to work not only should the objects in the container be built using the arena allocator (which the container guarantees) but all the memory those objects allocate should also be obtained from this allocator; this can get slightly more complicated unfortunately.