template <class T>
class simple_vector
{
private:

  // The vector maintains a dynamically allocated array to hold its data.
  // If more data that the array can hold is added to the vector, a new
  // larger array is allocated.
  // The following point to the first location in the array,
  // the first unused location in the array,
  // and the location one past the end of the array.
  T * start;
  T * finish;
  T * end_of_storage;

  // This function expands the storage available by allocating a new
  // array.  The size of the new array is given by the parameter, or
  // is double the size of the old array if no parameter is given.
  void expand(int new_len = 0)
  {
    // This is inefficient, since we first invoke the default constructor
    // for T in the new expression, and then later copy values from the old
    // array into each location in the new array.
    const int old_size = size();
    if (new_len == 0)
      new_len = (old_size == 0) ? 1 : 2 * old_size;
    T * new_start = new T[new_len];
    std::copy(start, finish, new_start);
    delete [] start;
    start = new_start;
    finish = new_start + old_size;
    end_of_storage = new_start + new_len;
  }

public:

  typedef T value_type;
  typedef T * iterator;
  typedef const T * const_iterator;

  iterator begin() { return start; }
  const_iterator begin() const { return start; }

  iterator end() { return finish; }
  const_iterator end() const { return finish; }

  int size() const { return finish - start; }

  int capacity() const { return end_of_storage - start; }

  bool empty() const { return start == finish; }

  T & operator[](int k) { return *(start + k); }
  const T & operator[](int k) const { return *(start + k); }

  simple_vector() : start(0), finish(0), end_of_storage(0) {}

  explicit simple_vector(int n)
  {
    start = new T[n];
    finish = start;
    end_of_storage = start + n;
  }

  explicit simple_vector(int n, const T & value) 
  {
    // This is inefficient, since we first invoke the default constructor
    // for T in the new expression, and then later assign values to
    // each location in the array.
    start = new T[n];
    finish = start + n;
    end_of_storage = start + n;
    std::fill(start, finish, value);
  }

  simple_vector(const simple_vector & x) 
  {
    // This is inefficient, since we first invoke the default constructor
    // for T in the new expression, and then later copy values from the other
    // vector into each location in the array.
    int n = x.size();
    start = new T[n];
    finish = start + n;
    end_of_storage = start + n;
    std::copy(x.start, x.finish, start);
  }

  ~simple_vector() 
  { 
    delete [] start;
  }

  simple_vector & operator=(const simple_vector & x)
  {
    // This is inefficient if we expand, since we copy the old data first
    // and then later copy over it with values from the other vector.
    if (&x != this) 
    {
      const int xlen = x.size();
      if (xlen > capacity()) 
        expand(xlen);
      std::copy(x.start, x.finish, start);
      finish = start + xlen;
    }
    return *this;
  }

  // Ensure that the vector can hold up to n items without requiring
  // the storage array to be made larger.
  void reserve(int n) 
  {
    if (capacity() < n) 
      expand(n);
  }

  T & front() { return *start; }
  const T & front() const { return *start; }

  T & back() { return *(finish - 1); }
  const T & back() const { return *(finish - 1); }

  void push_back(const T & x) 
  {
    if (finish == end_of_storage) 
      expand();
    *finish++ = x;
  }

  void swap(simple_vector & x) 
  {
    std::swap(start, x.start);
    std::swap(finish, x.finish);
    std::swap(end_of_storage, x.end_of_storage);
  }

  iterator insert(iterator position, const T & x) 
  {
    // This is inefficient, since we first copy elements as part of expand
    // and then later move elements over to make room to insert in the
    // new array.
    int n = position - start;
    if (finish == end_of_storage)
    {
      expand();
      // Note that expansion invalidates position.
      position = start + n;
    }
    std::copy_backward(position, finish, finish + 1);
    *position = x;
    ++finish;
    return position;
  }

  void pop_back() 
  {
    --finish;
  }

  iterator erase(iterator position) 
  {
    if (position + 1 != finish)
      std::copy(position + 1, finish, position);
    --finish;
    return position;
  }

  iterator erase(iterator first, iterator last) 
  {
    std::copy(last, finish, first);
    finish = finish - (last - first);
    return first;
  }

  void clear() { erase(start, finish); }
};

template <class T>
inline bool 
operator==(const simple_vector<T> & x, const simple_vector<T> & y)
{
  return x.size() == y.size() && std::equal(x.start, x.finish, y.start);
}

template <class T>
inline bool 
operator<(const simple_vector<T> & x, const simple_vector<T> & y)
{
  return std::lexicographical_compare(x.start, x.finish, y.start, y.finish);
}

template <class T>
inline void swap(simple_vector<T> & x, simple_vector<T> & y)
{
  x.swap(y);
}

template <class T>
inline bool
operator!=(const simple_vector<T> & x, const simple_vector<T> & y) 
{
  return !(x == y);
}

template <class T>
inline bool
operator>(const simple_vector<T> & x, const simple_vector<T> & y) 
{
  return y < x;
}

template <class T>
inline bool
operator<=(const simple_vector<T> & x, const simple_vector<T> & y) 
{
  return !(y < x);
}

template <class T>
inline bool
operator>=(const simple_vector<T> & x, const simple_vector<T> & y) 
{
  return !(x < y);
}