How I can write a monotonic allocator in C++?

Question

I'm trying to write a very simple monotonic allocator that uses a fixed total memory size. Here is my code:

#include <map>
#include <array>

template <typename T, size_t SZ>
class monotonic_allocator
{
public:
    using value_type = T;

    monotonic_allocator() noexcept {} 

    [[nodiscard]]
    value_type* allocate(std::size_t n)
    {
        size_t start = 0;
        for (const auto& [alloc_start, alloc_size] : alloc_list_) {
            if ((alloc_start - start) <= n) {
                alloc_list_[start] = n;
                return mem_.data() + start;
            }

            start = alloc_start + alloc_size;
        }

        throw std::bad_alloc{};
    }

    void deallocate(value_type* p, std::size_t n) noexcept
    {
        alloc_list_.erase(static_cast<size_t>(p - mem_.data()));
    }

    template <typename T1, size_t SZ1, typename T2, size_t SZ2>
    friend bool operator==(monotonic_allocator<T1, SZ1> const& x, monotonic_allocator<T2, SZ2> const& y) noexcept;

private:
    std::array<value_type, SZ> mem_;
    std::map<size_t, size_t> alloc_list_{};
};

template <typename T1, size_t SZ1, typename T2, size_t SZ2>
bool operator==(monotonic_allocator<T1, SZ1> const& x, monotonic_allocator<T2, SZ2> const& y) noexcept
{
    return SZ1 == SZ2 && x.mem_.data() == y.mem_.data();
}

template <typename T1, size_t SZ1, typename T2, size_t SZ2>
bool operator!=(monotonic_allocator<T1, SZ1> const& x, monotonic_allocator<T2, SZ2> const& y) noexcept
{
    return !(x == y);
}

int main()
{
    std::vector<int, monotonic_allocator<int, 4096>> vec = {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,6};
}

But I get a strange error which says:

error: no type named 'type' in 'std::__allocator_traits_base::__rebind<monotonic_allocator<int, 4096>, int>'

Any idea how I can solve this problem? BTW, this code may have other problems too.

Answer 1

According to cppreference, rebind (which is part of the Allocator requirements) is only optional if your allocator is a template of the form <typename T, [possibly other type arguments]>. But your template is of the form <typename T, size_t N>, so it doesn't match (the size_t argument is a non-type argument).

So you have to add the rebind implementation yourself, like in the example in this question: How are allocator in C++ implemented?