eonix/gblibstdc++/include/vector

#ifndef __GBLIBCPP_VECTOR__
#define __GBLIBCPP_VECTOR__

#include <bits/iter_ops>
#include <bits/compressed_pair>

#include <functional>
#include <memory>
#include <initializer_list>
#include <cstddef>

namespace std {

template <typename T, typename Allocator = std::allocator<T>>
class vector {
public:
    using value_type = T;
    using allocator_type = Allocator;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = T&;
    using const_reference = const T&;

    template <bool Const>
    class _iterator {
    public:
        // TODO:
        // using iterator_category = std::random_access_iterator_tag;
        using value_type = std::conditional_t<Const, const T, T>;
        using difference_type = std::ptrdiff_t;
        using pointer = std::add_pointer_t<value_type>;
        using reference = std::add_lvalue_reference_t<value_type>;

    private:
        T* m_ptr;

    public:
        constexpr _iterator(void) noexcept : m_ptr() {}
        constexpr explicit _iterator(const T* ptr) noexcept
            : m_ptr(const_cast<T*>(ptr)) {}
        constexpr _iterator(const _iterator& other) noexcept = default;
        constexpr _iterator(_iterator&& other) noexcept = default;
        constexpr _iterator& operator=(const _iterator& other) noexcept = default;
        constexpr _iterator& operator=(_iterator&& other) noexcept = default;
        constexpr bool operator==(const _iterator& other) const noexcept = default;

        constexpr reference operator*() const noexcept { return *m_ptr; }
        constexpr pointer operator&() const noexcept
        { return std::addressof(this->operator*()); }
        constexpr pointer operator->() const noexcept
        { return this->operator&(); }
        constexpr _iterator& operator++() noexcept
        { ++m_ptr; return *this; }
        constexpr _iterator operator++(int) noexcept
        { _iterator ret(m_ptr); (void)this->operator++(); return ret; }
        constexpr _iterator& operator--(void) noexcept
        { --m_ptr; return *this; }
        constexpr _iterator operator--(int) noexcept
        { _iterator ret(m_ptr); (void)this->operator--(); return ret; }
        constexpr _iterator& operator+=(difference_type n) noexcept
        { m_ptr += n; return *this; }
        constexpr _iterator& operator-=(difference_type n) noexcept
        { m_ptr -= n; return *this; }
        constexpr _iterator operator+(difference_type n) const noexcept
        { return _iterator { m_ptr + n }; }
        constexpr _iterator operator-(difference_type n) const noexcept
        { return _iterator { m_ptr - n }; }
        constexpr difference_type operator-(const _iterator& other) const noexcept
        { return m_ptr - other.m_ptr; }
        constexpr reference operator[](difference_type n) const noexcept
        { return m_ptr[n]; }
        constexpr operator bool() { return m_ptr; }
        constexpr operator _iterator<true>() { return _iterator<true> { m_ptr }; }
        constexpr operator _iterator<false>() { return _iterator<false> { m_ptr }; }
        constexpr operator const T*() { return m_ptr; }
    };

private:
    using alloc_traits = std::allocator_traits<Allocator>;

public:
    using pointer = typename alloc_traits::pointer;
    using const_pointer = typename alloc_traits::const_pointer;
    using iterator = _iterator<false>;
    using const_iterator = _iterator<true>;

private:
    impl::compressed_pair<T*, allocator_type> m_data;
    size_type m_size;
    size_type m_capacity;

private:
    constexpr allocator_type& _alloc() noexcept { return m_data.second(); }
    constexpr const allocator_type& _alloc() const noexcept { return m_data.second(); }
    constexpr T*& _data() noexcept { return m_data.first(); }
    constexpr T* const& _data() const noexcept { return m_data.first(); }

    // assert(n >= m_size)
    constexpr void _reallocate_safe(size_type n)
    {
        T* newptr = nullptr;
        if (n)
            newptr = alloc_traits::allocate(_alloc(), n);

        for (size_t i = 0; i < m_size; ++i) {
            if (n)
                alloc_traits::construct(_alloc(), newptr + i, std::move(_data()[i]));
            alloc_traits::destroy(_alloc(), _data() + i);
        }

        alloc_traits::deallocate(_alloc(), _data(), m_capacity);
        _data() = newptr;
        m_capacity = n;
    }

    // make m_capacity >= n >= m_size
    constexpr void _pre_resize(size_type n)
    {
        while (n < m_size)
            pop_back();

        reserve(n);
    }

public:
    constexpr vector(void)
        noexcept(noexcept(Allocator()))
        : m_data{impl::default_construct_t{}}, m_size(), m_capacity() {}

    constexpr explicit vector(const Allocator& alloc) noexcept
        : m_data{nullptr, alloc}, m_size(), m_capacity() {}

    constexpr vector(size_type n, const T& val,
        const Allocator& alloc = Allocator())
        : vector(alloc) { resize(n, val); }

    constexpr explicit vector(size_type n,
        const Allocator& alloc = Allocator())
        : vector(alloc) { resize(n); }

    // TODO: check whether InputIter satisfies LegacyInputIterator
    template <typename InputIter>
    constexpr vector(InputIter first, InputIter last,
        const Allocator& alloc = Allocator())
        : vector(alloc) { insert(cbegin(), first, last); }

    constexpr vector(const vector& other)
        : vector(std::allocator_traits<allocator_type>::
            select_on_container_copy_construction(other._alloc()))
    { insert(cbegin(), other.begin(), other.end()); }

    constexpr vector(const vector& other, const Allocator& alloc)
        : vector(alloc) { insert(cbegin(), other.begin(), other.end()); }

    constexpr vector(vector&& other) noexcept
        : m_data{std::exchange(other._data(), nullptr), std::move(other._alloc())}
        , m_size(std::exchange(other.m_size, 0))
        , m_capacity(std::exchange(other.m_capacity, 0)) { }

    constexpr vector(vector&& other, const Allocator& alloc)
        : vector(alloc)
    {
        if (alloc == other._alloc()) {
            _data() = std::exchange(other._data(), nullptr);
            m_size = std::exchange(other.m_size, 0);
            m_capacity = std::exchange(other.m_capacity, 0);
        } else {
            // TODO: std::move_iterator
            // insert(cbegin(), std::make_move_iterator(other.begin()),
            //     std::make_move_iterator(other.end()));
            for (auto& item : other)
                emplace_back(std::move(item));
        }
    }

    constexpr vector(std::initializer_list<T> init,
        const Allocator& alloc = Allocator())
        : vector(alloc) { insert(cbegin(), init.begin(), init.end()); }

    constexpr ~vector()
    {
        resize(0);
        shrink_to_fit();
    }

    constexpr vector& operator=(const vector& other)
    {
        clear();

        if constexpr (alloc_traits::
            propagate_on_container_copy_assignment::value) {
            if (_alloc() != other._alloc())
                shrink_to_fit();
            _alloc() = other._alloc();
        }

        insert(cbegin(), other.begin(), other.end());
        return *this;
    }

    constexpr vector& operator=(vector&& other)
    {
        clear();

        if constexpr (alloc_traits::
            propagate_on_container_move_assignment::value) {
            shrink_to_fit();
            _alloc() = std::move(other._alloc());
        }
        else {
            if (_alloc() != other._alloc()) {
                // TODO: std::move_iterator
                for (auto& item : other)
                    emplace_back(std::move(item));
                return *this;
            }
            shrink_to_fit();
        }

        _data() = std::exchange(other._data(), nullptr);
        m_size = std::exchange(other.m_size, 0);
        m_capacity = std::exchange(other.m_capacity, 0);
        return *this;
    }

    constexpr vector& operator=(std::initializer_list<T> init)
    {
        assign(init.begin(), init.end());
        return *this;
    }

    constexpr void assign(size_type n, const T& val)
    {
        clear();
        resize(n, val);
    }

    // TODO: check whether InputIter satisfies LegacyInputIterator
    template <typename InputIter>
    constexpr void assign(InputIter first, InputIter last)
    {
        clear();
        insert(cbegin(), first, last);
    }
    constexpr void assign(std::initializer_list<T> init)
    {
        clear();
        insert(cbegin(), init.begin(), init.end());
    }

    constexpr allocator_type get_allocator(void) const noexcept
    { return _alloc(); }

    constexpr reference at(size_type pos)
    {
        // TODO: exceptions
        // if (pos >= sz)
        //     throw std::out_of_range("vector::at");
        return _data()[pos];
    }
    constexpr const_reference at(size_type pos) const
    {
        // TODO: exceptions
        // if (pos >= sz)
        //     throw std::out_of_range("vector::at");
        return _data()[pos];
    }

    constexpr reference operator[](size_type pos) noexcept
    { return _data()[pos]; }
    constexpr const_reference operator[](size_type pos) const noexcept
    { return _data()[pos]; }

    constexpr reference front() noexcept
    { return _data()[0]; }
    constexpr const_reference front() const noexcept
    { return _data()[0]; }
    constexpr reference back() noexcept
    { return _data()[m_size - 1]; }
    constexpr const_reference back() const noexcept
    { return _data()[m_size - 1]; }

    constexpr T* data(void) noexcept
    { return _data(); }
    constexpr const T* data(void) const noexcept
    { return _data(); }

    // TODO: std::reverse_iterator
    constexpr iterator begin() noexcept
    { return iterator { _data() }; }
    constexpr const_iterator begin() const noexcept
    { return const_iterator { _data() }; }
    constexpr const_iterator cbegin() const noexcept
    { return const_iterator { _data() }; }
    constexpr iterator end() noexcept
    { return iterator { _data() + m_size }; }
    constexpr const_iterator end() const noexcept
    { return const_iterator { _data() + m_size }; }
    constexpr const_iterator cend() const noexcept
    { return const_iterator { _data() + m_size }; }

    [[nodiscard]] constexpr bool empty() const noexcept
    { return m_size == 0; }
    constexpr size_type size() const noexcept
    { return m_size; }
    constexpr size_type capacity() const noexcept
    { return m_capacity; }

    constexpr void reserve(size_type new_cap)
    {
        if (new_cap > m_capacity)
            _reallocate_safe(new_cap);
    }

    constexpr void resize(size_type n)
    {
        _pre_resize(n);
        while (n > m_size)
            emplace_back();
    }
    constexpr void resize(size_type n, const value_type& value)
    {
        _pre_resize(n);
        while (n > m_size)
            emplace_back(value);
    }

    constexpr void shrink_to_fit()
    {
        if (m_size < m_capacity)
            _reallocate_safe(m_size);
    }
    constexpr void clear() noexcept
    { resize(0); }

    template <typename... Args>
    constexpr iterator emplace(const_iterator pos, Args&&... args)
    {
        size_type idx = pos - _data();

        if (!_data())
            reserve(1);

        if (m_size == m_capacity)
            reserve(m_capacity * 2);

        for (size_type i = m_size; i > idx; --i)
            alloc_traits::construct(_alloc(), _data() + i, std::move(_data()[i-1]));

        alloc_traits::construct(_alloc(), _data() + idx,
            std::forward<Args>(args)...);

        ++m_size;
        return iterator { _data() + idx };
    }

    constexpr iterator insert(const_iterator pos, T&& val)
    { return emplace(pos, std::move(val)); }
    constexpr iterator insert(const_iterator pos, const T& val)
    { return emplace(pos, val); }

    constexpr iterator insert(const_iterator pos, size_type n, const T& val)
    {
        if (!n)
            return pos;

        size_type idx = pos - _data();
        if (!pos)
            reserve(n);

        if (m_size + n > m_capacity)
            reserve(m_size + n);
        for (size_type i = m_size + n - 1; i >= idx + n; --i)
            alloc_traits::construct(_alloc(), _data() + i, std::move(_data()[i-n]));
        for (size_type i = idx; i < idx + n; ++i)
            alloc_traits::construct(_alloc(), _data() + i, val);
        m_size += n;
        return iterator { _data() + idx };
    }

    // TODO: LegacyInputIterator version of this
    template <typename ForwardIter>
    constexpr iterator insert(const_iterator pos,
        ForwardIter first, ForwardIter last)
    {
        size_type idx = pos - _data();
        size_type n = 0;

        ForwardIter tmp = first;
        while (tmp != last)
            ++n, ++tmp;

        if (!n)
            return pos;

        if (!pos)
            reserve(n);

        if (m_size + n > m_capacity)
            reserve(m_size + n);
        for (size_type i = m_size + n - 1; i >= idx + n; --i)
            alloc_traits::construct(_alloc(), _data() + i, std::move(_data()[i-n]));
        for (size_type i = idx; i < idx + n; ++i)
            alloc_traits::construct(_alloc(), _data() + i, *first++);
        m_size += n;
        return iterator { _data() + idx };
    }

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

    constexpr iterator erase(const_iterator pos)
    {
        size_type idx = pos - _data();
        alloc_traits::destroy(_alloc(), _data() + idx);
        for (size_type i = idx; i < m_size - 1; ++i)
            alloc_traits::construct(_alloc(), _data() + i, std::move(_data()[i+1]));
        --m_size;
        return iterator { _data() + idx };
    }

    constexpr iterator erase(const_iterator first, const_iterator last)
    {
        size_type n = last - first;
        if (!n)
            return last;

        size_type idx = first - _data();
        for (size_type i = idx; i < idx + n; ++i)
            alloc_traits::destroy(_alloc(), _data() + i);

        for (size_type i = idx; i < m_size - n; ++i)
            _alloc().construct(_data() + i, std::move(_data()[i+n]));

        m_size -= n;
        return iterator { _data() + idx };
    }

    constexpr void push_back(const T& val) { insert(cend(), val); }
    constexpr void push_back(T&& val) { insert(cend(), std::move(val)); }

    template <typename... Args>
    constexpr reference emplace_back(Args&&... args)
    { return *emplace(cend(), std::forward<Args>(args)...); }

    constexpr void pop_back() { erase(--cend()); }

    constexpr void swap(vector& other) noexcept(
        alloc_traits::propagate_on_container_swap::value
        || alloc_traits::is_always_equal::value)
    {
        if (alloc_traits::propagate_on_container_swap::value)
            std::swap(_alloc(), other.m_alloc);
        std::swap(_data(), other.m_data);
        std::swap(m_size, other.m_size);
        std::swap(m_capacity, other.m_capacity);
    }
};

template <typename T, typename Allocator>
constexpr void swap(
    std::vector<T, Allocator>& lhs,
    std::vector<T, Allocator>& rhs) noexcept(noexcept(lhs.swap(rhs)))
{ lhs.swap(rhs); }

template <typename T, typename Allocator, typename U>
constexpr typename std::vector<T, Allocator>::size_type
erase(std::vector<T, Allocator>& vec, const U& value)
{
    typename std::vector<T, Allocator>::size_type n = 0;

    for (auto iter = vec.begin(); iter != vec.end(); ) {
        if (*iter == value) {
            iter = vec.erase(iter);
            ++n;
        } else {
            ++iter;
        }
    }
    return n;
}

template <typename T, typename Allocator, typename Pred>
constexpr typename std::vector<T, Allocator>::size_type
erase_if(std::vector<T, Allocator>& vec, Pred pred)
{
    typename std::vector<T, Allocator>::size_type n = 0;

    for (auto iter = vec.begin(); iter != vec.end(); ) {
        if (pred(*iter)) {
            iter = vec.erase(iter);
            ++n;
        } else {
            ++iter;
        }
    }
    return n;
}

} // namespace std

#endif