#include <functional>
#include <memory>
#include <vector>
#include <iostream>
#include <cassert>
 
 template <class T, std::size_t N, class Allocator = std::allocator<T>>
 class stack_allocator
 {
 	public:
 
 	typedef typename std::allocator_traits<Allocator>::value_type value_type;
 	typedef typename std::allocator_traits<Allocator>::pointer pointer;
 	typedef typename std::allocator_traits<Allocator>::const_pointer const_pointer;
 	typedef typename Allocator::reference reference;
 	typedef typename Allocator::const_reference const_reference;
 	typedef typename std::allocator_traits<Allocator>::size_type size_type;
 	typedef typename std::allocator_traits<Allocator>::difference_type difference_type;
 
 	typedef typename std::allocator_traits<Allocator>::const_void_pointer const_void_pointer;
 	typedef Allocator allocator_type;
 	
 	public:
 
 	explicit stack_allocator(const allocator_type& alloc = allocator_type()) 
 		: m_allocator(alloc), m_begin(nullptr), m_end(nullptr), m_stack_pointer(nullptr)
 	{ }
 
 	explicit stack_allocator(pointer buffer, const allocator_type& alloc = allocator_type())
 		: m_allocator(alloc), m_begin(buffer), m_end(buffer + N), 
 			m_stack_pointer(buffer)
 	{ }
 
 	template <class U>
 	stack_allocator(const stack_allocator<U, N, Allocator>& other)
 		: m_allocator(other.m_allocator), m_begin(other.m_begin), m_end(other.m_end),
 			m_stack_pointer(other.m_stack_pointer)
 	{ }
 
 	constexpr static size_type capacity()
 	{
 		return N;
 	}
 
 	pointer allocate(size_type n, const_void_pointer hint = const_void_pointer())
 	{
 		if (n <= std::distance(m_stack_pointer, m_end))
 		{
 			pointer result = m_stack_pointer;
 			m_stack_pointer += n;
 			return result;
 		}
 
 		return m_allocator.allocate(n, hint);
 	}
 
 	void deallocate(value_type* p, size_type n)
 	{
 		if (pointer_to_internal_buffer(p))
 		{
 			m_stack_pointer -= n;
 		}
 		else m_allocator.deallocate(p, n);	
 	}
 
 	size_type max_size() const noexcept
 	{
 		return m_allocator.max_size();
 	}
 
 	template <class U, class... Args>
 	void construct(U* p, Args&&... args)
 	{
 		m_allocator.construct(p, std::forward<Args>(args)...);
 	}
 
 	template <class U>
 	void destroy(U* p)
 	{
 		m_allocator.destroy(p);
 	}
 
 	pointer address(reference x) const
 	{
 		if (pointer_to_internal_buffer(std::addressof(x)))
 		{
 			return std::addressof(x);
 		}
 
 		return m_allocator.address(x);
 	}
 	
 	const_pointer address(const_reference x) const
 	{
 		if (pointer_to_internal_buffer(std::addressof(x)))
 		{
 			return std::addressof(x);
 		}
 
 		return m_allocator.address(x);
 	}
 
 	template <class U>
 	struct rebind { typedef stack_allocator<U, N, allocator_type> other; };
 
 	pointer buffer() const noexcept
 	{
 		return m_begin;
 	}
 
 	private:
 
 	template <class U>
 	bool pointer_to_internal_buffer(U* p) const
 	{
 		return (!(std::less<T*>()(p, m_begin)) && (std::less<T*>()(p, m_end)));
 	}
 
 	pointer m_begin;
 	pointer m_end;
 	pointer m_stack_pointer;
 	allocator_type m_allocator;
 };
 
 template <class T1, std::size_t N, class Allocator, class T2>
 bool operator == (const stack_allocator<T1, N, Allocator>& lhs, 
 	const stack_allocator<T2, N, Allocator>& rhs) noexcept
 {
 	return lhs.buffer() == rhs.buffer();
 }
 
 template <class T1, std::size_t N, class Allocator, class T2>
 bool operator != (const stack_allocator<T1, N, Allocator>& lhs, 
 	const stack_allocator<T2, N, Allocator>& rhs) noexcept
 {
 	return !(lhs == rhs);
 }

int main()
{

    const static std::size_t stack_size = 4;
    int buffer[stack_size];
    
    typedef stack_allocator<int, stack_size> allocator_type;
    
    std::vector<int, allocator_type> vec((allocator_type(buffer))); // double parenthesis here for "most vexing parse" nonsense
    vec.reserve(stack_size); // attempt to reserve space for 4 elements
    
    std::cout << vec.capacity() << std::endl;
    
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    
    // Assert that the vector is actually using our stack
    //
    assert(
    	std::equal(
    		vec.begin(), 
    		vec.end(), 
    		buffer, 
    		[](const int& v1, const int& v2) {
    			return &v1 == &v2;
    		}
    	)
    );
    
    // Output some values in the stack, we see it is the same values we
    // inserted in our vector.
    //
    std::cout << buffer[0] << std::endl;
    std::cout << buffer[1] << std::endl;
    std::cout << buffer[2] << std::endl;
    std::cout << buffer[3] << std::endl;

    // Attempt to push back some more values.  Since our stack allocator only has 
	 // room for 4 elements, we cannot satisfy the request for an 8 element buffer.  
	 // So, the allocator quietly falls back on using std::allocator.
    //
    // Alternatively, you could modify the stack_allocator implementation
    // to throw std::bad_alloc
    //
    vec.push_back(50);
    vec.push_back(60);
    vec.push_back(70);
    vec.push_back(80);
    
    // Assert that we are no longer using the stack buffer
    //
    assert(
    	!std::equal(
    		vec.begin(), 
    		vec.end(), 
    		buffer, 
    		[](const int& v1, const int& v2) {
    			return &v1 == &v2;
    		}
    	)
    );
    
    // Print out all the values in our vector just to make sure 
    // everything is sane.
    //
    for (auto v : vec) std::cout << v << ", ";
    std::cout << std::endl;
}