int main(int, char**)
{
    const std::allocator<int> a;
    std::size_t M = a.max_size();
    assert(M > 0xFFFF && M <= (std::numeric_limits<std::size_t>::max() / sizeof(int)));

  return 0;
}

void test_address()
{
    T* tp = new T();
    const T* ctp = tp;
    const std::allocator<T> a;
    assert(a.address(*tp) == tp);
    assert(a.address(*ctp) == tp);
    delete tp;
}

namespace NL3D
{
	#ifdef PS_FAST_ALLOC
		uint NumPSAlloc = 0;
		uint NumDealloc = 0;
		NLMISC::CContiguousBlockAllocator *PSBlockAllocator= NULL;
		static std::allocator<uint8> PSStdAllocator;
		//
		typedef NLMISC::CContiguousBlockAllocator *TBlocAllocPtr;
		//
		struct CPSAllocInfo
		{
			size_t			NumAllocatedBytes;
			TBlocAllocPtr   BlocAllocator;  // may be NULL if was allocated from stl allocator
		};
		//
		void *PSFastMemAlloc(uint numBytes)
		{
			NL_PS_FUNC(PSFastMemAlloc)
			CPSAllocInfo *result;
			// if a block allocator is available, use it
			if (PSBlockAllocator)
			{
				result = (CPSAllocInfo *) PSBlockAllocator->alloc(numBytes + sizeof(CPSAllocInfo));
				result->BlocAllocator = PSBlockAllocator; // mark as a block from block allocator
			}
			else
			{
				result = (CPSAllocInfo *) PSStdAllocator.allocate(numBytes + sizeof(CPSAllocInfo));
				result->BlocAllocator = NULL;
			}
			result->NumAllocatedBytes = numBytes;
			return (void *) (result + 1); // usable space starts after header
		}

		void PSFastMemFree(void *block)
		{
			NL_PS_FUNC(PSFastMemFree)
			uint8 *realAddress = (uint8 *) ((uint8 *) block - sizeof(CPSAllocInfo));
			CPSAllocInfo *ai = (CPSAllocInfo *) realAddress;
			if (ai->BlocAllocator)
			{
				// block comes from a block allocator
				ai->BlocAllocator->free((void *) realAddress, ai->NumAllocatedBytes + sizeof(CPSAllocInfo));
			}
			else
			{
				// block comes from the stl allocator
				PSStdAllocator.deallocate((uint8 *) realAddress, ai->NumAllocatedBytes + sizeof(CPSAllocInfo));
			}
		}
	#endif
}

		void *PSFastMemAlloc(uint numBytes)
		{
			NL_PS_FUNC(PSFastMemAlloc)
			CPSAllocInfo *result;
			// if a block allocator is available, use it
			if (PSBlockAllocator)
			{
				result = (CPSAllocInfo *) PSBlockAllocator->alloc(numBytes + sizeof(CPSAllocInfo));
				result->BlocAllocator = PSBlockAllocator; // mark as a block from block allocator
			}
			else
			{
				result = (CPSAllocInfo *) PSStdAllocator.allocate(numBytes + sizeof(CPSAllocInfo));
				result->BlocAllocator = NULL;
			}
			result->NumAllocatedBytes = numBytes;
			return (void *) (result + 1); // usable space starts after header
		}

        void reallocate()
        {
            auto newcap = size() ? size()*2 : 1;

            auto newspace = alloc.allocate(newcap);

            std::cout << "reallocate: size() " << size() << std::endl;

            auto dest = newspace;
            auto source = element_;

            // move the data from the old memory to the new
            // std::move() returns rvalue, which cause construct() to use string
            // move ctor.
            //
            // seg-fault when have a typo and use element in the loop:
            //
            // for (size_t i = 0; i != size(); ++i)
            //     alloc.construct(dest++, std::move(*element_++));
            //
            // *gdb-debug* bt when use -g
            // Program terminated with signal SIGSEGV, Segmentation fault.
            // #0  0x00007f94aa120113 in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string&&) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
            // (gdb) bt
            // #0  0x00007f94aa120113 in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string&&) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
            // #1  0x0000000000401bf7 in __gnu_cxx::new_allocator<std::string>::construct<std::string<std::string> > (this=0x602cd1 <StrVec::alloc>, __p=0xa53000) at /usr/include/c++/4.9/ext/new_allocator.h:120
            // #2  0x0000000000401932 in StrVec::reallocate (this=0x7ffdc9026bc0) at t_ex_strvec.cpp:117
            // #3  0x0000000000401aa5 in StrVec::check_and_alloc (this=0x7ffdc9026bc0) at t_ex_strvec.cpp:147
            // #4  0x000000000040165e in StrVec::push_back (this=0x7ffdc9026bc0, s="two") at t_ex_strvec.cpp:44
            // #5  0x000000000040133e in main () at t_ex_strvec.cpp:198
            //
            // when not use -g
            // (gdb) bt
            // #0  0x00007f3348f5c113 in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string&&) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
            // #1  0x0000000000401bf7 in void __gnu_cxx::new_allocator<std::string>::construct<std::string, std::string>(std::string*, std::string&&) ()
            // #2  0x0000000000401932 in StrVec::reallocate() ()
            // #3  0x0000000000401aa5 in StrVec::check_and_alloc() ()
            // #4  0x000000000040165e in StrVec::push_back(std::string const&) ()
            // #5  0x000000000040133e in main ()
            //
            // How to debug? See that uses 'construct' and gdb is useful to see
            // what's going on when stepping through. Found out that the loop
            // continues and saw that when add to print i and size().
            //
            // ...
            // i: 16856, size: 18446744073709534761
            // Segmentation fault (core dumped)
            //
            // (gdb) f 2
            // #2  0x0000000000401932 in StrVec::reallocate (this=0x7ffdc9026bc0) at t_ex_strvec.cpp:117
            // 117                     alloc.construct(dest++, std::move(*element_++));
            // (gdb) p i
            // $1 = 16856
            // (gdb) p/u free_-element_
            // $6 = 18446744073709534760
            //
            // Why? Since element_ is member data and keep increasing it, then
            // size() member function would produce negative which turns into
            // big number sicne size() returns size_t, unsigned int.

            for (size_t i = 0; i != size(); ++i)
            {
                // std::cout << "i: " << i << ", size: " << size() << std::endl;
                alloc.construct(dest++, std::move(*source++));
            }

            // std::cout.flush();
            // std::this_thread::sleep_for(std::chrono::seconds{5});

            // to point the new space
            element_ = newspace;
            free_ = dest;
            cap_ = element_ + newcap;
        }

void String::free()
{
    if (elements)
    {
        std::for_each(elements,end,
                    [this](char& c) {alloc.destroy(&c);});
        alloc.deallocate(elements,end-elements);
    }
}

/**
* @brief   destroy the elements and deallocate the space previously allocated.
*/
void StrVec::free()
{

	if (element)     //  if not nullptr
	{
		//! destory it  in reverse order.
		for (auto p = first_free; p != element; /* empty */)
			alloc.destroy(--p);

		alloc.deallocate(element, capacity());
	}
}

        void free()
        {
            // may not pass deallocate() a nullptr.
            if (element_)
            {
                // move backward and use "--p" to delete [element_, free)
                // call type dtor, which is string dtor.
                for (auto p = free_; p != element_; /* empty */ )
                    alloc.destroy(--p);

                alloc.deallocate(element_, cap_ - element_);
            }
        }

void str_vec::reallocate()
{
    auto new_capacity = size()>1?size()*2:1;
    auto new_data = alloc.allocate(new_capacity);
    auto dest = new_data;
    auto elem = elements;
    for(std::size_t i = 0;i<size();++i)
        alloc.construct(dest++,std::move(*elem++));
    free();
    elements = new_data;
    first_free = dest;
    std::cout << cap - elements << std::endl;
    cap = new_data+new_capacity;
}

static void *l_realloc_func(void *b, int os, int s)
{
	if (os == s) return b;
	void *newB = l_stlAlloc.allocate(s);
	memcpy(newB, b, std::min(os, s));
	l_free_func(b, os);
	return newB;
}

        std::pair<std::string *, std::string *>
            alloc_and_copy(const std::string *begin, const std::string *end)
            {
                // allocate `unconstructed` space to hold elements
                // *cxx-iter-arithmetic*
                auto data = alloc.allocate(end - begin);

                // uninitialized_copy() 
                // * construct copies of given elements in uninitialized space
                // * returns the position after the last initialized element.
                return {data, uninitialized_copy(begin, end, data)};
            }

/**
* @brief   allocate new space for the given range and copy them into it
* @param b
* @param e
* @return  a pair of pointers pointing to [first element , one past the last) in the new space
*/
std::pair<std::string *, std::string *>
StrVec::alloc_n_copy(std::string *b, std::string *e)
{
	//! calculate the size needed and allocate space accordingly
	std::string* data = alloc.allocate(e - b);

	return{ data, std::uninitialized_copy(b, e, data) };
	//!            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
	//! which copies the range [first,last) into the space of which
	//! the starting address p_data is pointing to.
	//! This function returns a pointer pointing to one past the last element.
}

/**
 @brief �ͷ�ԭ�ȵĿռ䲢���·���

  �൱�ڰ��³ߴ����¹���һ���� AutoGrownMemIO
  ����Ҫ�Ѿ����ݿ������µ�ַ
 */
void AutoGrownMemIO::init(size_t newsize)
{
//	if (m_beg)
//		::free(m_beg);
//	m_pos = m_beg = m_end = 0;
//	m_beg = (byte*)::malloc(newsize);
	size_t oldSize = size();
	try {
		if (m_beg) {
			G_byteAlloc.deallocate(m_beg, oldSize);
			m_pos = m_beg = m_end = 0;
		}
		m_beg = G_byteAlloc.allocate(newsize);
	}
	catch (const std::exception& exp)
	{
		std::ostringstream oss;
		oss << "at " << BOOST_CURRENT_FUNCTION << ": size=" << oldSize << ", newsize=" << newsize
			<< ", nested-exption[, type=" << typeid(exp).name() << ", what=" << exp.what() << "]";
		throw std::runtime_error(oss.str());
	}

	if (0 == m_beg)
	{
#ifdef _MSC_VER
		std::ostringstream oss;
		oss << "alloc failed in \"" << BOOST_CURRENT_FUNCTION
			<< "\", with capacity=" << newsize
			<< ", [this=" << (void*)(this)
			<< "] was partly mutated and is not in consistent state!";
		throw std::bad_alloc(oss.str().c_str());
#else
		throw std::bad_alloc();
#endif
	}
	m_pos = m_beg;
	m_end = m_beg + newsize;
}

/**
* @brief   allocate memory for spicified number of elements
* @param n
* @note    it's user's responsibility to ensure that @param n is greater than
*          the current capacity.
*/
void StrVec::wy_alloc_n_move(std::size_t n)
{
	std::size_t newCapacity = n;

	std::string*
		newData = alloc.allocate(newCapacity);

	std::string*
		dest = newData;
	std::string*
		elem = element;

	//! move the old to newly allocated space.
	for (std::size_t i = 0; i != size(); ++i)
		alloc.construct(dest++, std::move(*elem++));

	free();

	//! update data structure
	element = newData;
	first_free = dest;
	cap = element + newCapacity;
}

/**
 @brief �ı� buffer �ߴ�

  ���ı� buffer �е��Ѵ����ݣ����ı� pos

 @note must m_pos <= newsize
 */
void AutoGrownMemIO::resize(size_t newsize)
{
	assert(tell() <= newsize);

//	byte* newbeg = (byte*)::realloc(m_beg, newsize);
	byte* newbeg = 0;
	try {		
		newbeg = G_byteAlloc.allocate(newsize);
	}
	catch (const std::exception& exp)
	{
		std::ostringstream oss;
		oss << "at " << BOOST_CURRENT_FUNCTION << ": size=" << size() << ", newsize=" << newsize
			<< ", nested-exption[, type=" << typeid(exp).name() << ", what=" << exp.what() << "]";
		throw std::runtime_error(oss.str());
	}
	if (newbeg)
	{
		memcpy(newbeg, m_beg, size());		
		G_byteAlloc.deallocate(m_beg, size() );
		m_pos = newbeg + (m_pos - m_beg);
		m_beg = newbeg;
		m_end = newbeg + newsize;
	}
	else
	{
#ifdef _MSC_VER
		std::ostringstream oss;
		oss << "realloc failed in \"void AutoGrownMemIO::resize(newsize=" << newsize
			<< ")\", the AutoGrownMemIO object is not mutated!";
		throw std::bad_alloc(oss.str().c_str());
#else
		throw std::bad_alloc();
#endif
	}
}

AutoGrownMemIO::AutoGrownMemIO(size_t size)
{
//	m_beg = 0 == size ? 0 : (byte*)::malloc(size);
	try {
		m_beg = 0 == size ? 0 : G_byteAlloc.allocate(size);
	}
	catch (const std::exception& exp)
	{
		std::ostringstream oss;
		oss << "at " << BOOST_CURRENT_FUNCTION << ": size=" << size
			<< ", nested-exption[, type=" << typeid(exp).name() << ", what=" << exp.what() << "]";
		throw std::runtime_error(oss.str());
	}
	m_end = m_beg + size;
	m_pos = m_beg;
}

/**
*  @brief  Resizes it to the specified number of elements.
*  @param  __new_size  Number of elements it should contain.
*  @param  __x  Data with which new elements should be populated.
*
*  This function will resize it to the specified
*  number of elements.  If the number is smaller than the
*  current size the it is truncated, otherwise
*  the it is extended and new elements are populated with
*  given data.
*/
void StrVec::resize(std::size_t n, const std::string &s)
{
	if (n < size())
	{
		//! destroy the range : [element+n, first_free) using destructor
		for (auto p = element + n; p != first_free; /* empty */)
			alloc.destroy(p++);

		//! move frist_free point to the new address element + n
		first_free = element + n;
	}
	else if (n > size())
	{
		for (auto i = size(); i != n; ++i)
			push_back(std::string(s));
	}
}

std::pair<char*, char*> String::alloc_n_copy(const char *beg, const char *end) {
    auto data = alloc.allocate(end - beg);
    return {data, std::uninitialized_copy(beg, end, data)};
}

std::pair<std::string*,std::string*> str_vec::alloc_n_copy(std::string *b,std::string *e)
{
    std::string *p= alloc.allocate(e-b);
    return make_pair(p,uninitialized_copy(b,e,p));
}

void str_vec::free()
{
    for(std::string *p = first_free;p > elements;)
        alloc.destroy(--p);
    alloc.deallocate(elements,cap-elements);
}