#include <time.h>

#include <set>
#include <iostream>
#include <functional>
#include <vector>

#include <cstddef>
#include <cstdlib>

#include <limits>
#include <new>

namespace block_allocator {

template <class T, unsigned N = 32>
class block_allocator {
    void** blocks;
    void** free_blocks;
    int allocated;

public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;

    template <class U>
    struct rebind {
        typedef block_allocator<U, N> other;
    };

    block_allocator()
        : blocks()
        , free_blocks()
        , allocated()
    {
    }

    template<class U, unsigned M>
    block_allocator(const block_allocator<U, M>&)
        : blocks()
        , free_blocks()
        , allocated()
    {
    }

    ~block_allocator()
    {
        while (blocks) {
            void** next = reinterpret_cast<void**>(*blocks);
            free(blocks - block_elements);
            blocks = next;
        }
    }

    pointer address(reference x) const
    {
        return &x;
    }

    const_pointer address(const_reference x) const
    {
        return &x;
    }

    pointer allocate(size_type n, const void* = 0)
    {
        if (n == 1) {
            if (free_blocks) {
                pointer result = reinterpret_cast<pointer>(free_blocks);
                free_blocks = reinterpret_cast<void**>(*free_blocks);
                return result;
            } else {
                void** new_block = do_alloc<void*>(area_size);
                new_block[block_elements] = blocks;
                blocks = &new_block[block_elements];
                new_block[(N - 1) * multiplier] = 0;
                for (size_type i = 2; i < N; ++i) {
                    new_block[(i - 1) * multiplier] =
                        &new_block[i * multiplier];
                }
                free_blocks = &new_block[multiplier];
                return reinterpret_cast<pointer>(new_block);
            }
        } else {
            return do_alloc<T>(n * sizeof(T));
        }
    }

    void deallocate(pointer p, size_type n)
    {
        if (n == 1) {
            *reinterpret_cast<void**>(p) = free_blocks;
            free_blocks = reinterpret_cast<void**>(p);
        } else {
            free(p);
        }
    }

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

    void construct(pointer p, const T& val)
    {
        new(p) T(val);
    }

    void destroy(pointer p)
    {
        p->~T();
    }

private:
    template <class U>
    static U* do_alloc(size_type n) {
        U* result = reinterpret_cast<U*>(malloc(n));
        if (result) {
            return result;
        } else {
            throw std::bad_alloc();
        }
    }

    static char check[sizeof(T) % sizeof(void*) == 0 ? 1 : -1];
    static const size_type multiplier = sizeof(T) / sizeof(void*);
    static const size_type block_elements = multiplier * N;
    static const size_type area_size = sizeof(T) * N + sizeof(void*);
};

}

std::vector<int> input;

template <class Cont>
void do_test()
{
    Cont c;
    for (std::vector<int>::const_iterator iter = input.begin(), end = input.end(); iter != end; ++iter) {
        c.insert(*iter);
    }
}

int main()
{
    typedef void (*test)();
    test t[] = {
        do_test<std::set<int> >,
        do_test<std::set<int, std::less<int>, block_allocator::block_allocator<int, 1024> > >
    };
    int size = 1000000;
    for (int i = 0; i < size; ++i) {
        input.push_back(i + i % 3);
    }
    size = sizeof t / sizeof t[0];
    for (int i = 0; i < size; ++i) {
        const clock_t begin = clock();
        t[i]();
        std::cout << clock() - begin << std::endl;
    }
}