#include <iostream>
#include <memory>
#include <vector>
#include <cstdlib>
#include <list>
#include <ctime>

const std::size_t block_size = 1 << 11;
using std::vector;

class Block;

class SharedAllocator {
private:
	Block* LastBlock;
public:
	SharedAllocator() {
		LastBlock = nullptr;
	}

	~SharedAllocator() {
		delete LastBlock;
	}

	template <typename T>
	T* allocate(std::size_t n) {
		if (LastBlock == nullptr) {
			Block* b = new Block(n * sizeof(T));
			LastBlock = b;
			return reinterpret_cast<T*>(LastBlock->allocate(n * sizeof(T)));
		} else if (LastBlock->unused_memory  n * sizeof(T)) {
			Block* b = new Block(n * sizeof(T));
			blocks.push_back(b);
			return reinterpret_cast<T*>(blocks.back()->allocate(n * sizeof(T)));
		} else {
			return reinterpret_cast<T*>(blocks.back()->allocate(n * sizeof(T)));
		}
	}

	void deallocate() {
		return;
	}
};


template <typename T>
class StackAllocator : public std::allocator<T> {
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 > struct rebind { typedef StackAllocator<U> other; };

    StackAllocator(): m_allocator(std::make_shared<SharedAllocator>()) {
	}


    template<class U>
    StackAllocator(const StackAllocator<U>& other) {
        m_allocator = other.m_allocator;
    }

    ~StackAllocator() {

    }

    pointer allocate(size_type n, const_pointer hint = 0) {
        return m_allocator->allocate<T>(n);
    }

    void deallocate(pointer p, size_type n) {
        return;
    }

    std::shared_ptr<SharedAllocator> m_allocator;
};

class Block {
public:
	typedef char* pointer;
    typedef std::size_t size_type;
	friend class SharedAllocator;
    Block(const size_type n) {
        unused_memory = n;
		used_memory = 0;
		current_memory_pointer = reinterpret_cast<char*>(std::malloc(n));
    }

	~Block() {
		std::free(current_memory_pointer);
	}

    pointer get_current_place() {
		return current_memory_pointer + used_memory;
	}

	char* allocate(size_type n) {
		pointer p = get_current_place();
		unused_memory -= n;
		used_memory += n;
		return p;
	}

	void deallocate(size_type n) {
		return;
	}

private:
	pointer current_memory_pointer;
    size_type unused_memory;
	size_type used_memory;
	Block* previous;
};

int main() {
	std::list<int, StackAllocator<int>> l;

	clock_t t1, t2;
	t1 = clock();
	for (int i = 0; i < 1000000; ++i) {
		l.push_back(1);
	}
	t1 = clock() - t1;
	std::cout << (double) t1 / CLOCKS_PER_SEC << "\n";


	std::list<int, std::allocator<int>> l2;
	t2 = clock();
	for (int i = 0; i < 1000000; ++i) {
		l2.push_back(1);
	}
	t2 = clock() - t2;

	std::cout << (double) t2 / CLOCKS_PER_SEC;
	system("pause");
	return 0;
}