Return to Question

Having already attempted an implementation of the std::vector class here, I decided to take the comments on board and also do some new bits myself (mainly the algorithms for allocation and insert).

Having already attempted an implementation of the std::vector class here, I decided to take the comments on board and also do some new bits myself (mainly the algorithms for allocation and insert).

# ifndef __VECTOR_H__
# define __VECTOR_H__
# include <memory>
# include <algorithm>
template<typename T,
 typename A>
 class vector;
template<typename B, 
 typename R>
 class vector_iterator;
template<typename I>
 class vector_reverse_iterator;
template<typename A>
 class vector_base
 {
public:
 typedef vector_base<A> base_type;
 typedef typename A allocator_type;
 typedef typename A::pointer pointer;
 friend class vector<typename A::value_type, A>;
 friend class vector_iterator<base_type, typename A::reference>;
 friend class vector_iterator<base_type, typename A::const_reference>;
 friend class vector_reverse_iterator<vector_iterator<base_type, typename A::reference> >;
 friend class vector_reverse_iterator<vector_iterator<base_type, typename A::const_reference> >;
private:
 vector_base(allocator_type const &al)
 : ms_begin(pointer()),
 s_end(pointer()),
 m_end(pointer()),
 alloc(al)
 {
 }
 ~vector_base()
 {
 }
 base_type *get_base()
 {
 return (this);
 }
 pointer ms_begin, s_end, m_end;
 allocator_type alloc;
 };
# ifndef VECTOR_ITERATOR_CHECK_LEVEL
# define VECTOR_ITERATOR_CHECK_LEVEL 1
# endif
template<typename B,
 typename R = typename B::allocator_type::reference>
 class vector_iterator
 {
public:
 typedef vector_iterator<B, R> this_t;
 typedef B base_type;
 typedef typename B::allocator_type::pointer pointer;
 typedef typename R reference;
 typedef typename B::allocator_type::const_reference const_reference;
 typedef typename B::allocator_type::value_type value_type;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type;
 typedef std::random_access_iterator_tag iterator_category;
 friend class vector<value_type, typename B::allocator_type>;
 friend class vector_reverse_iterator<this_t>;
 friend class vector_reverse_iterator<vector_iterator<B, const_reference> >;
 friend class vector_iterator<B, const_reference>;
 vector_iterator(base_type *b, pointer p)
 : base(b),
 ptr(p)
 {
 }
 template<typename R = reference>
 vector_iterator(vector_iterator<B, R> const &rhs)
 : base(rhs.base),
 ptr(rhs.ptr)
 {
 }
 ~vector_iterator()
 {
 }
 this_t &operator=(this_t const &rhs)
 {
 base = rhs.base;
 ptr = rhs.ptr;
 return (*this);
 }
 this_t &operator++()
 {
 ++ptr;
 return (*this);
 }
 this_t operator++(int)
 {
 this_t temp(*this);
 ++ptr;
 return (temp);
 }
 this_t &operator--()
 {
 --ptr;
 return (*this);
 }
 this_t operator--(int)
 {
 this_t temp(*this);
 --ptr;
 return (temp);
 }
 this_t operator+(size_type offset) const
 {
 return (this_t(base, ptr + offset));
 }
 this_t operator-(size_type offset) const
 {
 return (this_t(base, ptr - offset));
 }
 difference_type operator-(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr - rhs.ptr);
 }
 this_t &operator+=(size_type offset)
 {
 ptr += offset;
 return (*this);
 }
 this_t &operator-=(size_type offset)
 {
 ptr -= offset;
 return (*this);
 }
 reference operator*() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (*ptr);
 }
 reference operator[](size_type offset) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(this_t(base, ptr + offset), ptr_in_seq);
# endif
 return (*(ptr + offset));
 }
 pointer operator->() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (ptr);
 }
 bool operator==(this_t const &rhs) const
 {
 return (ptr == rhs.ptr);
 }
 bool operator!=(this_t const &rhs) const
 {
 return (!((*this) == rhs));
 }
 bool operator<(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr < rhs.ptr);
 }
 bool operator>(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr > rhs.ptr);
 }
 bool operator<=(this_t const &rhs) const
 {
 return (!(ptr > rhs.ptr));
 }
 bool operator>=(this_t const &rhs) const
 {
 return (!(ptr < rhs.ptr));
 }
private:
 pointer ptr;
 base_type *base;
 static void check_validity(this_t const &it, bool (*test)(this_t const &))
 {
 if (!test(it))
 {
 throw std::exception("iterator out of range");
 }
 }
 void check_compatible(this_t const &it) const
 {
 if (it.base != base)
 {
 throw std::exception("iterators incompatible (not in same container)");
 }
 }
 static bool ptr_in_seq(this_t const &it)
 {
 return (it.ptr >= it.base->ms_begin && 
 it.ptr < it.base->s_end);
 }
 static bool ptr_in_seq_or_end(this_t const &it)
 {
 return (it.ptr >= it.base->ms_begin && 
 it.ptr <= it.base->s_end);
 }
 };
template<typename I>
 class vector_reverse_iterator
 {
public:
 typedef vector_reverse_iterator<I> this_t;
 typedef typename I::base_type base_type;
 typedef typename I::pointer pointer;
 typedef typename I::reference reference;
 typedef typename I::const_reference const_reference;
 typedef typename I::size_type size_type;
 typedef typename I::difference_type difference_type;
 friend class vector_reverse_iterator<vector_iterator<base_type, const_reference> >;
 vector_reverse_iterator(I const &it)
 : base(it.base)
 {
 size_type from_begin = (it.ptr - it.base->ms_begin) + 1;
 ptr = (it.base->s_end - from_begin);
 }
 template<typename R = reference>
 vector_reverse_iterator(vector_reverse_iterator<
 vector_iterator<base_type, R> > const &rhs)
 : base(rhs.base),
 ptr(rhs.ptr)
 {
 }
 ~vector_reverse_iterator()
 {
 }
 this_t &operator=(this_t const &rhs)
 {
 base = rhs.base;
 ptr = rhs.ptr;
 return (*this);
 }
 this_t &operator++()
 {
 --ptr;
 return (*this);
 }
 this_t operator++(int)
 {
 this_t temp(*this);
 --ptr;
 return (temp);
 }
 this_t &operator--()
 {
 ++ptr;
 return (*this);
 }
 this_t operator--(int)
 {
 this_t temp(*this);
 ++ptr;
 return (temp);
 }
 this_t operator+(size_type offset) const
 {
 return (this_t(base, ptr - offset));
 }
 this_t operator-(size_type offset) const
 {
 return (this_t(base, ptr + offset));
 }
 difference_type operator-(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (rhs.ptr - ptr);
 }
 this_t &operator+=(size_type offset)
 {
 ptr -= offset;
 return (*this);
 }
 this_t &operator-=(size_type offset)
 {
 ptr += offset;
 return (*this);
 }
 reference operator*() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (*ptr);
 }
 reference operator[](size_type offset) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(this_t(base, ptr - offset), ptr_in_seq);
# endif
 return (*(ptr + offset));
 }
 pointer operator->() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (ptr);
 }
 bool operator==(this_t const &rhs) const
 {
 return (ptr == rhs.ptr);
 }
 bool operator!=(this_t const &rhs) const
 {
 return (!((*this) == rhs));
 }
 bool operator<(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr > rhs.ptr);
 }
 bool operator>(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr < rhs.ptr);
 }
 bool operator<=(this_t const &rhs) const
 {
 return (!(ptr < rhs.ptr));
 }
 bool operator>=(this_t const &rhs) const
 {
 return (!(ptr > rhs.ptr));
 }
private:
 pointer ptr;
 base_type *base;
 static void check_validity(this_t const &it, bool (*test)(this_t const &))
 {
 if (!test(it))
 {
 throw std::exception("iterator out of range");
 }
 }
 void check_compatible(this_t const &it) const
 {
 if (it.base != base)
 {
 throw std::exception("iterators incompatible (not in same container)");
 }
 }
 static bool ptr_in_seq(this_t const &it)
 {
 return (it.ptr > (it.base->ms_begin - 1) && 
 it.ptr <= (it.base->s_end - 1));
 }
 static bool ptr_in_seq_or_end(this_t const &it)
 {
 return (it.ptr >= (it.base->ms_begin - 1) && 
 it.ptr <= (it.base->s_end - 1));
 }
 };
template<typename T,
 typename A = std::allocator<T> >
 class vector
 : public vector_base<A>
 {
public:
 typedef typename A::value_type value_type;
 typedef typename A::const_pointer const_pointer;
 typedef typename A::reference reference;
 typedef typename A::const_reference const_reference;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type;
 typedef vector_iterator<base_type> iterator;
 typedef vector_iterator<base_type, const_reference> const_iterator;
 typedef vector_reverse_iterator<iterator> reverse_iterator;
 typedef vector_reverse_iterator<const_iterator> const_reverse_iterator;
 typedef vector<T, A> this_t;
 explicit vector(allocator_type const &al = allocator_type())
 : base_type(al)
 {
 }
 explicit vector(size_type count, const_reference value = value_type(),
 allocator_type const &al = allocator_type())
 : base_type(al)
 {
 assign(count, value);
 }
 template<typename InIt>
 vector(typename std::enable_if<!std::is_integral<InIt>::value, InIt> first,
 typename std::enable_if<!std::is_integral<InIt>::value, InIt> last,
 allocator_type const &al = allocator_type())
 : base_type(al)
 {
 assign(first, last);
 }
 vector(this_t const &rhs)
 : base_type(rhs.alloc)
 {
 if(&rhs != this)
 {
 assign(rhs.ms_begin, rhs.s_end);
 }
 }
 void assign(size_type count, value_type const &value = value_type())
 {
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (count > capacity())
 {
 reallocate(count * 1.5);
 }
 wipe_values();
 }
 this->s_end = std::uninitialized_fill_n(
 this->ms_begin, count, value);
 }
 template<typename InIt>
 typename std::enable_if<!std::is_integral<InIt>::value, void>::type assign(InIt first, InIt last)
 {
 difference_type count = (last - first);
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (count > capacity())
 {
 reallocate(count * 1.5);
 }
 wipe_values();
 }
 this->s_end = std::uninitialized_copy(
 first, last, this->ms_begin);
 }
 iterator erase(iterator where)
 {
 return (erase(where, where + 1));
 }
 iterator erase(iterator first, iterator last)
 {
 iterator::check_validity(first, iterator::ptr_in_seq);
 iterator::check_validity(last, iterator::ptr_in_seq_or_end);
 difference_type diff = (last - first);
 size_type fpos = (first.ptr - this->ms_begin), 
 lpos = (last.ptr - this->ms_begin);
 std::rotate(this->ms_begin + fpos, this->ms_begin + lpos, this->s_end);
 while (diff--)
 {
 this->alloc.destroy(--this->s_end);
 }
 return (iterator(this->get_base(), this->ms_begin + (lpos - (last - first))));
 }
 void insert(iterator where, const value_type &value = value_type())
 {
 insert(where, 1, value);
 }
 void insert(iterator where, unsigned count, const value_type &value = value_type())
 {
 iterator::check_validity(where, iterator::ptr_in_seq_or_end);
 size_type wpos = (where.ptr - this->ms_begin)
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (size() + count > capacity())
 {
 reallocate((size() + count) * 1.5);
 }
 }
 size_type c2 = count;
 while (c2--)
 {
 this->alloc.construct(this->s_end++, value);
 }
 std::rotate(this->ms_begin + wpos, this->s_end - count, this->s_end);
 }
 template<typename InIt>
 typename std::enable_if<!std::is_integral<InIt>::value, void>::type insert(iterator where, InIt first, InIt last)
 {
 iterator::check_validity(where, iterator::ptr_in_seq_or_end);
 size_type wpos = (where.ptr - this->ms_begin);
 difference_type diff = (last - first);
 if (is_unconstructed())
 {
 allocate(diff * 1.5);
 }
 else
 {
 if (size() + diff > capacity())
 {
 reallocate((size() + diff) * 1.5);
 }
 }
 while (first != last)
 {
 this->alloc.construct(this->s_end++, first++);
 }
 std::rotate(this->ms_begin + wpos, this->s_end - diff, this->s_end);
 }
 void push_back(value_type const &value)
 {
 insert(end(), value);
 }
 void pop_back()
 {
 erase(end() - 1);
 }
 void clear()
 {
 erase(begin(), end());
 }
 iterator begin()
 {
 return (iterator(this->get_base(), this->ms_begin));
 }
 iterator end()
 {
 return (iterator(this->get_base(), this->s_end));
 }
 const_iterator begin() const
 {
 return (const_iterator(this->get_base(), this->ms_begin));
 }
 const_iterator end() const
 {
 return (const_iterator(this->get_base(), this->s_end));
 }
 reverse_iterator rbegin()
 {
 return (reverse_iterator(begin()));
 }
 reverse_iterator rend()
 {
 return (reverse_iterator(end()));
 }
 const_reverse_iterator rbegin() const
 {
 return (const_reverse_iterator(begin()));
 }
 const_reverse_iterator rend() const
 {
 return (const_reverse_iterator(end()));
 }
 reference operator[](size_type offset)
 {
 return (*(this->ms_begin + offset));
 }
 const_reference operator[](size_type offset) const
 {
 return (*(this->ms_begin + offset));
 }
 reference front()
 {
 return (*this->ms_begin);
 }
 const_reference front() const
 {
 return (*this->ms_begin);
 }
 reference back()
 {
 return (*(this->s_end - 1));
 }
 const_reference back() const
 {
 return (*(this->s_end - 1));
 }
 reference at(size_type offset)
 {
 if (offset >= size())
 {
 throw std::exception("offset out of bounds");
 }
 return (*(this->ms_begin + offset));
 }
 
 const_reference at(size_type offset) const
 {
 if (offset >= size())
 {
 throw std::exception("offset out of bounds");
 }
 return (*(this->ms_begin + offset));
 }
 void reserve(size_type count)
 {
 if (count > capacity())
 {
 reallocate(count);
 }
 }
 void resize(size_type count, value_type value = value_type())
 {
 if (count < size())
 {
 erase(begin() + count, end());
 }
 else
 {
 reserve(count);
 insert(end(), count - size(), value);
 }
 }
 void swap(this_t &rhs)
 {
 base_type b = *(this->get_base());
 *(this->get_base()) = *(rhs.get_base());
 *(rhs.get_base()) = b;
 }
 size_type size() const
 {
 return (this->s_end - this->ms_begin);
 }
 size_type capacity() const
 {
 return (this->m_end - this->ms_begin);
 }
 allocator_type get_allocator() const
 {
 return (this->alloc);
 }
 bool empty() const
 {
 return (this->ms_begin == this->s_end);
 }
private:
 void allocate(size_type count)
 {
 if (count > this->alloc.max_size())
 {
 throw std::exception("unable to allocate memory");
 }
 this->ms_begin = this->alloc.allocate(count);
 this->s_end = this->ms_begin;
 this->m_end = this->ms_begin + count;
 }
 void reallocate(size_type count)
 {
 if (count > this->alloc.max_size())
 {
 throw std::exception("unable to allocate memory");
 }
 pointer nbegin = this->alloc.allocate(count);
 std::uninitialized_copy(this->ms_begin, this->s_end, nbegin);
 size_type sz = size();
 wipe_all();
 this->ms_begin = nbegin;
 this->s_end = nbegin + sz;
 this->m_end = nbegin + count;
 }
 void wipe_values()
 {
 if (!is_unconstructed())
 {
 size_type sz = size();
 while (this->ms_begin != this->s_end)
 {
 this->alloc.destroy(this->ms_begin++);
 }
 this->ms_begin -= sz;
 }
 }
 void wipe_all()
 {
 if (!is_unconstructed())
 {
 wipe_values();
 this->alloc.deallocate(this->ms_begin, capacity());
 this->ms_begin = pointer();
 this->s_end = pointer();
 this->m_end = pointer();
 }
 }
 bool is_unconstructed() const
 {
 return (this->ms_begin == pointer());
 }
 };
# endif

# ifndef __VECTOR_H__
# define __VECTOR_H__
# include <memory>
# include <algorithm>
template<typename T,
 typename A>
 class vector;
template<typename B, 
 typename R>
 class vector_iterator;
template<typename I>
 class vector_reverse_iterator;
template<typename A>
 class vector_base
 {
public:
 typedef vector_base<A> base_type;
 typedef typename A allocator_type;
 typedef typename A::pointer pointer;
 friend class vector<typename A::value_type, A>;
 friend class vector_iterator<base_type, typename A::reference>;
 friend class vector_iterator<base_type, typename A::const_reference>;
 friend class vector_reverse_iterator<vector_iterator<base_type, typename A::reference> >;
 friend class vector_reverse_iterator<vector_iterator<base_type, typename A::const_reference> >;
private:
 vector_base(allocator_type const &al)
 : ms_begin(pointer()),
 s_end(pointer()),
 m_end(pointer()),
 alloc(al)
 {
 }
 ~vector_base()
 {
 }
 base_type *get_base()
 {
 return (this);
 }
 pointer ms_begin, s_end, m_end;
 allocator_type alloc;
 };
# ifndef VECTOR_ITERATOR_CHECK_LEVEL
# define VECTOR_ITERATOR_CHECK_LEVEL 1
# endif
template<typename B,
 typename R = typename B::allocator_type::reference>
 class vector_iterator
 {
public:
 typedef vector_iterator<B, R> this_t;
 typedef B base_type;
 typedef typename B::allocator_type::pointer pointer;
 typedef typename R reference;
 typedef typename B::allocator_type::const_reference const_reference;
 typedef typename B::allocator_type::value_type value_type;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type;
 typedef std::random_access_iterator_tag iterator_category;
 friend class vector<value_type, typename B::allocator_type>;
 friend class vector_reverse_iterator<this_t>;
 friend class vector_reverse_iterator<vector_iterator<B, const_reference> >;
 friend class vector_iterator<B, const_reference>;
 vector_iterator(base_type *b, pointer p)
 : base(b),
 ptr(p)
 {
 }
 template<typename R = reference>
 vector_iterator(vector_iterator<B, R> const &rhs)
 : base(rhs.base),
 ptr(rhs.ptr)
 {
 }
 ~vector_iterator()
 {
 }
 this_t &operator=(this_t const &rhs)
 {
 base = rhs.base;
 ptr = rhs.ptr;
 return (*this);
 }
 this_t &operator++()
 {
 ++ptr;
 return (*this);
 }
 this_t operator++(int)
 {
 this_t temp(*this);
 ++ptr;
 return (temp);
 }
 this_t &operator--()
 {
 --ptr;
 return (*this);
 }
 this_t operator--(int)
 {
 this_t temp(*this);
 --ptr;
 return (temp);
 }
 this_t operator+(size_type offset) const
 {
 return (this_t(base, ptr + offset));
 }
 this_t operator-(size_type offset) const
 {
 return (this_t(base, ptr - offset));
 }
 difference_type operator-(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr - rhs.ptr);
 }
 this_t &operator+=(size_type offset)
 {
 ptr += offset;
 return (*this);
 }
 this_t &operator-=(size_type offset)
 {
 ptr -= offset;
 return (*this);
 }
 reference operator*() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (*ptr);
 }
 reference operator[](size_type offset) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(this_t(base, ptr + offset), ptr_in_seq);
# endif
 return (*(ptr + offset));
 }
 pointer operator->() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (ptr);
 }
 bool operator==(this_t const &rhs) const
 {
 return (ptr == rhs.ptr);
 }
 bool operator!=(this_t const &rhs) const
 {
 return (!((*this) == rhs));
 }
 bool operator<(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr < rhs.ptr);
 }
 bool operator>(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr > rhs.ptr);
 }
 bool operator<=(this_t const &rhs) const
 {
 return (!(ptr > rhs.ptr));
 }
 bool operator>=(this_t const &rhs) const
 {
 return (!(ptr < rhs.ptr));
 }
private:
 pointer ptr;
 base_type *base;
 static void check_validity(this_t const &it, bool (*test)(this_t const &))
 {
 if (!test(it))
 {
 throw std::exception("iterator out of range");
 }
 }
 void check_compatible(this_t const &it) const
 {
 if (it.base != base)
 {
 throw std::exception("iterators incompatible (not in same container)");
 }
 }
 static bool ptr_in_seq(this_t const &it)
 {
 return (it.ptr >= it.base->ms_begin && 
 it.ptr < it.base->s_end);
 }
 static bool ptr_in_seq_or_end(this_t const &it)
 {
 return (it.ptr >= it.base->ms_begin && 
 it.ptr <= it.base->s_end);
 }
 };
template<typename I>
 class vector_reverse_iterator
 {
public:
 typedef vector_reverse_iterator<I> this_t;
 typedef typename I::base_type base_type;
 typedef typename I::pointer pointer;
 typedef typename I::reference reference;
 typedef typename I::const_reference const_reference;
 typedef typename I::size_type size_type;
 typedef typename I::difference_type difference_type;
 friend class vector_reverse_iterator<vector_iterator<base_type, const_reference> >;
 vector_reverse_iterator(I const &it)
 : base(it.base)
 {
 size_type from_begin = (it.ptr - it.base->ms_begin) + 1;
 ptr = (it.base->s_end - from_begin);
 }
 template<typename R = reference>
 vector_reverse_iterator(vector_reverse_iterator<
 vector_iterator<base_type, R> > const &rhs)
 : base(rhs.base),
 ptr(rhs.ptr)
 {
 }
 ~vector_reverse_iterator()
 {
 }
 this_t &operator=(this_t const &rhs)
 {
 base = rhs.base;
 ptr = rhs.ptr;
 return (*this);
 }
 this_t &operator++()
 {
 --ptr;
 return (*this);
 }
 this_t operator++(int)
 {
 this_t temp(*this);
 --ptr;
 return (temp);
 }
 this_t &operator--()
 {
 ++ptr;
 return (*this);
 }
 this_t operator--(int)
 {
 this_t temp(*this);
 ++ptr;
 return (temp);
 }
 this_t operator+(size_type offset) const
 {
 return (this_t(base, ptr - offset));
 }
 this_t operator-(size_type offset) const
 {
 return (this_t(base, ptr + offset));
 }
 difference_type operator-(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (rhs.ptr - ptr);
 }
 this_t &operator+=(size_type offset)
 {
 ptr -= offset;
 return (*this);
 }
 this_t &operator-=(size_type offset)
 {
 ptr += offset;
 return (*this);
 }
 reference operator*() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (*ptr);
 }
 reference operator[](size_type offset) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(this_t(base, ptr - offset), ptr_in_seq);
# endif
 return (*(ptr + offset));
 }
 pointer operator->() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (ptr);
 }
 bool operator==(this_t const &rhs) const
 {
 return (ptr == rhs.ptr);
 }
 bool operator!=(this_t const &rhs) const
 {
 return (!((*this) == rhs));
 }
 bool operator<(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr > rhs.ptr);
 }
 bool operator>(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr < rhs.ptr);
 }
 bool operator<=(this_t const &rhs) const
 {
 return (!(ptr < rhs.ptr));
 }
 bool operator>=(this_t const &rhs) const
 {
 return (!(ptr > rhs.ptr));
 }
private:
 pointer ptr;
 base_type *base;
 static void check_validity(this_t const &it, bool (*test)(this_t const &))
 {
 if (!test(it))
 {
 throw std::exception("iterator out of range");
 }
 }
 void check_compatible(this_t const &it) const
 {
 if (it.base != base)
 {
 throw std::exception("iterators incompatible (not in same container)");
 }
 }
 static bool ptr_in_seq(this_t const &it)
 {
 return (it.ptr > (it.base->ms_begin - 1) && 
 it.ptr <= (it.base->s_end - 1));
 }
 static bool ptr_in_seq_or_end(this_t const &it)
 {
 return (it.ptr >= (it.base->ms_begin - 1) && 
 it.ptr <= (it.base->s_end - 1));
 }
 };
template<typename T,
 typename A = std::allocator<T> >
 class vector
 : public vector_base<A>
 {
public:
 typedef typename A::value_type value_type;
 typedef typename A::const_pointer const_pointer;
 typedef typename A::reference reference;
 typedef typename A::const_reference const_reference;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type;
 typedef vector_iterator<base_type> iterator;
 typedef vector_iterator<base_type, const_reference> const_iterator;
 typedef vector_reverse_iterator<iterator> reverse_iterator;
 typedef vector_reverse_iterator<const_iterator> const_reverse_iterator;
 typedef vector<T, A> this_t;
 explicit vector(allocator_type const &al = allocator_type())
 : base_type(al)
 {
 }
 explicit vector(size_type count, const_reference value = value_type(),
 allocator_type const &al = allocator_type())
 : base_type(al)
 {
 assign(count, value);
 }
 template<typename InIt>
 vector(typename std::enable_if<!std::is_integral<InIt>::value, InIt> first,
 typename std::enable_if<!std::is_integral<InIt>::value, InIt> last,
 allocator_type const &al = allocator_type())
 : base_type(al)
 {
 assign(first, last);
 }
 vector(this_t const &rhs)
 : base_type(rhs.alloc)
 {
 if(&rhs != this)
 {
 assign(rhs.ms_begin, rhs.s_end);
 }
 }
 void assign(size_type count, value_type const &value = value_type())
 {
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (count > capacity())
 {
 reallocate(count * 1.5);
 }
 wipe_values();
 }
 this->s_end = std::uninitialized_fill_n(
 this->ms_begin, count, value);
 }
 template<typename InIt>
 typename std::enable_if<!std::is_integral<InIt>::value, void>::type assign(InIt first, InIt last)
 {
 difference_type count = (last - first);
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (count > capacity())
 {
 reallocate(count * 1.5);
 }
 wipe_values();
 }
 this->s_end = std::uninitialized_copy(
 first, last, this->ms_begin);
 }
 this_t &operator=(this_t const &rhs)
 {
 if (&rhs != this)
 {
 assign(rhs.ms_begin, rhs.s_end);
 }
 return (*this);
 }
 iterator erase(iterator where)
 {
 return (erase(where, where + 1));
 }
 iterator erase(iterator first, iterator last)
 {
 iterator::check_validity(first, iterator::ptr_in_seq);
 iterator::check_validity(last, iterator::ptr_in_seq_or_end);
 difference_type diff = (last - first);
 size_type fpos = (first.ptr - this->ms_begin), 
 lpos = (last.ptr - this->ms_begin);
 std::rotate(this->ms_begin + fpos, this->ms_begin + lpos, this->s_end);
 while (diff--)
 {
 this->alloc.destroy(--this->s_end);
 }
 return (iterator(this->get_base(), this->ms_begin + (lpos - (last - first))));
 }
 void insert(iterator where, const value_type &value = value_type())
 {
 insert(where, 1, value);
 }
 void insert(iterator where, unsigned count, const value_type &value = value_type())
 {
 iterator::check_validity(where, iterator::ptr_in_seq_or_end);
 size_type wpos = (where.ptr - this->ms_begin);
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (size() + count > capacity())
 {
 reallocate((size() + count) * 1.5);
 }
 }
 size_type c2 = count;
 while (c2--)
 {
 this->alloc.construct(this->s_end++, value);
 }
 std::rotate(this->ms_begin + wpos, this->s_end - count, this->s_end);
 }
 template<typename InIt>
 typename std::enable_if<!std::is_integral<InIt>::value, void>::type insert(iterator where, InIt first, InIt last)
 {
 iterator::check_validity(where, iterator::ptr_in_seq_or_end);
 size_type wpos = (where.ptr - this->ms_begin);
 difference_type diff = (last - first);
 if (is_unconstructed())
 {
 allocate(diff * 1.5);
 }
 else
 {
 if (size() + diff > capacity())
 {
 reallocate((size() + diff) * 1.5);
 }
 }
 while (first != last)
 {
 this->alloc.construct(this->s_end++, first++);
 }
 std::rotate(this->ms_begin + wpos, this->s_end - diff, this->s_end);
 }
 void push_back(value_type const &value)
 {
 insert(end(), value);
 }
 void pop_back()
 {
 erase(end() - 1);
 }
 void clear()
 {
 erase(begin(), end());
 }
 iterator begin()
 {
 return (iterator(this->get_base(), this->ms_begin));
 }
 iterator end()
 {
 return (iterator(this->get_base(), this->s_end));
 }
 const_iterator begin() const
 {
 return (const_iterator(this->get_base(), this->ms_begin));
 }
 const_iterator end() const
 {
 return (const_iterator(this->get_base(), this->s_end));
 }
 reverse_iterator rbegin()
 {
 return (reverse_iterator(begin()));
 }
 reverse_iterator rend()
 {
 return (reverse_iterator(end()));
 }
 const_reverse_iterator rbegin() const
 {
 return (const_reverse_iterator(begin()));
 }
 const_reverse_iterator rend() const
 {
 return (const_reverse_iterator(end()));
 }
 reference operator[](size_type offset)
 {
 return (*(this->ms_begin + offset));
 }
 const_reference operator[](size_type offset) const
 {
 return (*(this->ms_begin + offset));
 }
 reference front()
 {
 return (*this->ms_begin);
 }
 const_reference front() const
 {
 return (*this->ms_begin);
 }
 reference back()
 {
 return (*(this->s_end - 1));
 }
 const_reference back() const
 {
 return (*(this->s_end - 1));
 }
 reference at(size_type offset)
 {
 if (offset >= size())
 {
 throw std::exception("offset out of bounds");
 }
 return (*(this->ms_begin + offset));
 }
 
 const_reference at(size_type offset) const
 {
 if (offset >= size())
 {
 throw std::exception("offset out of bounds");
 }
 return (*(this->ms_begin + offset));
 }
 void reserve(size_type count)
 {
 if (count > capacity())
 {
 reallocate(count);
 }
 }
 void resize(size_type count, value_type value = value_type())
 {
 if (count < size())
 {
 erase(begin() + count, end());
 }
 else
 {
 reserve(count);
 insert(end(), count - size(), value);
 }
 }
 void swap(this_t &rhs)
 {
 base_type b = *(this->get_base());
 *(this->get_base()) = *(rhs.get_base());
 *(rhs.get_base()) = b;
 }
 size_type size() const
 {
 return (this->s_end - this->ms_begin);
 }
 size_type capacity() const
 {
 return (this->m_end - this->ms_begin);
 }
 allocator_type get_allocator() const
 {
 return (this->alloc);
 }
 bool empty() const
 {
 return (this->ms_begin == this->s_end);
 }
private:
 void allocate(size_type count)
 {
 if (count > this->alloc.max_size())
 {
 throw std::exception("unable to allocate memory");
 }
 this->ms_begin = this->alloc.allocate(count);
 this->s_end = this->ms_begin;
 this->m_end = this->ms_begin + count;
 }
 void reallocate(size_type count)
 {
 if (count > this->alloc.max_size())
 {
 throw std::exception("unable to allocate memory");
 }
 pointer nbegin = this->alloc.allocate(count);
 std::uninitialized_copy(this->ms_begin, this->s_end, nbegin);
 size_type sz = size();
 wipe_all();
 this->ms_begin = nbegin;
 this->s_end = nbegin + sz;
 this->m_end = nbegin + count;
 }
 void wipe_values()
 {
 if (!is_unconstructed())
 {
 size_type sz = size();
 while (this->ms_begin != this->s_end)
 {
 this->alloc.destroy(this->ms_begin++);
 }
 this->ms_begin -= sz;
 }
 }
 void wipe_all()
 {
 if (!is_unconstructed())
 {
 wipe_values();
 this->alloc.deallocate(this->ms_begin, capacity());
 this->ms_begin = pointer();
 this->s_end = pointer();
 this->m_end = pointer();
 }
 }
 bool is_unconstructed() const
 {
 return (this->ms_begin == pointer());
 }
 };
# endif

# ifndef __VECTOR_H__
# define __VECTOR_H__
# include <memory>
# include <algorithm>
template<typename T,
 typename A>
 class vector;
template<typename B, 
 typename R>
 class vector_iterator;
template<typename I>
 class vector_reverse_iterator;
template<typename A>
 class vector_base
 {
public:
 typedef vector_base<A> base_type;
 typedef typename A allocator_type;
 typedef typename A::pointer pointer;
 friend class vector<typename A::value_type, A>;
 friend class vector_iterator<base_type, typename A::reference>;
 friend class vector_iterator<base_type, typename A::const_reference>;
 friend class vector_reverse_iterator<vector_iterator<base_type, typename A::reference> >;
 friend class vector_reverse_iterator<vector_iterator<base_type, typename A::const_reference> >;
private:
 vector_base(allocator_type const &al)
 : ms_begin(pointer()),
 s_end(pointer()),
 m_end(pointer()),
 alloc(al)
 {
 }
 ~vector_base()
 {
 }
 base_type *get_base()
 {
 return (this);
 }
 pointer ms_begin, s_end, m_end;
 allocator_type alloc;
 };
# ifndef VECTOR_ITERATOR_CHECK_LEVEL
# define VECTOR_ITERATOR_CHECK_LEVEL 1
# endif
template<typename B,
 typename R = typename B::allocator_type::reference>
 class vector_iterator
 {
public:
 typedef vector_iterator<B, R> this_t;
 typedef B base_type;
 typedef typename B::allocator_type::pointer pointer;
 typedef typename R reference;
 typedef typename B::allocator_type::const_reference const_reference;
 typedef typename B::allocator_type::value_type value_type;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type;
 typedef std::random_access_iterator_tag iterator_category;
 friend class vector<value_type, typename B::allocator_type>;
 friend class vector_reverse_iterator<this_t>;
 friend class vector_reverse_iterator<vector_iterator<B, const_reference> >;
 friend class vector_iterator<B, const_reference>;
 vector_iterator(base_type *b, pointer p)
 : base(b),
 ptr(p)
 {
 }
 template<typename R = reference>
 vector_iterator(vector_iterator<B, R> const &rhs)
 : base(rhs.base),
 ptr(rhs.ptr)
 {
 }
 ~vector_iterator()
 {
 }
 this_t &operator=(this_t const &rhs)
 {
 base = rhs.base;
 ptr = rhs.ptr;
 return (*this);
 }
 this_t &operator++()
 {
 ++ptr;
 return (*this);
 }
 this_t operator++(int)
 {
 this_t temp(*this);
 ++ptr;
 return (temp);
 }
 this_t &operator--()
 {
 --ptr;
 return (*this);
 }
 this_t operator--(int)
 {
 this_t temp(*this);
 --ptr;
 return (temp);
 }
 this_t operator+(size_type offset) const
 {
 return (this_t(base, ptr + offset));
 }
 this_t operator-(size_type offset) const
 {
 return (this_t(base, ptr - offset));
 }
 difference_type operator-(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr - rhs.ptr);
 }
 this_t &operator+=(size_type offset)
 {
 ptr += offset;
 return (*this);
 }
 this_t &operator-=(size_type offset)
 {
 ptr -= offset;
 return (*this);
 }
 reference operator*() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (*ptr);
 }
 reference operator[](size_type offset) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(this_t(base, ptr + offset), ptr_in_seq);
# endif
 return (*(ptr + offset));
 }
 pointer operator->() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (ptr);
 }
 bool operator==(this_t const &rhs) const
 {
 return (ptr == rhs.ptr);
 }
 bool operator!=(this_t const &rhs) const
 {
 return (!((*this) == rhs));
 }
 bool operator<(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr < rhs.ptr);
 }
 bool operator>(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr > rhs.ptr);
 }
 bool operator<=(this_t const &rhs) const
 {
 return (!(ptr > rhs.ptr));
 }
 bool operator>=(this_t const &rhs) const
 {
 return (!(ptr < rhs.ptr));
 }
private:
 pointer ptr;
 base_type *base;
 static void check_validity(this_t const &it, bool (*test)(this_t const &))
 {
 if (!test(it))
 {
 throw std::exception("iterator out of range");
 }
 }
 void check_compatible(this_t const &it) const
 {
 if (it.base != base)
 {
 throw std::exception("iterators incompatible (not in same container)");
 }
 }
 static bool ptr_in_seq(this_t const &it)
 {
 return (it.ptr >= it.base->ms_begin && 
 it.ptr < it.base->s_end);
 }
 static bool ptr_in_seq_or_end(this_t const &it)
 {
 return (it.ptr >= it.base->ms_begin && 
 it.ptr <= it.base->s_end);
 }
 };
template<typename I>
 class vector_reverse_iterator
 {
public:
 typedef vector_reverse_iterator<I> this_t;
 typedef typename I::base_type base_type;
 typedef typename I::pointer pointer;
 typedef typename I::reference reference;
 typedef typename I::const_reference const_reference;
 typedef typename I::size_type size_type;
 typedef typename I::difference_type difference_type;
 friend class vector_reverse_iterator<vector_iterator<base_type, const_reference> >;
 vector_reverse_iterator(I const &it)
 : base(it.base)
 {
 size_type from_begin = (it.ptr - it.base->ms_begin) + 1;
 ptr = (it.base->s_end - from_begin);
 }
 template<typename R = reference>
 vector_reverse_iterator(vector_reverse_iterator<
 vector_iterator<base_type, R> > const &rhs)
 : base(rhs.base),
 ptr(rhs.ptr)
 {
 }
 ~vector_reverse_iterator()
 {
 }
 this_t &operator=(this_t const &rhs)
 {
 base = rhs.base;
 ptr = rhs.ptr;
 return (*this);
 }
 this_t &operator++()
 {
 --ptr;
 return (*this);
 }
 this_t operator++(int)
 {
 this_t temp(*this);
 --ptr;
 return (temp);
 }
 this_t &operator--()
 {
 ++ptr;
 return (*this);
 }
 this_t operator--(int)
 {
 this_t temp(*this);
 ++ptr;
 return (temp);
 }
 this_t operator+(size_type offset) const
 {
 return (this_t(base, ptr - offset));
 }
 this_t operator-(size_type offset) const
 {
 return (this_t(base, ptr + offset));
 }
 difference_type operator-(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (rhs.ptr - ptr);
 }
 this_t &operator+=(size_type offset)
 {
 ptr -= offset;
 return (*this);
 }
 this_t &operator-=(size_type offset)
 {
 ptr += offset;
 return (*this);
 }
 reference operator*() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (*ptr);
 }
 reference operator[](size_type offset) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(this_t(base, ptr - offset), ptr_in_seq);
# endif
 return (*(ptr + offset));
 }
 pointer operator->() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (ptr);
 }
 bool operator==(this_t const &rhs) const
 {
 return (ptr == rhs.ptr);
 }
 bool operator!=(this_t const &rhs) const
 {
 return (!((*this) == rhs));
 }
 bool operator<(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr > rhs.ptr);
 }
 bool operator>(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr < rhs.ptr);
 }
 bool operator<=(this_t const &rhs) const
 {
 return (!(ptr < rhs.ptr));
 }
 bool operator>=(this_t const &rhs) const
 {
 return (!(ptr > rhs.ptr));
 }
private:
 pointer ptr;
 base_type *base;
 static void check_validity(this_t const &it, bool (*test)(this_t const &))
 {
 if (!test(it))
 {
 throw std::exception("iterator out of range");
 }
 }
 void check_compatible(this_t const &it) const
 {
 if (it.base != base)
 {
 throw std::exception("iterators incompatible (not in same container)");
 }
 }
 static bool ptr_in_seq(this_t const &it)
 {
 return (it.ptr > (it.base->ms_begin - 1) && 
 it.ptr <= (it.base->s_end - 1));
 }
 static bool ptr_in_seq_or_end(this_t const &it)
 {
 return (it.ptr >= (it.base->ms_begin - 1) && 
 it.ptr <= (it.base->s_end - 1));
 }
 };
template<typename T,
 typename A = std::allocator<T> >
 class vector
 : public vector_base<A>
 {
public:
 typedef typename A::value_type value_type;
 typedef typename A::const_pointer const_pointer;
 typedef typename A::reference reference;
 typedef typename A::const_reference const_reference;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type; 
 typedef vector_iterator<base_type> iterator; 
 typedef vector_iterator<base_type, const_reference> const_iterator;
 typedef vector_reverse_iterator<iterator> reverse_iterator;
 typedef vector_reverse_iterator<const_iterator> const_reverse_iterator;
 typedef vector<T, A> this_t;
 explicit vector(allocator_type const &al = allocator_type())
 : base_type(al)
 {
 }
 explicit vector(size_type count, const_reference value = value_type(),
 allocator_type const &al = allocator_type())
 : base_type(al)
 {
 assign(count, value);
 }
 template<typename InIt>
 vector(typename std::enable_if<!std::is_integral<InIt>::value, InIt> first,
 typename std::enable_if<!std::is_integral<InIt>::value, InIt> last,
 allocator_type const &al = allocator_type())
 : base_type(al)
 {
 assign(first, last);
 }
 vector(this_t const &rhs)
 : base_type(rhs.alloc)
 {
 assign(rhs.ms_begin, rhs.s_end);
 }
 void assign(size_type count, value_type const &value = value_type())
 {
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (count > capacity())
 {
 reallocate(count * 1.5);
 }
 wipe_values();
 }
 this->s_end = std::uninitialized_fill_n(
 this->ms_begin, count, value);
 }
 template<typename InIt>
 typename std::enable_if<!std::is_integral<InIt>::value, void>::type assign(InIt first, InIt last)
 {
 difference_type count = (last - first);
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (count > capacity())
 {
 reallocate(count * 1.5);
 }
 wipe_values();
 }
 this->s_end = std::uninitialized_copy(
 first, last, this->ms_begin);
 }
 iterator erase(iterator where)
 {
 return (erase(where, where + 1));
 }
 iterator erase(iterator first, iterator last)
 {
 iterator::check_validity(first, iterator::ptr_in_seq);
 iterator::check_validity(last, iterator::ptr_in_seq_or_end);
 difference_type diff = (last - first);
 size_type fpos = (first.ptr - this->ms_begin), 
 lpos = (last.ptr - this->ms_begin);
 std::rotate(this->ms_begin + fpos, this->ms_begin + lpos, this->s_end);
 while (diff--)
 {
 this->alloc.destroy(--this->s_end);
 }
 return (iterator(this->get_base(), this->ms_begin + (lpos - (last - first))));
 }
 void insert(iterator where, const value_type &value = value_type())
 {
 insert(where, 1, value);
 }
 void insert(iterator where, unsigned count, const value_type &value = value_type())
 {
 iterator::check_validity(where, iterator::ptr_in_seq_or_end);
 size_type wpos = (where.ptr - this->ms_begin)
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (size() + count > capacity())
 {
 reallocate((size() + count) * 1.5);
 }
 }
 size_type c2 = count;
 while (c2--)
 {
 this->alloc.construct(this->s_end++, value);
 }
 std::rotate(this->ms_begin + wpos, this->s_end - count, this->s_end);
 }
 template<typename InIt>
 typename std::enable_if<!std::is_integral<InIt>::value, void>::type insert(iterator where, InIt first, InIt last)
 {
 iterator::check_validity(where, iterator::ptr_in_seq_or_end);
 size_type wpos = (where.ptr - this->ms_begin);
 difference_type diff = (last - first);
 if (is_unconstructed())
 {
 allocate(diff * 1.5);
 }
 else
 {
 if (size() + diff > capacity())
 {
 reallocate((size() + diff) * 1.5);
 }
 }
 while (first != last)
 {
 this->alloc.construct(this->s_end++, first++);
 }
 std::rotate(this->ms_begin + wpos, this->s_end - diff, this->s_end);
 }
 void push_back(value_type const &value)
 {
 insert(end(), value);
 }
 void pop_back()
 {
 erase(end() - 1);
 }
 void clear()
 {
 erase(begin(), end());
 }
 iterator begin()
 {
 return (iterator(this->get_base(), this->ms_begin));
 }
 iterator end()
 {
 return (iterator(this->get_base(), this->s_end));
 }
 const_iterator begin() const
 {
 return (const_iterator(this->get_base(), this->ms_begin));
 }
 const_iterator end() const
 {
 return (const_iterator(this->get_base(), this->s_end));
 }
 reverse_iterator rbegin()
 {
 return (reverse_iterator(begin()));
 }
 reverse_iterator rend()
 {
 return (reverse_iterator(end()));
 }
 const_reverse_iterator rbegin() const
 {
 return (const_reverse_iterator(begin()));
 }
 const_reverse_iterator rend() const
 {
 return (const_reverse_iterator(end()));
 }
 reference operator[](size_type offset)
 {
 return (*(this->ms_begin + offset));
 }
 const_reference operator[](size_type offset) const
 {
 return (*(this->ms_begin + offset));
 }
 reference front()
 {
 return (*this->ms_begin);
 }
 const_reference front() const
 {
 return (*this->ms_begin);
 }
 reference back()
 {
 return (*(this->s_end - 1));
 }
 const_reference back() const
 {
 return (*(this->s_end - 1));
 }
 reference at(size_type offset)
 {
 if (offset >= size())
 {
 throw std::exception("offset out of bounds");
 }
 return (*(this->ms_begin + offset));
 }
 
 const_reference at(size_type offset) const
 {
 if (offset >= size())
 {
 throw std::exception("offset out of bounds");
 }
 return (*(this->ms_begin + offset));
 }
 void reserve(size_type count)
 {
 if (count > capacity())
 {
 reallocate(count);
 }
 }
 void resize(size_type count, value_type value = value_type())
 {
 if (count < size())
 {
 erase(begin() + count, end());
 }
 else
 {
 reserve(count);
 insert(end(), count - size(), value);
 }
 }
 void swap(this_t &rhs)
 {
 base_type b = *(this->get_base());
 *(this->get_base()) = *(rhs.get_base());
 *(rhs.get_base()) = b;
 }
 size_type size() const
 {
 return (this->s_end - this->ms_begin);
 }
 size_type capacity() const
 {
 return (this->m_end - this->ms_begin);
 }
 allocator_type get_allocator() const
 {
 return (this->alloc);
 }
 bool empty() const
 {
 return (this->ms_begin == this->s_end);
 }
private:
 void allocate(size_type count)
 {
 if (count > this->alloc.max_size())
 {
 throw std::exception("unable to allocate memory");
 }
 this->ms_begin = this->alloc.allocate(count);
 this->s_end = this->ms_begin;
 this->m_end = this->ms_begin + count;
 }
 void reallocate(size_type count)
 {
 if (count > this->alloc.max_size())
 {
 throw std::exception("unable to allocate memory");
 }
 pointer nbegin = this->alloc.allocate(count);
 std::uninitialized_copy(this->ms_begin, this->s_end, nbegin);
 size_type sz = size();
 wipe_all();
 this->ms_begin = nbegin;
 this->s_end = nbegin + sz;
 this->m_end = nbegin + count;
 }
 void wipe_values()
 {
 if (!is_unconstructed())
 {
 size_type sz = size();
 while (this->ms_begin != this->s_end)
 {
 this->alloc.destroy(this->ms_begin++);
 }
 this->ms_begin -= sz;
 }
 }
 void wipe_all()
 {
 if (!is_unconstructed())
 {
 wipe_values();
 this->alloc.deallocate(this->ms_begin, capacity());
 this->ms_begin = pointer();
 this->s_end = pointer();
 this->m_end = pointer();
 }
 }
 bool is_unconstructed() const
 {
 return (this->ms_begin == pointer());
 }
 };
# endif

# ifndef __VECTOR_H__
# define __VECTOR_H__
# include <memory>
# include <algorithm>
template<typename T,
 typename A>
 class vector;
template<typename B, 
 typename R>
 class vector_iterator;
template<typename I>
 class vector_reverse_iterator;
template<typename A>
 class vector_base
 {
public:
 typedef vector_base<A> base_type;
 typedef typename A allocator_type;
 typedef typename A::pointer pointer;
 friend class vector<typename A::value_type, A>;
 friend class vector_iterator<base_type, typename A::reference>;
 friend class vector_iterator<base_type, typename A::const_reference>;
 friend class vector_reverse_iterator<vector_iterator<base_type, typename A::reference> >;
 friend class vector_reverse_iterator<vector_iterator<base_type, typename A::const_reference> >;
private:
 vector_base(allocator_type const &al)
 : ms_begin(pointer()),
 s_end(pointer()),
 m_end(pointer()),
 alloc(al)
 {
 }
 ~vector_base()
 {
 }
 base_type *get_base()
 {
 return (this);
 }
 pointer ms_begin, s_end, m_end;
 allocator_type alloc;
 };
# ifndef VECTOR_ITERATOR_CHECK_LEVEL
# define VECTOR_ITERATOR_CHECK_LEVEL 1
# endif
template<typename B,
 typename R = typename B::allocator_type::reference>
 class vector_iterator
 {
public:
 typedef vector_iterator<B, R> this_t;
 typedef B base_type;
 typedef typename B::allocator_type::pointer pointer;
 typedef typename R reference;
 typedef typename B::allocator_type::const_reference const_reference;
 typedef typename B::allocator_type::value_type value_type;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type;
 typedef std::random_access_iterator_tag iterator_category;
 friend class vector<value_type, typename B::allocator_type>;
 friend class vector_reverse_iterator<this_t>;
 friend class vector_reverse_iterator<vector_iterator<B, const_reference> >;
 friend class vector_iterator<B, const_reference>;
 vector_iterator(base_type *b, pointer p)
 : base(b),
 ptr(p)
 {
 }
 template<typename R = reference>
 vector_iterator(vector_iterator<B, R> const &rhs)
 : base(rhs.base),
 ptr(rhs.ptr)
 {
 }
 ~vector_iterator()
 {
 }
 this_t &operator=(this_t const &rhs)
 {
 base = rhs.base;
 ptr = rhs.ptr;
 return (*this);
 }
 this_t &operator++()
 {
 ++ptr;
 return (*this);
 }
 this_t operator++(int)
 {
 this_t temp(*this);
 ++ptr;
 return (temp);
 }
 this_t &operator--()
 {
 --ptr;
 return (*this);
 }
 this_t operator--(int)
 {
 this_t temp(*this);
 --ptr;
 return (temp);
 }
 this_t operator+(size_type offset) const
 {
 return (this_t(base, ptr + offset));
 }
 this_t operator-(size_type offset) const
 {
 return (this_t(base, ptr - offset));
 }
 difference_type operator-(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr - rhs.ptr);
 }
 this_t &operator+=(size_type offset)
 {
 ptr += offset;
 return (*this);
 }
 this_t &operator-=(size_type offset)
 {
 ptr -= offset;
 return (*this);
 }
 reference operator*() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (*ptr);
 }
 reference operator[](size_type offset) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(this_t(base, ptr + offset), ptr_in_seq);
# endif
 return (*(ptr + offset));
 }
 pointer operator->() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (ptr);
 }
 bool operator==(this_t const &rhs) const
 {
 return (ptr == rhs.ptr);
 }
 bool operator!=(this_t const &rhs) const
 {
 return (!((*this) == rhs));
 }
 bool operator<(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr < rhs.ptr);
 }
 bool operator>(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr > rhs.ptr);
 }
 bool operator<=(this_t const &rhs) const
 {
 return (!(ptr > rhs.ptr));
 }
 bool operator>=(this_t const &rhs) const
 {
 return (!(ptr < rhs.ptr));
 }
private:
 pointer ptr;
 base_type *base;
 static void check_validity(this_t const &it, bool (*test)(this_t const &))
 {
 if (!test(it))
 {
 throw std::exception("iterator out of range");
 }
 }
 void check_compatible(this_t const &it) const
 {
 if (it.base != base)
 {
 throw std::exception("iterators incompatible (not in same container)");
 }
 }
 static bool ptr_in_seq(this_t const &it)
 {
 return (it.ptr >= it.base->ms_begin && 
 it.ptr < it.base->s_end);
 }
 static bool ptr_in_seq_or_end(this_t const &it)
 {
 return (it.ptr >= it.base->ms_begin && 
 it.ptr <= it.base->s_end);
 }
 };
template<typename I>
 class vector_reverse_iterator
 {
public:
 typedef vector_reverse_iterator<I> this_t;
 typedef typename I::base_type base_type;
 typedef typename I::pointer pointer;
 typedef typename I::reference reference;
 typedef typename I::const_reference const_reference;
 typedef typename I::size_type size_type;
 typedef typename I::difference_type difference_type;
 friend class vector_reverse_iterator<vector_iterator<base_type, const_reference> >;
 vector_reverse_iterator(I const &it)
 : base(it.base)
 {
 size_type from_begin = (it.ptr - it.base->ms_begin) + 1;
 ptr = (it.base->s_end - from_begin);
 }
 template<typename R = reference>
 vector_reverse_iterator(vector_reverse_iterator<
 vector_iterator<base_type, R> > const &rhs)
 : base(rhs.base),
 ptr(rhs.ptr)
 {
 }
 ~vector_reverse_iterator()
 {
 }
 this_t &operator=(this_t const &rhs)
 {
 base = rhs.base;
 ptr = rhs.ptr;
 return (*this);
 }
 this_t &operator++()
 {
 --ptr;
 return (*this);
 }
 this_t operator++(int)
 {
 this_t temp(*this);
 --ptr;
 return (temp);
 }
 this_t &operator--()
 {
 ++ptr;
 return (*this);
 }
 this_t operator--(int)
 {
 this_t temp(*this);
 ++ptr;
 return (temp);
 }
 this_t operator+(size_type offset) const
 {
 return (this_t(base, ptr - offset));
 }
 this_t operator-(size_type offset) const
 {
 return (this_t(base, ptr + offset));
 }
 difference_type operator-(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (rhs.ptr - ptr);
 }
 this_t &operator+=(size_type offset)
 {
 ptr -= offset;
 return (*this);
 }
 this_t &operator-=(size_type offset)
 {
 ptr += offset;
 return (*this);
 }
 reference operator*() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (*ptr);
 }
 reference operator[](size_type offset) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(this_t(base, ptr - offset), ptr_in_seq);
# endif
 return (*(ptr + offset));
 }
 pointer operator->() const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_validity(*this, ptr_in_seq);
# endif
 return (ptr);
 }
 bool operator==(this_t const &rhs) const
 {
 return (ptr == rhs.ptr);
 }
 bool operator!=(this_t const &rhs) const
 {
 return (!((*this) == rhs));
 }
 bool operator<(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr > rhs.ptr);
 }
 bool operator>(this_t const &rhs) const
 {
# if VECTOR_ITERATOR_CHECK_LEVEL >= 1
 check_compatible(rhs);
# endif
 return (ptr < rhs.ptr);
 }
 bool operator<=(this_t const &rhs) const
 {
 return (!(ptr < rhs.ptr));
 }
 bool operator>=(this_t const &rhs) const
 {
 return (!(ptr > rhs.ptr));
 }
private:
 pointer ptr;
 base_type *base;
 static void check_validity(this_t const &it, bool (*test)(this_t const &))
 {
 if (!test(it))
 {
 throw std::exception("iterator out of range");
 }
 }
 void check_compatible(this_t const &it) const
 {
 if (it.base != base)
 {
 throw std::exception("iterators incompatible (not in same container)");
 }
 }
 static bool ptr_in_seq(this_t const &it)
 {
 return (it.ptr > (it.base->ms_begin - 1) && 
 it.ptr <= (it.base->s_end - 1));
 }
 static bool ptr_in_seq_or_end(this_t const &it)
 {
 return (it.ptr >= (it.base->ms_begin - 1) && 
 it.ptr <= (it.base->s_end - 1));
 }
 };
template<typename T,
 typename A = std::allocator<T> >
 class vector
 : public vector_base<A>
 {
public:
 typedef typename A::value_type value_type;
 typedef typename A::const_pointer const_pointer;
 typedef typename A::reference reference;
 typedef typename A::const_reference const_reference;
 typedef std::size_t size_type;
 typedef std::ptrdiff_t difference_type; 
 typedef vector_iterator<base_type> iterator; 
 typedef vector_iterator<base_type, const_reference> const_iterator;
 typedef vector_reverse_iterator<iterator> reverse_iterator;
 typedef vector_reverse_iterator<const_iterator> const_reverse_iterator;
 typedef vector<T, A> this_t;
 explicit vector(allocator_type const &al = allocator_type())
 : base_type(al)
 {
 }
 explicit vector(size_type count, const_reference value = value_type(),
 allocator_type const &al = allocator_type())
 : base_type(al)
 {
 assign(count, value);
 }
 template<typename InIt>
 vector(typename std::enable_if<!std::is_integral<InIt>::value, InIt> first,
 typename std::enable_if<!std::is_integral<InIt>::value, InIt> last,
 allocator_type const &al = allocator_type())
 : base_type(al)
 {
 assign(first, last);
 }
 vector(this_t const &rhs)
 : base_type(rhs.alloc)
 {
 if(&rhs != this)
 {
 assign(rhs.ms_begin, rhs.s_end);
 }
 }
 void assign(size_type count, value_type const &value = value_type())
 {
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (count > capacity())
 {
 reallocate(count * 1.5);
 }
 wipe_values();
 }
 this->s_end = std::uninitialized_fill_n(
 this->ms_begin, count, value);
 }
 template<typename InIt>
 typename std::enable_if<!std::is_integral<InIt>::value, void>::type assign(InIt first, InIt last)
 {
 difference_type count = (last - first);
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (count > capacity())
 {
 reallocate(count * 1.5);
 }
 wipe_values();
 }
 this->s_end = std::uninitialized_copy(
 first, last, this->ms_begin);
 }
 iterator erase(iterator where)
 {
 return (erase(where, where + 1));
 }
 iterator erase(iterator first, iterator last)
 {
 iterator::check_validity(first, iterator::ptr_in_seq);
 iterator::check_validity(last, iterator::ptr_in_seq_or_end);
 difference_type diff = (last - first);
 size_type fpos = (first.ptr - this->ms_begin), 
 lpos = (last.ptr - this->ms_begin);
 std::rotate(this->ms_begin + fpos, this->ms_begin + lpos, this->s_end);
 while (diff--)
 {
 this->alloc.destroy(--this->s_end);
 }
 return (iterator(this->get_base(), this->ms_begin + (lpos - (last - first))));
 }
 void insert(iterator where, const value_type &value = value_type())
 {
 insert(where, 1, value);
 }
 void insert(iterator where, unsigned count, const value_type &value = value_type())
 {
 iterator::check_validity(where, iterator::ptr_in_seq_or_end);
 size_type wpos = (where.ptr - this->ms_begin)
 if (is_unconstructed())
 {
 allocate(count * 1.5);
 }
 else
 {
 if (size() + count > capacity())
 {
 reallocate((size() + count) * 1.5);
 }
 }
 size_type c2 = count;
 while (c2--)
 {
 this->alloc.construct(this->s_end++, value);
 }
 std::rotate(this->ms_begin + wpos, this->s_end - count, this->s_end);
 }
 template<typename InIt>
 typename std::enable_if<!std::is_integral<InIt>::value, void>::type insert(iterator where, InIt first, InIt last)
 {
 iterator::check_validity(where, iterator::ptr_in_seq_or_end);
 size_type wpos = (where.ptr - this->ms_begin);
 difference_type diff = (last - first);
 if (is_unconstructed())
 {
 allocate(diff * 1.5);
 }
 else
 {
 if (size() + diff > capacity())
 {
 reallocate((size() + diff) * 1.5);
 }
 }
 while (first != last)
 {
 this->alloc.construct(this->s_end++, first++);
 }
 std::rotate(this->ms_begin + wpos, this->s_end - diff, this->s_end);
 }
 void push_back(value_type const &value)
 {
 insert(end(), value);
 }
 void pop_back()
 {
 erase(end() - 1);
 }
 void clear()
 {
 erase(begin(), end());
 }
 iterator begin()
 {
 return (iterator(this->get_base(), this->ms_begin));
 }
 iterator end()
 {
 return (iterator(this->get_base(), this->s_end));
 }
 const_iterator begin() const
 {
 return (const_iterator(this->get_base(), this->ms_begin));
 }
 const_iterator end() const
 {
 return (const_iterator(this->get_base(), this->s_end));
 }
 reverse_iterator rbegin()
 {
 return (reverse_iterator(begin()));
 }
 reverse_iterator rend()
 {
 return (reverse_iterator(end()));
 }
 const_reverse_iterator rbegin() const
 {
 return (const_reverse_iterator(begin()));
 }
 const_reverse_iterator rend() const
 {
 return (const_reverse_iterator(end()));
 }
 reference operator[](size_type offset)
 {
 return (*(this->ms_begin + offset));
 }
 const_reference operator[](size_type offset) const
 {
 return (*(this->ms_begin + offset));
 }
 reference front()
 {
 return (*this->ms_begin);
 }
 const_reference front() const
 {
 return (*this->ms_begin);
 }
 reference back()
 {
 return (*(this->s_end - 1));
 }
 const_reference back() const
 {
 return (*(this->s_end - 1));
 }
 reference at(size_type offset)
 {
 if (offset >= size())
 {
 throw std::exception("offset out of bounds");
 }
 return (*(this->ms_begin + offset));
 }
 
 const_reference at(size_type offset) const
 {
 if (offset >= size())
 {
 throw std::exception("offset out of bounds");
 }
 return (*(this->ms_begin + offset));
 }
 void reserve(size_type count)
 {
 if (count > capacity())
 {
 reallocate(count);
 }
 }
 void resize(size_type count, value_type value = value_type())
 {
 if (count < size())
 {
 erase(begin() + count, end());
 }
 else
 {
 reserve(count);
 insert(end(), count - size(), value);
 }
 }
 void swap(this_t &rhs)
 {
 base_type b = *(this->get_base());
 *(this->get_base()) = *(rhs.get_base());
 *(rhs.get_base()) = b;
 }
 size_type size() const
 {
 return (this->s_end - this->ms_begin);
 }
 size_type capacity() const
 {
 return (this->m_end - this->ms_begin);
 }
 allocator_type get_allocator() const
 {
 return (this->alloc);
 }
 bool empty() const
 {
 return (this->ms_begin == this->s_end);
 }
private:
 void allocate(size_type count)
 {
 if (count > this->alloc.max_size())
 {
 throw std::exception("unable to allocate memory");
 }
 this->ms_begin = this->alloc.allocate(count);
 this->s_end = this->ms_begin;
 this->m_end = this->ms_begin + count;
 }
 void reallocate(size_type count)
 {
 if (count > this->alloc.max_size())
 {
 throw std::exception("unable to allocate memory");
 }
 pointer nbegin = this->alloc.allocate(count);
 std::uninitialized_copy(this->ms_begin, this->s_end, nbegin);
 size_type sz = size();
 wipe_all();
 this->ms_begin = nbegin;
 this->s_end = nbegin + sz;
 this->m_end = nbegin + count;
 }
 void wipe_values()
 {
 if (!is_unconstructed())
 {
 size_type sz = size();
 while (this->ms_begin != this->s_end)
 {
 this->alloc.destroy(this->ms_begin++);
 }
 this->ms_begin -= sz;
 }
 }
 void wipe_all()
 {
 if (!is_unconstructed())
 {
 wipe_values();
 this->alloc.deallocate(this->ms_begin, capacity());
 this->ms_begin = pointer();
 this->s_end = pointer();
 this->m_end = pointer();
 }
 }
 bool is_unconstructed() const
 {
 return (this->ms_begin == pointer());
 }
 };
# endif