// This is a replacement for std::vector (implementing only some
// of the functionality). I wrote it because the cost of VC++'s
// std::vector::push_back() was more than I could bear (>400
// bytes of inline code even for a simple vector of pointers).
// I'll probably drop it later.

#include <memory>


template<class T>
class Vector {
	T* v;
	unsigned long s,a;

	Vector(const Vector&);

#ifdef _MSC_VER
	friend void swap(Vector<T>& a, Vector<T>& b);
#else
	friend void swap<>(Vector<T>& a, Vector<T>& b);
#endif

	T* new_uninit(int n) { return reinterpret_cast<T*>(new char[n*sizeof(T)]); }
	void delete_uninit(T* p) { delete reinterpret_cast<char*>(p); }

	void destruct(T* first, T* last) {
		while (last > first) {
			--last;
			last->~T();
		}
	}

	void grow();

public:

	Vector() { v=0; s=0; a=0; }

	explicit Vector(int n, const T& t = T()) {
		v = new_uninit(a=s=n);
		std::uninitialized_fill_n(v, s, t);
	}

	~Vector() {
		destruct(v, v+s);
		delete_uninit(v);
	}

	void clear() {
		destruct(v, v+s);
		s = 0;
	}

	int size() const { return s; }

	T* begin() { return v; }
	T* end() { return v+s; }
	T& back() { return v[s-1]; }
	T& operator[](int i) { return v[i]; }

	const T* begin() const { return v; }
	const T* end() const { return v+s; }
	const T& back() const { return v[s-1]; }
	const T& operator[](int i) const { return v[i]; }

	void push_back(const T& e) {
		if (!(s < a)) {
			grow();
		}
		new (&v[s]) T(e);
		++s;
	}

	void pop_back() {
		--s;
		v[s].~T();
	}
};

template<class T>
void Vector<T>::grow() {
	a = a*2+1;
	T* n = new_uninit(a);
	std::uninitialized_copy(v, v+s, n);
	delete_uninit(v);
	v = n;
}

namespace std {

template<class T>
static inline void swap(Vector<T>& x, Vector<T>& y) {
	swap(x.v, y.v);
	swap(x.s, y.s);
	swap(x.a, y.a);
}

}