List.h 3.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182
  1. #ifndef LIST_H
  2. #define LIST_H
  3. #include <new>
  4. #include <utility>
  5. #include "utils/StringBuffer.h"
  6. template<typename T>
  7. class List final {
  8. int length;
  9. int capacity;
  10. T* data;
  11. public:
  12. List() : length(0), capacity(0), data(nullptr) {
  13. }
  14. List(const List& other)
  15. : length(0), capacity(other.capacity), data(allocate(capacity)) {
  16. for(int i = 0; i < other.length; i++) {
  17. add(other[i]);
  18. }
  19. }
  20. List(List&& other) : List() {
  21. swap(other);
  22. }
  23. ~List() {
  24. clear();
  25. delete[] reinterpret_cast<char*>(data);
  26. }
  27. List& operator=(List other) {
  28. swap(other);
  29. return *this;
  30. }
  31. T* begin() {
  32. return data;
  33. }
  34. T* end() {
  35. return data + length;
  36. }
  37. const T* begin() const {
  38. return data;
  39. }
  40. const T* end() const {
  41. return data + length;
  42. }
  43. void reserve(int n) {
  44. if(n <= capacity) {
  45. return;
  46. }
  47. List copy;
  48. copy.capacity = n;
  49. copy.data = allocate(n);
  50. for(int i = 0; i < length; i++) {
  51. copy.add(std::move(data[i]));
  52. }
  53. swap(copy);
  54. }
  55. void resize(int n, const T& t) {
  56. if(length < n) {
  57. reserve(n);
  58. for(int i = length; i < n; i++) {
  59. add(t);
  60. }
  61. } else if(length > n) {
  62. for(int i = n; i < length; i++) {
  63. data[i].~T();
  64. }
  65. length = n;
  66. }
  67. }
  68. void resize(int n) {
  69. if(length < n) {
  70. reserve(n);
  71. for(int i = length; i < n; i++) {
  72. add(T());
  73. }
  74. } else if(length > n) {
  75. for(int i = n; i < length; i++) {
  76. data[i].~T();
  77. }
  78. length = n;
  79. }
  80. }
  81. List& add(const T& t) {
  82. ensureCapacity();
  83. new(data + length++) T(t);
  84. return *this;
  85. }
  86. List& add(T&& t) {
  87. ensureCapacity();
  88. new(data + length++) T(std::move(t));
  89. return *this;
  90. }
  91. template<typename... Args>
  92. List& add(Args&&... args) {
  93. ensureCapacity();
  94. new(data + length++) T(std::forward<Args>(args)...);
  95. return *this;
  96. }
  97. T& operator[](int index) {
  98. return data[index];
  99. }
  100. const T& operator[](int index) const {
  101. return data[index];
  102. }
  103. int getLength() const {
  104. return length;
  105. }
  106. void clear() {
  107. for(int i = 0; i < length; i++) {
  108. data[i].~T();
  109. }
  110. length = 0;
  111. }
  112. void removeBySwap(int index) {
  113. length--;
  114. if(index != length) {
  115. data[index] = std::move(data[length]);
  116. }
  117. data[length].~T();
  118. }
  119. void remove(int index) {
  120. length--;
  121. for(int i = index; i < length; i++) {
  122. data[i] = std::move(data[i + 1]);
  123. }
  124. data[length].~T();
  125. }
  126. template<int L>
  127. void toString(StringBuffer<L>& s) const {
  128. s.append("[");
  129. for(int i = 0; i < length - 1; i++) {
  130. s.append(data[i]);
  131. s.append(", ");
  132. }
  133. if(length > 0) {
  134. s.append(data[length - 1]);
  135. }
  136. s.append("]");
  137. }
  138. private:
  139. static T* allocate(int n) {
  140. return reinterpret_cast<T*>(new char[sizeof(T) * n]);
  141. }
  142. void swap(List& other) {
  143. std::swap(length, other.length);
  144. std::swap(capacity, other.capacity);
  145. std::swap(data, other.data);
  146. }
  147. void ensureCapacity() {
  148. if(length >= capacity) {
  149. reserve(capacity == 0 ? 8 : capacity * 2);
  150. }
  151. }
  152. };
  153. #endif