template<class T>
class alloc;

template<typename T, typename Alloc = alloc<T>>
class MyContainer{
public:
    template<typename U>
    struct rebind{
        typedef Alloc<U> other; // Allocator type for type U
        // other represents some other objects
    };
};

#include <new>          // for placement new
#include <cstddef>      // for ptrdiff_t, size_t
#include <cstdlib>      // for exit()
#include <climits>      // for UINT_MAX
#include <iostream>     // for cerr
#include <vector>       // for test

namespace T_ {
    // allocate memory
    template<class T>
    inline T* _allocate(ptrdiff_t size, T*) {
        std::set_new_handler(0);    // invoke when out of memory
        T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));  // allocate memory
        if (tmp == 0) {   // the allocated memory is 0, which means that allocating memory fails
            std::cerr << "out of memory" << '\n';
            exit(0);    // terminate processs
        }
        return tmp;     // return the pointer of the allocated memory block
    }

    // release memory
    template<class T>
    inline void _deallocate(T* buffer) {
        ::operator delete(buffer);  // release the allocated memory
    }

    // constructor
    template<class T1, class T2>
    inline void _construct(T1* p, const T2& value) {
        new(p) T1(value);           // assign value at pointer p
    }

    // destructor
    template<class T>
    inline void _destroy(T* ptr) {
        ptr->~T();                  // invoke the destructor of type class
    }

    template<class T>
    class allocator {
    public:
        typedef T			value_type;
        typedef T* pointer;
        typedef const T* const_pointer;
        typedef T& reference;
        typedef const T& const_reference;
        typedef size_t		size_type;
        typedef ptrdiff_t	difference_type;

        /*-----implement part of the specific API-----*/

        // allocator::rebind->rebind allocator of type U
        template<class U>
        struct rebind {
            typedef allocator<U> other;
        };

        // pointer allocator::allocate->hint used for locality
        pointer allocate(size_type n, const void* hint = 0) {
            return _allocate((difference_type)n, (pointer)0);
        }

        // allocator::deallocate
        void deallocate(pointer p, size_type n) { _deallocate(p); }

        // allocator::construct
        void construct(pointer p, const T& value) {
            _construct(p, value);
        }

        // allocator::destroy
        void destroy(pointer p) { _destroy(p); }

        // pointer allocator::address
        pointer address(reference x) { return (pointer)&x; }

        // const_pointer allocator::const_address
        const_pointer const_address(const_reference x) {
            return (const_pointer)&x;
        }

        // size_type allocator::max_size()
        size_type max_size() const {
            return size_type(UINT_MAX / sizeof(T));
        }
    };
}

int main() {
    int ia[5] = { 0, 1, 2, 3, 4 };
    unsigned int i;

    std::vector<int, T_::allocator<int>> iv(ia, ia + 5);
    for (i = 0; i < iv.size(); i++) std::cout << iv[i] << ' ';
    std::cout << '\n';

    return 0;
}

template<class T, class Alloc = alloc>  // 缺省使用alloc为配置器
class vector{ ... };

#include <new>
#include <cstddef>
#include <cstdlib>
#include <limits>
#include <iostream>
#include <algorithm>
#include <vector>

/*-----generalized_style-----*/
template<class T>
inline T* allocate(ptrdiff_t size, T*)
{
    std::set_new_handler(0);
    T* tmp = (T*)(::operator new ((size_t)(size * sizeof(T))));
    if(tmp == 0)
    {
        std::cerr << "out of memory" << '\n';
        exit(1);
    }
    return tmp;
}

template<class T>
inline void deallocate(T* buffer)
{
    ::operator delete(buffer);
}

/*-----SGI_style-----*/
template<class T>
class allocator
{
public:
    typedef T			value_type;
    typedef T*			pointer;
    typedef const T*	const_pointer;
    typedef T&			reference;
    typedef const T*	const_reference;
    typedef size_t		size_type;
    typedef ptrdiff_t	difference_type;

    pointer allocate(size_type n)
    {
        return ::allocate((difference_type)n, (pointer)0);
    }

    /*-----in the book-----*/
    /*void deallocate(pointer p) { ::deallocate(p); }
      this deallocate is not runnable */
    /*-----and the below "deallocate" is runnable --------------*/

    void deallocate(pointer p, size_type n) { ::deallocate(p); }
    pointer address(reference x) { return (pointer)&x; }

    const_pointer const_address(const_reference x)
    {
        return (const_pointer)&x;
    }

    size_type init_page_size()
    {
        return std::max(size_type(1), size_type(4096 / sizeof(T)));
    }

    size_type max_size() const
    {
        return std::max(size_type(1), size_type(UINT_MAX / sizeof(T)));
    }
};

int main() {
    int ia[5] = { 0, 1, 2, 3, 4 };
    unsigned int i;

    std::vector<int, allocator<int>> iv(ia, ia + 5);
    for (i = 0; i < iv.size(); i++) std::cout << iv[i] << ' ';
    std::cout << '\n';

    return 0;
}

#include<stl_alloc.h>     // for allocating and deallocating of memory
#include<stl_construct.h> // for constructing and destructing of object

#include <new>          // for placement new

template<class T1, class T2>
inline void construct(T1* p, const T2& value){
    new(p) T1(value);   // placement new -> invoke T1::T1(value);
}

template<class T>
inline void destroy(T* pointer){
    pointer->~T();      // invoke ~T()
}

template<class T>
inline void destroy(ForwardIterator first, ForwardIterator last){
    __destroy(first, last, value_type(first));
}

template<class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*){
    typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
    __destroy_aux(first, last, trivial_destructor());
}

templace<class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type){
    for(; first < last; ++first) destroy(&*first);
}

template<class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type){}

#ifdef
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;     // set alloc as primary allocator
#else
// set alloc as secondary allocator
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
#endif

template<class T, class Alloc>
class simple_alloc{
public:
    static T* allocate(size_t n){
        return 0 == n ? 0 : (T*) Alloc::allocate(n * sizeof(T));
    }
    static T* allocate(void){
        return (T*) Alloc::allocate(sizeof(T));
    }
    static void deallocate(T* p, size_t n){
        if(0 != n) Alloc::deallocate(p, n * sizeof(T));
    }
    static void deallocate(T* p){
        Alloc::deallocate(p, sizeof(T));
    }
};

template<class T, class Alloc = alloc> // default
class vector{
protected:
    // specified allocator that allocates a size of element per time
    typedef simple_alloc<value_type, Alloc> data_allocator;
    void deallocate(){
        if(...) data_allocator(start, end_of_storage - start);
    }
    ...
};

#if 0
#   include <new>
#   define THROW_BAD_ALLOC throw bad_alloc
#elif #defined(__THROW_BAD_ALLOC)
#   include <iostream>
#   define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1);
#endif

template<int inst>
class ex{
public:
  void printf() { std::cout << "inst: " << inst; }
};

int main(){
  /* ex<para> e1; here para = inst */
  ex<3> e1;
  e1.printf();
  return 0;
}

#include <iostream>

class MyClass{
public:
    static void staticFunction(){
        std::cout << "Inside staticFunction" << '\n';
    }

    void nonstaticFunction(){
        std::cout << "Inside nonstaticFunction" << '\n';
    }
};

int main(){
    /* call static function without an instance */
    MyClass::staticFunction();

    /* class static function from an instance (this is uncommon but valid) */
    MyClass obj;
    obj.staticFunction();

    /* cannot call non-static function without an instance */
    MyClass::nonStaticFunction(); /* Error cannot call non-static function
                                     without instance */

    /* call non-static function from an instance */
    obj.nonstaticFunction();

    return 0;
}

#include <iostream>

int add(int a, int b);
int subtract(int a, int b);

int main(){
    int(*operation)(int, int);  /* declaration of function pointer */

    operation = add;    /* assign address of add function to operation */
    printf("Addition result: %d\n", (*operation)(5, 3));    /* call function through function pointer */

    operation = subtract;   /* assign address of subtract function to operation */
    printf("Subtract result: %d\n", (*operation)(5, 3));    /* call function through function pointer */

    return 0;
}

int add(int a, int b){ return a + b; }
int subtract(int a, int b) { return a - b; }

template<int inst>
class __malloc_alloc_template {
private:
    /* the below are the function
     pointers which are used for cope with the out-of-memory(oom) */
    static void *oom_malloc(size_t);

    static void *oom_realloc(void *, size_t);

    static void (* __malloc_alloc_oom_handler)();

public:
    /* allocator */
    static void *allocate(size_t n) {
        void *result = malloc(n); // primary allocator employs malloc() directly
        /* when out of memory, invoke oom_malloc() */
        if (0 == result) result = oom_malloc(n);
        return result;
    }

    /* deallocator */
    static void deallocate(void *p, size_t /* n */) {
        free(p);  /* primary allocator employs free() directly */
    }

    /* reallocator */
    static void *reallocate(void *p, size_t /* old_sz */, size_t new_sz) {
        void *result = realloc(p, new_sz);
        /* primary allocator employs realloc() directly
 when out of memory, invoke oom_realloc()*/
        if (0 == result) result = oom_realloc(p, new_sz);
        return result;
    }

    /* emulate set_new_handler(), which means that
       out-of-memory handler is definable */
    static void (*set_malloc_handler(void (*f)()))() {
        void (* old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return (old);
    }
};

/* malloc_alloc out-of-memory banding */
template<int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;

template<int inst>
void* __malloc_alloc_template<inst>::oom_malloc(size_t n){
  void (* my_malloc_handler)();
  void* result;

  for(;;){ /* endlessly allocate and deallocate until allocate successfully */
    my_malloc_handler = __malloc_alloc_oom_handler;
    if(0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
    (* my_malloc_handler)();
    result = malloc(n);
    if(result) return result;
   }
}

union obj{
  union obj* free_list_link;
  char client_data[1];
};

#include <cstddef>

enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES / __ALIGN };

template<bool threads, int inst>
class __default_alloc_template{
private:
    static size_t ROUND_UP(size_t bytes){ return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1)); }
    /*  '(bytes + __ALIGN -1': This part adds an offset to the 'bytes' value. The '__ALIGN - 1'
     *  is used to ensure that we round up to the next multiple of '__ALIGN'.For example, if '__ALIGN'
     *  is 4, then '__ALIGN - 1' is 3, and adding 3 ensures that the result will be at least a multiple
     *  of 4 greater than 'bytes'.
     *  '& !(__ALIGN - 1)‘: This part performs a bitwise AND operation wit the complement of '(__ALIGN - 4)'.
     *  The complement operation '~' flips all the bits of '(__ALIGN - 1)', effective creating a bitmask where
     *  all bits are set to 1 except for the lower bits determined by '__ALIGN - 1'. By performing a bitwise AND
     *  with this bitmask, we effectively set the lower bits to O, thus rounding down the result to the nearest
     *  multiple of '__ALIGN'.
     */
private:
    union obj{
        union obj* free_list_link;
        char client_data[1];
    };
private:
    /* 16 free-lists */
    static obj* volatile free_list[__NFREELISTS];
    /* employ Nth free-list according to the size
     * of memory chunk (begin with 1st memory chunk)
    */
    static size_t FREELIST_INDEX(size_t bytes){ return (((bytes) + __ALIGN + 1) / __ALIGN - 1); }
    /* return a object in size of n, and add other memory
     * chunks in size of n into free-list if possible
    */
    static void* refill(size_t n);
    /* allocate a memory space that can hold n objs
     * its capacity is size
     * if inconvenient to allocate for n objs, n cloud decrease
    */
    static void* refill(size_t size, int& nobjs);

    // chunk allocation state
    static char* start_free;    // the start position in memory pool, only changes in chunk_alloc()
    static char* end_free;      // the end position in memory pool, only changes in chunk_alloc()
    static size_t heap_size;
public:
    static void* allocate(size_t n) { }
    static void deallocate(void* p, size_t n) { }
    static void* reallocate(void* p, size_t old_sz, size_t new_sz);
};

/* the original value and definition setting for static data member */
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::start_free = 0;

template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = 0;

template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj* volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] =
        {0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0};

// n must be > 0, to assure that
// there is the memory allocated
static void* allocate(size_t n){
  obj* volatile* my_free_list;
  obj* result;

// if allocating memory > 128 bytes
if(n > (size_t) __MAX_BYTES){
  return (malloc_alloc:allocate(n));
}

// select a suitable chunk in 1 of 16 free lists
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if (result == 0){
  // no find a available free list
  // preparing to refill another
  void* r = refill(ROUND_UP(n));
  return r;
}
// adjust free list
*my_free_list = result -> free_list_link;
return (result);
};

// p can not be 0
static void deallocate(void* p, size_t n){
    obj* q = (obj *)p;
    obj* volatile* my_free_list;

    // if size > 128 bytes, call the primary allocator
    if(n > (size_t) __MAX_BYTES){
        malloc_alloc::deallocate(p, n);
        return;
    }

    // selecting the corresponding free list
    my_free_list = free_list + FREELIST_INDEX(n);

    // adjust free list, recycle the chunk
    q -> free_list_link = *my_free_list;
    *my_free_list = q;
}

// return a obj in size of n
// and supply some chunks for free list properly sometimes
// supposing that n is upregulated to a multiple of 8
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n){
    int nobjs = 20;
    // call chunk_alloc(), try to get n(objs) chunks
    // as new nodes for free list
    char* chunk = chunk_alloc(n, nobjs); // nobjs -> pass by reference
    obj* volatile* my_free_list;
    obj* result;
    obj* current_obj, * next_obj;
    int i;

    // if only get one chunk, then allocate this chunk to the target
    // so there is no new node for free list
    if(l == nobjs) return(chunk);
    // if not, adjust free list and prepare to link a new node
    my_free_list = free_list + FREELIST_INDEX(n);

    // create free list in chunk space
    result = (obj*)chunk;   // this piece of chunk will return to user
    // help free list point toward the new allocated space (from memory pool)
    *my_free_list = new_obj = (obj*)(chunk + n);
    // connect the each node in free list
    for(i = 1; ; i++){      // i begin with 1, because i[0] will be return to user
        current_obj = next_obj;
        if (nobjs - 1 == i){
            current_obj -> free_list_link = 0;
            break;
        }else{
            current_obj -> free_list_link = next_obj;
        }
    }
    return(result);
}

template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs){
    char* result;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free;  // the rest of memory pool

    if(bytes_left >= total_bytes){
        // the rest of memory pool could satisfy the need
        result = start_free;
        start_free += total_bytes;
        return(result);
    }else if( bytes_left >= size){
        // the rest of memory pool could not totally satisfy the need
        // but only one or more chunks
        nobjs = bytes_left / size;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return(result);
    }else{
        // memory pool can not supply the size o only one chunk
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // make full use of memory fragments
        if(bytes_left > 0){
            // allocate some surplus memory for free list primarily
            // select the proper free list
            obj* volatile* my_free_list = free_list + FREELIST_INDEX(bytes_left);
            // adjust free list, integrate the surplus memory in memory pool
            ((obj*) start_free) -> free_list_link = *my_free_list;
            *my_free_list = (obj*) start_free;
        }

        // configure heap to supply memory pool
        start_free = (char*) malloc(bytes_to_get);
        if(0 == start_free){
            // heap is not enough, malloc() fails
            int i;
            obj* volatile* my_free_list, *p;
            // check the memory that I currently have
            // allocate the small memory space is dangerous under multi-threads circumstance
            // select a proper free list
            // "proper" means that the unused memory is big enough to satisfy the need
            for(i = size; i <= __MAX_BYTES; i += __ALIGN){
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if(0 != p){
                    // chunk not in free list
                    // adjust free list to release the unused memory
                    *my_free_list = p -> free_list_link;
                    start_free = (char*) p;
                    end_free = start_free + i;
                    // revoke itself to fix nobjs
                    return(chunk_alloc(size, nobjs));
                    // any surplus memory will be integrated in free list as spare
                }
            }
            end_free = 0;   // if occur the accident, allocate the primary allocator
            // turning to out-of-memory
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);
            // if failed, throw exception
            // if succeeded, memory lack will be fixed
        }
     heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        // revoke itself to fix nobjs
        return(chunk_alloc(size, nobjs));
    }

template<class T, class Alloc>
class simple_alloc{
public:
    static T* allocate(size_t n){
        return 0 == n ? 0 : (T*) Alloc::allocate(n * sizeof(T));
    }
    static T* allocate(void){
        return (T*) Alloc::allocate(sizeof(T));
    }
    static void deallocate(T* p, size_t n){
        if(0 != n) Alloc::deallocate(p, n * sizeof(T));
    }
    static void deallocate(T* p){
        Alloc::deallocate(p, sizeof(T));
    }
};

template <class T, class Alloc = alloc> // 缺省使用 alloc 为配置器
class vector{
    public:
        typedef T value_type;
    protected:  // 专属配置器，每次配置一个元素大小
        typedef simple_alloc<value_type, Alloc> data_allocator;
};

template<class InputIterator, class ForwardIterator>
ForwardIterator
unitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result);

template<class ForwardIterator, class T>
void unintialized_fill(ForwardIterator first, ForwardIterator last,
 const T&x);

template<class ForwardIterator, class Size, class T>
ForwardIterator
uninitialized_fill_n(ForwardIterator first, Size n, const T& x);