#include <memory>
#include <deque>

template<class T,class size_type = std::size_t>
class ArrayList{
    std::deque<std::shared_ptr<T>> Elements;
	std::deque<std::shared_ptr<T>> Removes;
public:
	typedef T Type;
	typedef size_type SizeType;
public:
	ArrayList(){}
	bool Push_Back(std::shared_ptr<T> Item){
		Elements.push_back(Item);
		return true;
	}	
	bool Push_Back(T* Item){//i need user called new object. do not delete Item by your hand.
		std::shared_ptr<T> ptr = std::shared_ptr<T>(Item);
		Elements.push_back(ptr);
		return true;
	}
	bool Push_Back(const T& Item){
		std::shared_ptr<T> ptr = std::shared_ptr<T>(nullptr);
		if(Removes.size() != 0){
			ptr = Removes.back();
			Removes.pop_back();
			*ptr = Item;
		}else{
			//ptr = std::shared_ptr<T>(new T(Item));
			ptr= std::make_shared<T>(Item);
		}

		Elements.push_back(ptr);

		return true;
	}
	const size_type Size() const{
		return Elements.size();
	}

	bool Erase(size_type Idx){
		Removes.push_back(Elements[Idx]);
		Elements.erase(Elements.begin()+Idx);
		return true;
	}
	bool GabageCollect(){
		Removes.clear();
		return true;
	}

	T& operator [](size_type Idx){
		return *(Elements[Idx].get());
	}
	std::shared_ptr<T> GetShared(size_type Idx){
		return Elements[Idx];
	}
};

#include <iostream>
//#include "ArrayList.h"

template<class T = int>
class TestObject{
	T i;
public:
	TestObject(const T& Item):i(Item){
		std::cout<<"construct:"<<Item<<std::endl;
	}
	const T& Get(){ return i;}
	virtual ~TestObject(){
		std::cout<<"Destruct:"<<i<<std::endl;
	}
};

int main(){
	typedef TestObject<int> TO;
	ArrayList<TO> Array;

	for(int i=0;i<8;i++){
		Array.Push_Back(new TO(i));
	}

	Array.Erase(3);
	Array.Erase(4);
	Array.Erase(5);

	Array.Push_Back(TO(8));
	Array.Push_Back(new TO(9));
	Array.Push_Back(std::make_shared<TO>(10));

	Array.GabageCollect();

	for(int i=0;i<Array.Size();i++){
		std::cout<<Array[i].Get()<<std::endl;
	}
	return 0;
}