#include<iostream>
#include<memory> 
#include<iterator>
#include<string>
using std::cout;
using std::endl;
using std::cin;

template <class T> class Vec
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef size_t size_type;
	typedef T value_type;

	Vec() { create(); }
	explicit Vec(size_type n,const T& t=T()) { create(n,t);}
	
	Vec(const Vec& v) { create(v.begin(),v.end()); }
	Vec& operator=(const Vec&);
	~Vec() { uncreate();}

	T& operator[](size_type i) { return data[i]; }
	const T& operator[](size_type i) const {return data[i];}

	void push_back(const T& t)
	{
		if(avail==limit)
			grow();
		unchecked_append(t);
	}

	iterator erase(iterator);
	void clear();

	size_type size() const {return avail-data;}

	iterator begin() { return data;}
	const_iterator begin() const { return data;}

	iterator end() { return avail;}
	const_iterator end() const { return avail; }
private:
	iterator data;		//first element in the Vec
	iterator avail;		//(one past) the last of element in the Vec
	iterator limit;		//(one past) the allocated menory

	//facilities for memory allocation
	std::allocator<T> alloc;	//object to handle memory allocation
	
	//allocation and initialize the underlying array
	void create();
	void create(size_type,const T&);
	void create(const_iterator, const_iterator);

	//destroy the element in the array and free the memory
	void uncreate();

	//support funcions for push_back
	void grow();
	void unchecked_append(const T&);

};

template<class T>
Vec<T>& Vec<T>::operator =(const Vec& rhs)
{
	//check for self-assignment
	if(&rhs!=this)
	{
		//free the array in the left-hand side
		uncreate();
		//copy elements from the right-hand to the left-hand side
		create(rhs.begin(),rhs.end());
	}
	return *this;
}
template <class T> void Vec<T>::create()
{
	data=avail=limit=0;
}
template <class T> void Vec<T>::create(size_type n, const T& val)
{
	data=alloc.allocate(n,0);
	limit=avail=data+n;
	std::uninitialized_fill(data,limit,val);
}
template <class T> 
void Vec<T>::create(const_iterator i,const_iterator j)
{
	data=alloc.allocate(j-i,0);
	limit=avail=std::uninitialized_copy(i,j,data);
}
template <class T> void Vec<T>::uncreate()
{
	if(data)
	{
		//destroy (in reverse orde) the elements that were constructed
		iterator it=avail;
		while(it!=data)
			alloc.destroy(--it);

		//return all the space that was allocated
		alloc.deallocate(data,limit-data);
	}
	//reset pointers to indicate that the Vec is empty again
	data=limit=avail=0;
}
template <class T> void Vec<T>::grow()
{
	//when growing, allocate twice as much space as currently in use
	size_type new_size=std::_MAX(2*(limit-data),ptrdiff_t(1));

	//allocate new space and copy existing elements to the new space
	iterator new_data=alloc.allocate(new_size,0);
	iterator new_avail=std::uninitialized_copy(data,avail,new_data);

	//return the old space
	uncreate();

	//reset pointers to point to the newly allocate space
	data=new_data;
	avail=new_avail;
	limit=data+new_size;
}
template <class T> void Vec<T>::unchecked_append(const T& val)
{
	alloc.construct(avail++,val);
}
template <class T> Vec<T>::iterator Vec<T>::erase(iterator i)
{
	std::copy(i+1,avail,i);
	--avail;
	return i;
}
template <class T> void Vec<T>::clear()
{
	uncreate();
}



template<class T> class Ptr
{
public:
	//to copy the object conditionally when needed
	void make_unique()
	{
		if(*refptr!=1)
		{
			--*refptr;
			refptr=new size_t(1);
			p=p?clone(p):0;
		}
	}

	Ptr():refptr(new size_t(1)),p(0){}
	Ptr(T* t):refptr(new size_t(1)),p(t){}
	Ptr(const Ptr& h):refptr(h.refptr),p(h.p){++*refptr;}

	Ptr& operator=(const Ptr&);
	~Ptr();
	operator bool() const { return p;}
	T& operator*() const;
	T* operator->() const;
private:
	T* p;
	size_t* refptr;
};
template<class T> 
T& Ptr<T>::operator *() const
{
	if(p)
		return *p;
	throw std::runtime_error("unbound Ptr");
}
template<class T> 
T* Ptr<T>::operator ->() const
{
	if(p)
		return p;
	throw std::runtime_error("unbound Ptr");
}
template<class T> 
Ptr<T>& Ptr<T>::operator =(const Ptr& rhs)
{
	++*rhs.refptr;
	//free the left-hand side, destorying pointers if appropriate
	if(--*refptr==0)
	{
		delete refptr;
		delete p;
	}

	//copy in values from the right-hand side
	refptr=rhs.refptr;
	p=rhs.p;
	return *this;
}
template<class T>
Ptr<T>::~Ptr()
{
	if(--*refptr==0)
	{
		delete refptr;
		delete p;
	}
}

Vec<char>* clone(const Vec<char>* vp)
{
    return new Vec<char>(*vp);
}

class Str
{
	friend std::istream& operator>>(std::istream&,Str&);
	friend std::istream& getline(std::istream&,Str&);
public:
	operator bool(){return size()!=0?true:false;}
	Str& operator+=(const Str& s)
	{
		data.make_unique();
		std::copy(s.data->begin(),s.data->end(),std::back_inserter(*data));
		return *this;
	}

	//interface as before
	typedef Vec<char>::size_type size_type;

	//constructors to creator Ptrs
	Str():data(new Vec<char>){}
	Str(const char* cp):data(new Vec<char>)
	{
		std::copy(cp,cp+strlen(cp),std::back_inserter(*data));
	}
	Str(size_type n,char c):data(new Vec<char>(n,c)){}
	template<class In>
	Str(In i,In j):data(new Vec<char>)
	{
		std::copy(i,j,std::back_inserter(*data));
	}

	//call mack_unique as necessary
	char& operator[](size_type i)
	{
		data.make_unique();
		return (*data)[i];
	}
	const char& operator[](size_type i)const{return (*data)[i];}
	size_type size()const{return data->size();}

	const char* c_str() const;
	const char* c_date() const;
	const char* copy(char*,size_type) const;

	typedef Vec<char>::iterator iterator;
	typedef Vec<char>::const_iterator const_iterator;
	iterator begin(){return data->begin();}
	const_iterator begin() const {return data->begin();}
	iterator end(){return data->end();}
	const_iterator end() const {return data->end();}

private:
	//store a Ptr to a vector
	Ptr<Vec<char> > data;
};
std::ostream& operator<<(std::ostream& os, const Str& s)
{
	for(Str::size_type i=0;i<s.size();++i)
		os<<s[i];
	return os;
}
Str operator+(const Str& s,const Str& t)
{
	Str r=s;
	r+=t;
	return r;
}
std::istream& getline(std::istream& is,Str& s)
{
	//obliterate existing value (s)
	s.data->clear();

	//read and discard leading whitespace
	char c;
	while(is.get(c)&&isspace(c))
		;//nothing to do, except testing the condition
		//if still something to read, do so until next whitespace charactor
	if(is)
	{
		do
			s.data->push_back(c);	//compile error! data is private
		while(is.get(c)&&c!='\n');
	}
	return is;
}
const char* Str::copy(char* p,size_type n) const
{
	if(strlen(p)<n)
		throw "benefit!";
	else
	{
		std::copy(data->begin(),data->begin()+n,p);
		return p;
	}
}
const char* Str::c_str() const
{
	char* p=new char[size()];
	std::copy(data->begin(),data->end(),p);
	p[size()]=0;
	return p;
}
const char* Str::c_date() const
{
	char* p=new char[size()-1];
	std::copy(data->begin(),data->end(),p);
	return p;
}
int main()
{
	Str s1="cheng",s2=", ning";
	cout<<(s1+s2)[3]<<endl;
	Str s;
//	getline(cin,s);
//	cout<<s<<endl;
//	if(s)cout<<"Yes!"<<endl;	
	return 0;
}