std::vector (BSU)

#pragma once

#include <memory>
#include <iterator>
#include <type_traits>
#include <algorithm>

template<typename _InIter>
using _RequireInputIter = typename std::enable_if<
    std::is_convertible<
        typename std::iterator_traits<_InIter>::iterator_category,
        std::input_iterator_tag
    >::value
>::type;

template <class T, class A = std::allocator<T> >
class vector {
    public:
        using allocator_type = A;
        using value_type = T;
        using reference = T&;
        using const_reference = const T&;
        using pointer = typename std::allocator_traits<A>::pointer;
        using const_pointer = typename std::allocator_traits<A>::const_pointer;
        using difference_type = typename std::allocator_traits<A>::difference_type;
        using size_type = typename std::allocator_traits<A>::size_type;

        using iterator = T*;
        using const_iterator = const T*;

        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    public:
        explicit vector(size_type n = 0, const T& init = T(),
                        const allocator_type& alloc = allocator_type()) :
            _capacity(n), _alloc(alloc)
        {
            _data = std::allocator_traits<A>::allocate(_alloc, _capacity);
            for (_size = 0; _size < n; ++_size) {
                try {
                    std::allocator_traits<A>::construct(_alloc, _data + _size, init);
                } catch (...) {
                    clear();
                    throw;
                }
            }
        }

        template <class InIter,
                  typename = _RequireInputIter<InIter> >
        vector(InIter begin, InIter end,
               const allocator_type& alloc = allocator_type()) :
            _capacity(std::distance(begin, end)), _alloc(alloc)
        {
            _data = std::allocator_traits<A>::allocate(_alloc, _capacity);
            for (auto it = begin; it != end; ++it) {
                try {
                    std::allocator_traits<A>::construct(_alloc, _data + _size, *it);
                } catch (...) {
                    clear();
                    throw;
                }
                ++_size;
            }
        }

        vector(std::initializer_list<value_type> ilist,
                        const allocator_type& alloc = allocator_type()) :
            vector(ilist.begin(), ilist.end(), alloc) {}

        vector(const vector& rhs, const A& alloc) : _capacity(rhs._size), _alloc(alloc)
        {
            _data = std::allocator_traits<A>::allocate(_alloc, _capacity);
            for (_size = 0; _size < rhs.size(); ++_size) {
                try {
                    std::allocator_traits<A>::construct(_alloc, _data + _size, rhs[_size]);
                } catch (...) {
                    clear();
                    throw;
                }
            }
        }

        vector(const vector& rhs) : vector(rhs, rhs._alloc) {}

        vector(vector&& rhs, const A& alloc) : _size(rhs._size),
                _capacity(rhs._capacity), _data(rhs._data), _alloc(alloc)
        {
            rhs._data = nullptr;
            rhs._capacity = 0;
            rhs._size = 0;
        }

        vector(vector&& rhs) : _size(rhs._size), _capacity(rhs._capacity),
                _data(rhs._data), _alloc(std::move(rhs._alloc))
        {
            rhs._data = nullptr;
            rhs._capacity = 0;
            rhs._size = 0;
        }

        vector& operator=(vector rhs)
        {
            using std::swap;
            vector tmp(std::move(rhs));
            swap(*this, tmp);
            return *this;
        }

        ~vector()
        {
            clear();
        }

        void reserve(size_type n)
        {
            if (n > _capacity) {
                _force_reserve(n);
            }
        }

        void shrink_to_fit()
        {
            if (_size < _capacity)
                _force_reserve(_size);
        }

        void resize(size_type n, const value_type& val = value_type())
        {
            if (n == _size) return;
            if (n < _size) {
                for (size_type i = n; i != _size; ++i) {
                    std::allocator_traits<A>::destroy(_alloc, _data + i);
                }
                _size = n;
            }
            else {
                reserve(n);
                for (; _size < n; ++_size) {
                    std::allocator_traits<A>::construct(_alloc, _data + _size, val);
                }
            }
        }

        reference operator[](size_type i)
        {
            return _data[i];
        }

        const_reference operator[](size_type i) const
        {
            return _data[i];
        }

        reference at(size_type i)
        {
            if (i < 0 || i >= _size) {
                throw std::out_of_range("Trying to access element outside allowed range");
            }
            return _data[i];
        }

        const_reference at(size_type i) const
        {
            if (i < 0 || i >= _size) {
                throw std::out_of_range("Trying to access element outside allowed range");
            }
            return _data[i];
        }

        reference back()
        {
            return _data[_size - 1];
        }

        const_reference back() const
        {
            return _data[_size - 1];
        }

        reference front()
        {
            return _data[0];
        }

        const_reference front() const
        {
            return _data[0];
        }


        template <class... Ts>
        void assign(Ts&&... args)
        {
            using std::swap;
            vector tmp(std::forward<Ts>(args)...);
            swap(*this, tmp);
        }

        void assign(std::initializer_list<T> ilist)
        {
            assign(ilist.begin(), ilist.end());
        }

        void push_back(const T& element)
        {
            emplace_back(element);
        }

        template <class... Ts>
        void emplace_back(Ts&&... args)
        {
            _expand(1);
            std::allocator_traits<A>::construct(_alloc, _data + _size, std::forward<Ts>(args)...);
            ++_size;
        }

        void pop_back() noexcept
        {
            std::allocator_traits<A>::destroy(_alloc, _data + _size - 1);
            --_size;
        }

        template <class U>
        iterator insert(iterator pos, U&& rhs)
        {
            return emplace(pos, std::forward<U>(rhs));
        }

        iterator insert(iterator pos, size_type n,
                        const value_type& val)
        {
            const auto rel = pos - begin();
            _expand(n);
            pos = begin() + rel;

            for (auto i = end() - 1; i != pos - 1; --i) {
                *(i + n) = std::move_if_noexcept(*i);
            }
            _size += n;
            for (auto i = pos; i != pos + n; ++i) {
                *i = val;
            }
            return pos;
        }

        template <class InIter,
                    typename = _RequireInputIter<InIter> >
        iterator insert(iterator pos, InIter first, InIter last)
        {
            const auto rel = pos - begin();
            const auto n = std::distance(first, last);
            _expand(n);
            pos = begin() + rel;

            for (auto i = end() - 1; i != pos - 1; --i) {
                *(i + n) = std::move_if_noexcept(*i);
            }
            _size += n;
            for (auto i = pos, j = first; i != pos + n; ++i, ++j) {
                *i = *j;
            }
            return pos;
        }

        iterator insert(iterator pos, std::initializer_list<T> ilist)
        {
            return insert(pos, ilist.begin(), ilist.end());
        }

        template <class... Ts>
        iterator emplace(iterator pos, Ts&&... args)
        {
            difference_type rel = pos - begin();
            _expand(1);
            pos = begin() + rel;
            for (iterator i = end(); i != pos; --i) {
                *i = std::move_if_noexcept(*(i - 1));
            }
            ++_size;
            std::allocator_traits<A>::construct(_alloc, pos, std::forward<Ts...>(args...));
            return const_cast<iterator>(pos);
        }

        iterator erase(iterator pos)
        {
            return erase(pos, pos + 1);
        }

        iterator erase(iterator first, iterator last)
        {
            {
                auto i = first;
                for (auto j = last; j != end(); ++i, ++j) {
                    using std::swap;
                    *i = std::move(*j);
                    //swap(*i, *j);
                }
                for (; i != end(); ++i) {
                    std::allocator_traits<A>::destroy(_alloc, i);
                }
            }
            _size -= std::distance(first, last);
            return first;
        }

        void clear() noexcept
        {
            for (auto i = end() - 1; i + 1 != begin(); --i) {
                std::allocator_traits<A>::destroy(_alloc, i);
            }
            std::allocator_traits<A>::deallocate(_alloc, _data, _capacity);
            _data = nullptr;
            _size = _capacity = 0;
        }

        void swap(vector& rhs) noexcept
        {
            using std::swap;
            swap(_size, rhs._size);
            swap(_capacity, rhs._capacity);
            swap(_data, rhs._data);
            swap(_alloc, rhs._alloc);
        }

        iterator begin() noexcept
        {
            return _data;
        }
        const_iterator begin() const noexcept
        {
            return _data;
        }
        iterator end() noexcept
        {
            return _data + _size;
        }
        const_iterator end() const noexcept
        {
            return _data + _size;
        }
        const_iterator cbegin() const noexcept
        {
            return _data;
        }
        const_iterator cend() const noexcept
        {
            return _data + _size;
        }
        reverse_iterator rbegin() noexcept
        {
            return reverse_iterator(_data + _size);
        }
        reverse_iterator rend() noexcept
        {
            return reverse_iterator(_data);
        }
        const_reverse_iterator crbegin() const noexcept
        {
            return const_reverse_iterator(_data + _size);
        }
        const_reverse_iterator crend() const noexcept
        {
            return const_reverse_iterator(_data);
        }

        value_type* data() noexcept
        {
            return _data;
        }

        const value_type* data() const noexcept
        {
            return _data;
        }

        constexpr size_type size() const noexcept
        {
            return _size;
        }

        constexpr size_type capacity() const noexcept
        {
            return _capacity;
        }

        constexpr bool empty() const noexcept
        {
            return !_size;
        }

        friend bool operator==(const vector& lhs, const vector& rhs)
        {
            return lhs.size() == rhs.size() &&
                    std::equal(lhs.begin(), lhs.end(), rhs.begin());
        }
        friend bool operator!=(const vector& lhs, const vector& rhs)
        {
            return !(lhs == rhs);
        }
        friend bool operator<(const vector& lhs, const vector& rhs)
        {
            return std::lexicographical_compare(lhs.begin(), lhs.end(),
                                                rhs.begin(), rhs.end());
        }
        friend bool operator<=(const vector& lhs, const vector& rhs)
        {
            return lhs == rhs || lhs < rhs;
        }
        friend bool operator>(const vector& lhs, const vector& rhs)
        {
            return !(lhs <= rhs);
        }
        friend bool operator>=(const vector& lhs, const vector& rhs)
        {
            return !(lhs < rhs);
        }

    private:
        void _force_reserve(size_type n)
        {
            pointer new_data;
            new_data = std::allocator_traits<A>::allocate(_alloc, n);
            for (size_type i = 0; i < _size; ++i) {
                try {
                    std::allocator_traits<A>::construct(_alloc, new_data + i,
                                     std::move_if_noexcept(_data[i]));
                } catch (...) {
                    for (size_type j = 0; j < i; ++j)
                        std::allocator_traits<A>::destroy(_alloc, new_data + j);
                    std::allocator_traits<A>::deallocate(_alloc, new_data, n);
                    trow;
                }
            }
            const auto old_size = _size;
            clear();

            _size = old_size;
            _data = new_data;
            _capacity = n;
        }

        bool _expand(size_type req_size)
        {
            if (req_size + _size > _capacity) {
                reserve((req_size + _size) * 2);
                return true;
            }
            return false;
        }

    private:
        size_type _size = 0;
        size_type _capacity = 0;
        pointer _data = nullptr;
        allocator_type _alloc = allocator_type();
};

template <class T>
void swap(vector<T>& lhs, vector<T>& rhs) noexcept
{
    lhs.swap(rhs);
}

// vim:ts=4:sts=4:sw=4:noexpandtab