template <typename T>
class Vector {
public:
	Vector() {
		capacity = 100;
		size = 0;
		data = new T[capacity];
	}
	Vector(int capacity) {
		this->capacity = capacity;
		size = 0;
		data = new T[capacity];
	}
	~Vector()
	{
		delete[] data;
	}

	//добавляем в конец массива
	void Push(T value) {
		if (size + 1 > capacity) {
			capacity += 100;
			T* newMem = new T[capacity];
			memcpy(newMem, data, sizeof(T) * size);
			delete data;
			data = newMem;
		}

		data[size] = value;
		size++;
	}

	int Size() {
		return size;
	}

	T& operator[](int index) {
		return data[index];
	}

	void Remove(int index) {
		if ((size - 1) > 0) {
			memcpy(data + index, data + index + 1, (size - index - 1) * sizeof(T));
			// | здесь мы смещаем то что после
			//удаляемого элемента на его место;
		}
		size--;
	}

	void Insert(int index, T key) {
		if (size + 1 > capacity) {
			capacity += 100;
			T* t = new T[capacity];
			memcpy(t, data, size * sizeof(T));
			delete data; //очистка памяти
			data = t;
		}

		memcpy(data + index + 1, data + index, (size - index) * sizeof(T));
		data[index] = key;
		size++;
	}

	class Iterator {
	public:
		Iterator(T* cur) {
			current = cur;
		}

		bool operator!=(const Iterator& other) {
			return current != other.current;
		}

		Iterator& operator++() {
			current = ++current;
			return *this;
		}
		Iterator& operator++(int) {
			Iterator i = *this;
			current = ++current;
			return i;
		}

		T operator*() {
			return *current;
		}
	private:
		T* current;
	};

	class ReverseIterator {
	private:
		T* current;
	public:
		ReverseIterator(T* cur) {
			current = cur;
		}
		T operator*() {
			return *current;
		}

		bool operator!=(const ReverseIterator& other) {
			return current != other.current;
		}

		ReverseIterator& operator++() { //префикс
			current = --current;
			return *this;
		}

		ReverseIterator& operator++(int) { //постфикс
			ReverseIterator i = *this;
			current = --current;
			return i;
		}
	};

	Iterator Begin() {
		return Iterator(data);
	}
	Iterator End() {
		return Iterator(data + size);
	}
	ReverseIterator rBegin() {
		return ReverseIterator(data + size - 1);
	}
	ReverseIterator rEnd() {
		return ReverseIterator(data-1);
	}

private:
	int size;
	int capacity;
	T* data;
};