#include <vector>
#include <deque>
#include <algorithm>
#include <functional>

template <class T,class SizeType = std::size_t>
class ArrayList{
    std::vector<SizeType> Indexes;
	std::vector<T> Elements;
	std::deque<SizeType> Removes;

public:
	ArrayList(){}

	bool Push_Back(const T& Item){
		SizeType Idx = 0;
	
		if(Removes.size() != 0){
			Idx = Removes.front();
			Removes.pop_front();
		}else{
			Idx = Indexes.size();
		}
	
		Indexes.push_back(Idx);
		if(Elements.size() <= Idx){
			Elements.push_back(Item);
		}else{
			Elements[Idx] = Item;
		}
			return true;
	
	}

	bool Erase(std::size_t Idx){
		SizeType I = Indexes[Idx];
		Indexes.erase((Indexes.begin()+Idx));
		Removes.push_back(I);

		return true;
	}

	bool GabageCollect(){//ここがわからん。。。
		std::sort(Removes.begin(),Removes.end(),std::less<SizeType>());
		
		SizeType j=0,k=0,l = Removes.size();
		for(SizeType i=0;i<Indexes.size();i++){
			if(i == Removes[j]-l){
				j++;
				k++;
				//continue;
			}
			if(Indexes[i-k]>=i)Indexes[i-k]-=k;

		}

		std::for_each(Removes.begin(),Removes.end(),[&](SizeType Idx){Elements.erase(Elements.begin()+Idx);});
		Removes.clear();

		return true;
	}

	const SizeType Size(){
		return Indexes.size();
	}
	const SizeType Capacity(){
		return Elements.capacity();
	}

	T& operator [](SizeType Idx){
		return Elements[Indexes[Idx]];
	}
	const T& operator [](SizeType Idx) const{
		return Elements[Indexes[Idx]];
	}
};
#include <iostream>

int main(){
	ArrayList<int> Array;

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

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

	Array.GabageCollect();

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

	return 0;
}