学步园

#ifndef __TYPETRAIT__H__
#define __TYPETRAIT__H__
#include <cstddef>
namespace stc{
	class trueType{};
	class falseType{};
	template <typename type>
	class typeTrait{
	public:
		typedef trueType	thisDummyMemberMustBeFirst;
		typedef falseType	hasTrivalDefaultCtor;
		typedef falseType	hasTrivalCopyCtor;
		typedef falseType	hasTrivalAssignmentOperator;
		typedef falseType	hasTrivalDtor;
		typedef falseType	isPODType;
	};
	template <> class typeTrait < signed char > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < unsigned char > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < wchar_t > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < short > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < unsigned short > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < int > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < unsigned int > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < long > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < long long> {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < unsigned long > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < float > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < double > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < long double > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <class type> class typeTrait < type* > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
	template <> class typeTrait < bool > {
	public:
		typedef trueType	hasTrivalDefaultCtor;
		typedef trueType	hasTrivalCopyCtor;
		typedef trueType	hasTrivalAssignmentOperator;
		typedef trueType	hasTrivalDtor;
		typedef trueType	isPODType;
	};
}
#endif

#ifndef __VECTOR__H__
#define __VECTOR__H__
#pragma warning(disable : 4996)
#include <memory>
#include <string>
#include <cassert>
#include <algorithm>
#include <stdexcept>
#include "typeTrait.h"
namespace stc{
	template <typename type,
	class Alloc = std::allocator<type> >
	class vector{
	public:
		typedef	type				valueType;
		typedef type*				pointer;
		typedef type*				iterator;
		typedef type&				reference;
		typedef std::size_t			sizeType;
		typedef std::ptrdiff_t		differenceType;
	public:
		~vector();
		vector();
		vector(vector<type>&&);
		vector(const vector<type>&);
		vector(sizeType, const type&);
		vector(int, const type&);
		vector(long, const type&);
		explicit vector(sizeType);
		iterator begin() { return (mStart); }
		iterator end() { return (mFinish); }
		sizeType size() const{ return (mFinish - mStart); }
		sizeType capacity()	const{ return (mEnd - mStart); }
		bool empty() const{ return mStart == mFinish; }
		reference operator[](sizeType index) { return *(mStart + index); }
		reference front() { assert(!empty()); return *mStart; }
		reference back() { assert(!empty()); return *(mFinish - 1); }
		void push_back(const type&);
		void pop_back();
		iterator erase(iterator, iterator);
		iterator erase(iterator);
		void clear();
		void insert(iterator,const type&,const sizeType = 1);
		vector<type>& operator =(const vector<type>&);
		vector<type>& operator =(vector<type>&&);
		vector<type>& memcopy(const vector<type>&);
		vector<type>& memcopy(vector<type>&&);
	private:
		void insertAux(const sizeType Sz = sDefaultSize);
		void insertAux(trueType,const sizeType Sz = sDefaultSize);
		void insertAux(falseType,const sizeType Sz = sDefaultSize);
		void deallocate();
		void fillInitialize(sizeType, const type&);
		void fillInitialize(sizeType, const type&, trueType);
		void fillInitialize(sizeType, const type&, falseType);
		void destroy(trueType) { mFinish = mStart; }
		void destroy(falseType);
		void push_back(const type&, trueType);
		void push_back(const type&, falseType);
		void pop_back(falseType);
		void pop_back(trueType);
		iterator erase(iterator, iterator, falseType);
		iterator erase(iterator, iterator, trueType);
	private:
		iterator				mStart;
		iterator				mFinish;
		iterator				mEnd;
		Alloc					mAllocator;
		static const sizeType	sDefaultSize = 12;
	};

	template <typename type, class Alloc>
	vector<type, Alloc>::
		vector() :mStart(0), mFinish(0), mEnd(0){
	}

	template <typename type, class Alloc>
	vector<type, Alloc>::
		vector(sizeType Sz, const type& val)
		: mStart(0), mFinish(0), mEnd(0){
		this->fillInitialize(Sz, val);
	}

	template <typename type, class Alloc>
	vector<type, Alloc>::
		vector(int Sz, const type& val)
		: mStart(0), mFinish(0), mEnd(0){
		this->fillInitialize(Sz, val);
	}

	template <typename type, class Alloc>
	vector<type, Alloc>::
		vector(long Sz, const type& val)
		: mStart(0), mFinish(0), mEnd(0){
		this->fillInitialize(Sz, val);
	}

	template <typename type, class Alloc>
	vector<type, Alloc>::
		vector(sizeType Sz)
		: mStart(0), mFinish(0), mEnd(0){
		this->fillInitialize(Sz, type());
	}

	template <typename type,class Alloc>
	vector<type,Alloc>::
		vector(const vector<type>& rhs)
		: mStart(0), mFinish(0), mEnd(0){
		*this = rhs;
	}

	template <typename type,class Alloc>
	vector<type,Alloc>::
		vector(vector<type>&& rhs)
		: mStart(0), mFinish(0), mEnd(0){
		mStart = rhs.mStart;
		mFinish = rhs.mFinish;
		mEnd = rhs.mEnd;
		rhs.mStart = rhs.mFinish = mEnd = NULL;
	}

	template <typename type, class Alloc>
	vector<type, Alloc>::
		~vector(){
		typedef typename typeTrait<type>::
			isPODType		isPODType;
		if (mStart != NULL){
			this->destroy(isPODType());
			mAllocator.deallocate(mStart, mEnd - mStart);
		}
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		fillInitialize(sizeType Sz, const type& val){
		assert(!mStart || !mEnd);
		mStart = mAllocator.allocate(Sz);
		if (mStart == NULL)
			throw std::bad_alloc();
		mFinish = mEnd = mStart + Sz;
		typedef typename typeTrait<type>::
			isPODType		isPODType;
		this->fillInitialize(Sz, val, isPODType());
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		fillInitialize(sizeType Sz, const type& val, trueType){
		std::uninitialized_fill(mStrart, mStart + Sz, val);
	}

	template <> void vector<char>::
		fillInitialize(sizeType Sz, const char& ch, trueType){
		memset(mStart, ch, Sz);
	}

	template <> void vector<wchar_t>::
		fillInitialize(sizeType Sz, const wchar_t& wch, trueType){
		wmemset(mStart, wch, Sz);
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		fillInitialize(sizeType Sz, const type& val, falseType){
		std::uninitialized_fill(mStart, mStart + Sz, val);
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		deallocate(){
		assert(mStart);
		mAllocator.deallocate(mStart, mEnd - mStart);
		mStart = mFinish = mEnd = NULL;
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		insertAux(const sizeType Sz){
		typedef typename stc::typeTrait<type>::
			isPODType	isPODType;
		this->insertAux(isPODType());
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		insertAux(trueType,const sizeType Sz){
		sizeType oSz = size();
		sizeType nSz = oSz + sDefaultSize;
		iterator ps = mAllocator.allocate(nSz);
		if (ps == NULL)
			throw std::bad_alloc();
		if (oSz != 0){
			std::copy(mStart, mStart + oSz, ps);
			mAllocator.deallocate(mStart, oSz);
		}
		mStart = ps;
		mEnd = mStart + nSz;
		mFinish = mStart + oSz;
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		insertAux(falseType,const sizeType Sz){
		sizeType oSz = size();
		sizeType nSz = oSz + Sz;
		iterator ps = mAllocator.allocate(nSz);
		if (ps == NULL)
			throw std::bad_alloc();
		std::uninitialized_copy(mStart, mEnd, ps);
		this->destroy(falseType());
		mAllocator.deallocate(mStart, oSz);
		mStart = ps;
		mFinish = mStart + oSz;
		mEnd = ps + nSz;
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		destroy(falseType){
		if (mStart == NULL) return;
		for (iterator first = mStart; first != mFinish; ++first)
			mAllocator.destroy(first);
		mFinish = mStart;
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		push_back(const type& val){
		if (mFinish == mEnd)
			this->insertAux();
		typedef typename stc::typeTrait<type>::
			isPODType isPODType;
		this->push_back(val, isPODType());
	}

	template <typename type, class Alloc>
	void vector<type, Alloc>::
		push_back(const type& val, falseType){
		mAllocator.construct(mFinish, val);
		++mFinish;
	}

	template <typename type,class Alloc>
	inline void vector<type,Alloc>::
		push_back(const type& val, trueType){
		*mFinish = val;
		++mFinish;
	}

	template <typename type,class Alloc>
	void vector<type,Alloc>::
		pop_back(){
		assert(mStart != mFinish);
		typedef typename stc::typeTrait<type>::
				isPODType isPODType;
		this->pop_back(isPODType());
	}

	template <typename type,class Alloc>
	inline void vector<type,Alloc>::
		pop_back(trueType){
		--mFinish;
	}

	template <typename type,class Alloc>
	void vector<type, Alloc>::
		pop_back(falseType){
		mAllocator.destroy(mFinish);
		--mFinish;
	}

	template <typename type,class Alloc>
	typename vector<type,Alloc>::iterator 
		vector<type,Alloc>::
	erase(iterator first, iterator last){
		assert(first <= last);
		assert(last <= mFinish);
		typedef typename typeTrait<type>::isPODType
				isPODType;
		return erase(first, last, isPODType());
	}

	template <typename type,class Alloc>
	typename vector<type,Alloc>::iterator
		vector<type, Alloc>::
	erase(iterator first, iterator last, falseType){
		iterator it = std::copy(last, mFinish, first);
		for (iterator iter = it; iter != mFinish; ++iter)
			mAllocator.destroy(iter);
		mFinish -= (last - first);
		return it;
	}

	template <typename type,class Alloc>
	typename vector<type,Alloc>::iterator
		vector<type,Alloc>::
		erase(iterator first, iterator last, trueType){
		iterator it = std::copy(last, mFinish, first);
		mFinish -= (last - first);
		return it;
	}

	template <> typename vector<char>::iterator
			vector<char>::
			erase(char* first, char* last, trueType){
		char* it = (char*)memcpy(first, last, mFinish - last);
		mFinish -= (last - first);
		return it;
	}

	template <typename type,class Alloc>
	typename vector<type,Alloc>::iterator
		vector<type,Alloc>::
		erase(iterator pos){
		assert(pos >= mStart && pos < mFinish);
		return erase(pos, pos + 1);
	}

	template <typename type,class Alloc>
	void vector<type,Alloc>::
		clear(){
		if (empty()) return;
		erase(begin(), end());
		mStart = mEnd = mFinish = NULL;
	}

	template <typename type,class Alloc>
	void vector<type,Alloc>::
		insert(iterator pos, const type& val, const sizeType Sz){
		if (Sz == 0) return;
		assert(pos < this->mFinish);
		assert(pos >= mStart);
		if (capacity() >= Sz){
			sizeType elemAfter = mFinish - pos;
			sizeType pre = mFinish;
			if (elemAfter > Sz){
				std::uninitialized_copy(mFinish - Sz, mFinish, mFinish);
				mFinish += Sz;
				std::copy_backward(pos, pre - Sz, pre);
				std::fill(pos, pos + Sz, val);
			}else{
				std::uninitialized_copy_n(mFinish, Sz - elemAfter, val);
				mFinish += Sz - elemAfter;
				std::uninitialized_copy(pos, pre, pre);
				mFinish += elemAfter;
				std::fill(pos, pre, val);
			}
		}else{
			sizeType oSz = size();
			sizeType nSz = oSz + Sz;
			iterator nMemory = mAllocator.allocate(nSz);
			if (nMemory == NULL) throw std::bad_alloc();
			iterator nFinish = std::uninitialized_copy(mStart, pos, nMemory);
			nFinish = std::uninitialized_copy_n(nFinish, Sz, val);
			nFinish = std::uninitialized_copy(pos, mFinish, nFinish);
			this->clear();
			mStart = nMemory;
			mFinish = nFinish;
			mEnd = mStart + nSz;
		}
	}

	template <typename type,class Alloc>
	vector<type>& vector<type,Alloc>::
		operator =(const vector<type>& rhs){
		return this->memcopy(rhs);
	}

	template <typename type,class Alloc>
	vector<type>& vector<type,Alloc>::
		operator =(vector<type>&& rhs){
		if (this == (&rhs)) return *this;
		this->clear();
		mStart = rhs.mStart;
		mFinish = rhs.mFinish;
		mEnd = rhs.mEnd;
		rhs.mStart = rhs.mFinish = mEnd = NULL;
	}

	template <typename type,class Alloc>
	vector<type>& vector<type,Alloc>::
		memcopy(const vector<type>& rhs){
		if (this == (&rhs)) return *this;
		iterator nMemory = mAllocator.allocate(rhs.size());
		if (nMemory == NULL) throw std::bad_alloc();
		iterator it = std::
			uninitialized_copy(rhs.begin(),rhs.end(),nMemory);
		try{
			if (it != (nMemory + rhs.size())){
				mAlloc.deallocate(nMemory);
				std::runtime_error("");
			}
		}catch (const std::runtime_error& e){
			abort();
		}catch (...){}
		this->clear();
		mStart = nMemory;
		mFinish = mEnd = nMemory + rhs.size();
		return *this;
	}

	template <typename type,class Alloc>
	vector<type>& vector<type,Alloc>::
		memcopy(vector<type>&& rhs){
		if (this == (&rhs)) return *this;
		this->clear();
		mStart = rhs.mStart;
		mFinish = rhs.mFinish;
		mEnd = rhs.mEnd;
		rhs.mStart = rhs.mFinish = mEnd = NULL;
	}
}
#endif