fork download
copy 
  1. #include <vector>
  2. #include <deque>
  3. #include <algorithm>
  4. #include <functional>
  5.  
  6. template <class T,class SizeType = std::size_t>
  7. class ArrayList{
  8.     std::vector<SizeType> Indexes;
  9. 	std::vector<T> Elements;
  10. 	std::deque<SizeType> Removes;
  11.  
  12. public:
  13. 	ArrayList(){}
  14.  
  15. 	bool Push_Back(const T& Item){
  16. 		SizeType Idx = 0;
  17.  
  18. 		if(Removes.size() != 0){
  19. 			Idx = Removes.front();
  20. 			Removes.pop_front();
  21. 		}else{
  22. 			Idx = Indexes.size();
  23. 		}
  24.  
  25. 		Indexes.push_back(Idx);
  26. 		if(Elements.size() <= Idx){
  27. 			Elements.push_back(Item);
  28. 		}else{
  29. 			Elements[Idx] = Item;
  30. 		}
  31. 			return true;
  32.  
  33. 	}
  34.  
  35. 	bool Erase(std::size_t Idx){
  36. 		SizeType I = Indexes[Idx];
  37. 		Indexes.erase((Indexes.begin()+Idx));
  38. 		Removes.push_back(I);
  39.  
  40. 		return true;
  41. 	}
  42.  
  43. 	bool GabageCollect(){//ここがわからん。。。
  44. 		std::sort(Removes.begin(),Removes.end(),std::less<SizeType>());
  45.  
  46. 		SizeType j=0,k=0,l = Removes.size();
  47. 		for(SizeType i=0;i<Indexes.size();i++){
  48. 			if(i == Removes[j]-l){
  49. 				j++;
  50. 				k++;
  51. 				//continue;
  52. 			}
  53. 			if(Indexes[i-k]>=i)Indexes[i-k]-=k;
  54.  
  55. 		}
  56.  
  57. 		std::for_each(Removes.begin(),Removes.end(),[&](SizeType Idx){Elements.erase(Elements.begin()+Idx);});
  58. 		Removes.clear();
  59.  
  60. 		return true;
  61. 	}
  62.  
  63. 	const SizeType Size(){
  64. 		return Indexes.size();
  65. 	}
  66. 	const SizeType Capacity(){
  67. 		return Elements.capacity();
  68. 	}
  69.  
  70. 	T& operator [](SizeType Idx){
  71. 		return Elements[Indexes[Idx]];
  72. 	}
  73. 	const T& operator [](SizeType Idx) const{
  74. 		return Elements[Indexes[Idx]];
  75. 	}
  76. };
  77. #include <iostream>
  78.  
  79. int main(){
  80. 	ArrayList<int> Array;
  81.  
  82. 	for(int i=0;i<8;i++){
  83. 		Array.Push_Back(i);
  84. 	}
  85.  
  86. 	Array.Erase(3);
  87. 	Array.Erase(4);
  88. 	Array.Erase(5);
  89. 	Array.Push_Back(9);
  90.  
  91. 	Array.GabageCollect();
  92.  
  93. 	for(int i=0;i<Array.Size();i++){
  94. 		std::cout<<Array[i]<<' '<<std::endl;
  95. 	}
  96.  
  97. 	return 0;
  98. }
Runtime error #stdin #stdout 0s 3036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WauTAF
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!