vector.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_VECTOR_HPP__
#define NEFORCE_CORE_CONTAINER_VECTOR_HPP__

 
#include "NeForce/core/memory/memory_view.hpp"
#include "NeForce/core/memory/standard_allocator.hpp"
#include "NeForce/core/memory/uninitialized.hpp"
NEFORCE_BEGIN_NAMESPACE__


template <bool IsConst, typename Vector>
struct vector_iterator : iiterator<vector_iterator<IsConst, Vector>> {
public:
    using container_type = Vector;                                    
    using value_type = typename container_type::value_type;           
    using size_type = typename container_type::size_type;             
    using difference_type = typename container_type::difference_type; 
    using iterator_category = contiguous_iterator_tag;                
    using reference = conditional_t<IsConst, typename container_type::const_reference,
                                    typename container_type::reference>; 
    using pointer = conditional_t<IsConst, typename container_type::const_pointer,
                                  typename container_type::pointer>; 
 
private:
    pointer current_ = nullptr;                 
    const container_type* container_ = nullptr; 
 
public:
    NEFORCE_CONSTEXPR20 vector_iterator() noexcept = default;
    NEFORCE_CONSTEXPR20 ~vector_iterator() = default;
 
    NEFORCE_CONSTEXPR20 vector_iterator(const vector_iterator&) noexcept = default;
    NEFORCE_CONSTEXPR20 vector_iterator& operator=(const vector_iterator&) noexcept = default;
    NEFORCE_CONSTEXPR20 vector_iterator(vector_iterator&&) noexcept = default;
    NEFORCE_CONSTEXPR20 vector_iterator& operator=(vector_iterator&&) noexcept = default;

    NEFORCE_CONSTEXPR20 vector_iterator(pointer ptr, const container_type* vec) noexcept :
    current_(ptr),
    container_(vec) {}

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference dereference() const noexcept {
        NEFORCE_DEBUG_VERIFY(current_ && container_, "Attempting to dereference on a null pointer");
        NEFORCE_DEBUG_VERIFY(container_->start_ <= current_ && current_ < container_->finish_,
                             "Attempting to dereference out of boundary");
        return *current_;
    }

    NEFORCE_CONSTEXPR20 void increment() noexcept {
        NEFORCE_DEBUG_VERIFY(current_ && container_, "Attempting to increment a null pointer");
        NEFORCE_DEBUG_VERIFY(current_ < container_->finish_, "Attempting to increment out of boundary");
        ++current_;
    }

    NEFORCE_CONSTEXPR20 void decrement() noexcept {
        NEFORCE_DEBUG_VERIFY(current_ && container_, "Attempting to decrement a null pointer");
        NEFORCE_DEBUG_VERIFY(container_->start_ < current_, "Attempting to decrement out of boundary");
        --current_;
    }

    NEFORCE_CONSTEXPR20 void advance(difference_type off) noexcept {
        NEFORCE_DEBUG_VERIFY((current_ && container_) || off == 0, "Attempting to advance a null pointer");
        NEFORCE_DEBUG_VERIFY((off < 0 ? off >= container_->start_ - current_ : off <= container_->finish_ - current_),
                             "Attempting to advance out of boundary");
        current_ += off;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 difference_type distance_to(const vector_iterator& other) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == other.container_, "Attempting to distance to a different container");
        return static_cast<difference_type>(current_ - other.current_);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference operator[](difference_type off) noexcept { return *(*this + off); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool equal_to(const vector_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "Attempting to equal to a different container");
        return current_ == rhs.current_;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool less_than(const vector_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "Attempting to less than a different container");
        return current_ < rhs.current_;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 pointer base() const noexcept { return current_; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const container_type* container() const noexcept { return container_; }
};
 

template <typename T, typename Alloc = allocator<T>>
class vector : public icollector<vector<T, Alloc>> {
    static_assert(is_object_v<T>, "vector only contains object types.");
    static_assert(is_allocator_v<Alloc>, "Alloc type is not a standard allocator type.");
    static_assert(is_same_v<T, typename Alloc::value_type>, "allocator type mismatch.");
 
public:
    using pointer = T*;                                                       
    using reference = T&;                                                     
    using const_pointer = const T*;                                           
    using const_reference = const T&;                                         
    using value_type = T;                                                     
    using size_type = size_t;                                                 
    using difference_type = ptrdiff_t;                                        
    using iterator = vector_iterator<false, vector<T, Alloc>>;                
    using const_iterator = vector_iterator<true, vector<T, Alloc>>;           
    using reverse_iterator = _NEFORCE reverse_iterator<iterator>;             
    using const_reverse_iterator = _NEFORCE reverse_iterator<const_iterator>; 
    using allocator_type = Alloc;                                             
 
private:
    pointer start_ = nullptr;  
    pointer finish_ = nullptr; 
    compressed_pair<allocator_type, pointer> pair_{default_construct_tag{},
                                                   nullptr}; 
 
    template <bool, typename>
    friend struct vector_iterator;
 
public:
    static constexpr size_type npos = static_cast<size_type>(-1);
 
private:
    NEFORCE_CONSTEXPR20 void fill_initialize(size_type n, const T& value) {
        start_ = pair_.get_base().allocate(n);
        _NEFORCE uninitialized_fill_n(start_, n, value);
        finish_ = start_ + n;
        pair_.value = finish_;
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 pointer allocate_and_copy(size_type n, Iterator first, Iterator last) {
        NEFORCE_DEBUG_VERIFY(n < max_size(), "vector allocate out of allocate bounds.");
        pointer result = pair_.get_base().allocate(n);
        pointer finish = result;
        try {
            finish = _NEFORCE uninitialized_copy(first, last, result);
        } catch (...) {
            _NEFORCE destroy(result, finish);
            pair_.get_base().deallocate(result, n);
            throw;
        }
        return result;
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 pointer allocate_and_move(size_type n, Iterator first, Iterator last) {
        pointer result = pair_.get_base().allocate(n);
        pointer finish = result;
        try {
            finish = _NEFORCE uninitialized_move(first, last, result);
        } catch (...) {
            _NEFORCE destroy(result, finish);
            pair_.get_base().deallocate(result, n);
            throw;
        }
        return result;
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 enable_if_t<!is_ranges_fwd_iter_v<Iterator>> range_initialize(Iterator first, Iterator last) {
        for (; first != last; ++first) {
            vector::push_back(*first);
        }
        return;
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 enable_if_t<is_ranges_fwd_iter_v<Iterator>> range_initialize(Iterator first, Iterator last) {
        size_type n = _NEFORCE distance(first, last);
        start_ = vector::allocate_and_copy(n, first, last);
        finish_ = start_ + n;
        pair_.value = finish_;
        return;
    }

    NEFORCE_CONSTEXPR20 void deallocate() noexcept {
        if (start_) {
            pair_.get_base().deallocate(start_, pair_.value - start_);
        }
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 enable_if_t<!is_ranges_fwd_iter_v<Iterator>> range_insert(iterator position, Iterator first,
                                                                                  Iterator last) {
        while (first != last) {
            position = vector::insert(position, *first);
            ++position;
            ++first;
        }
        return;
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 enable_if_t<is_ranges_fwd_iter_v<Iterator>> range_insert(iterator position, Iterator first,
                                                                                 Iterator last) {
        if (first == last) {
            return;
        }
 
        const size_t n = _NEFORCE distance(first, last);
 
        if (static_cast<size_t>(pair_.value - finish_) >= n) {
            const size_t elems_after = end() - position;
            iterator old_finish = end();
 
            if (elems_after > n) {
                _NEFORCE uninitialized_copy(finish_ - n, finish_, finish_);
                finish_ += n;
                _NEFORCE copy_backward(position, old_finish - n, old_finish);
                _NEFORCE copy(first, last, position);
            } else {
                Iterator mid = first;
                _NEFORCE advance(mid, elems_after);
                _NEFORCE uninitialized_copy(mid, last, finish_);
                finish_ += (n - elems_after);
                _NEFORCE uninitialized_move(position, old_finish, finish_);
                finish_ += elems_after;
                _NEFORCE copy(first, mid, position);
            }
        } else {
            const size_type old_size = size();
            const size_type len = old_size + _NEFORCE max(old_size, n);
            pointer new_start = pair_.get_base().allocate(len);
            pointer new_finish = new_start;
 
            new_finish = _NEFORCE uninitialized_copy(begin(), position, new_start);
            new_finish = _NEFORCE uninitialized_copy(first, last, new_finish);
            new_finish = _NEFORCE uninitialized_copy(position, end(), new_finish);
 
            _NEFORCE destroy(start_, finish_);
            deallocate();
 
            start_ = new_start;
            finish_ = new_finish;
            pair_.value = new_start + len;
        }
        return;
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 enable_if_t<!is_ranges_fwd_iter_v<Iterator>> assign_aux(Iterator first, Iterator last) {
        clear();
        while (first != last) {
            vector::push_back(*first);
            ++first;
        }
        return;
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 enable_if_t<is_ranges_fwd_iter_v<Iterator>> assign_aux(Iterator first, Iterator last) {
        const size_t n = _NEFORCE distance(first, last);
        if (n > capacity()) {
            pointer new_start = vector::allocate_and_copy(n, first, last);
            _NEFORCE destroy(start_, finish_);
            deallocate();
            start_ = new_start;
            finish_ = start_ + n;
            pair_.value = start_ + n;
        } else if (n > size()) {
            Iterator mid = first;
            _NEFORCE advance(mid, size());
            _NEFORCE copy(first, mid, start_);
            finish_ = _NEFORCE uninitialized_copy(mid, last, finish_);
        } else {
            _NEFORCE copy(first, last, start_);
            vector::erase(begin() + n, end());
        }
        return;
    }
 
public:
    NEFORCE_CONSTEXPR20 vector() {
        constexpr size_type init_cap = 1;
        pointer result = pair_.get_base().allocate(init_cap);
        finish_ = start_ = result;
        pair_.value = finish_ + init_cap;
    }

    NEFORCE_CONSTEXPR20 explicit vector(const size_type n) {
        start_ = pair_.get_base().allocate(n);
        finish_ = start_;
        try {
            for (size_type i = 0; i < n; ++i) {
                _NEFORCE construct(finish_);
                ++finish_;
            }
        } catch (...) {
            _NEFORCE destroy(start_, finish_);
            pair_.get_base().deallocate(start_, n);
            throw;
        }
        pair_.value = start_ + n;
    }

    NEFORCE_CONSTEXPR20 explicit vector(const size_type n, const T& value) { vector::fill_initialize(n, value); }

    NEFORCE_CONSTEXPR20 explicit vector(const int32_t n, const T& value) { vector::fill_initialize(n, value); }

    NEFORCE_CONSTEXPR20 explicit vector(const int64_t n, const T& value) { vector::fill_initialize(n, value); }

    NEFORCE_CONSTEXPR20 vector(const vector& other) {
        const size_type n = other.size();
        start_ = vector::allocate_and_copy(n, other.begin(), other.end());
        finish_ = start_ + n;
        pair_.value = finish_;
    }

    NEFORCE_CONSTEXPR20 vector& operator=(const vector& other) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
 
        vector::clear();
        vector::insert(end(), other.cbegin(), other.cend());
        return *this;
    }

    NEFORCE_CONSTEXPR20
    vector(vector&& other) noexcept(is_nothrow_swappable_v<compressed_pair<allocator_type, pointer>>) {
        vector::swap(other);
    }

    NEFORCE_CONSTEXPR20 vector&
    operator=(vector&& other) noexcept(is_nothrow_destructible_v<value_type> &&
                                       is_nothrow_swappable_v<compressed_pair<allocator_type, pointer>>) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
 
        vector::clear();
        vector::swap(other);
        return *this;
    }

    template <typename Iterator, enable_if_t<is_ranges_iter_v<Iterator>, int> = 0>
    NEFORCE_CONSTEXPR20 vector(Iterator first, Iterator last) {
        vector::range_initialize(first, last);
    }

    template <typename Iterator>
    NEFORCE_CONSTEXPR20 vector(Iterator first, const size_type n) :
    vector(first, _NEFORCE next(first, n)) {}

    NEFORCE_CONSTEXPR20 vector(std::initializer_list<T> ilist) :
    vector(ilist.begin(), ilist.end()) {}

    NEFORCE_CONSTEXPR20 vector(memory_view<T> view) :
    vector(view.begin(), view.end()) {}

    NEFORCE_CONSTEXPR20 vector& operator=(std::initializer_list<T> ilist) {
        if (ilist.size() > capacity()) {
            pointer new_ = vector::allocate_and_move(ilist.end() - ilist.begin(), ilist.begin(), ilist.end());
            _NEFORCE destroy(start_, finish_);
            deallocate();
            start_ = new_;
            finish_ = start_ + ilist.size();
            pair_.value = start_ + ilist.size();
        } else if (size() >= ilist.size()) {
            iterator i = _NEFORCE copy(ilist.begin(), ilist.end(), begin());
            _NEFORCE destroy(i.base(), finish_);
        } else {
            _NEFORCE copy(ilist.begin(), ilist.begin() + size(), start_);
            _NEFORCE uninitialized_copy(ilist.begin() + size(), ilist.end(), finish_);
        }
        finish_ = start_ + ilist.size();
        return *this;
    }

    NEFORCE_CONSTEXPR20 ~vector() {
        clear();
        deallocate();
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 iterator begin() noexcept { return iterator(start_, this); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 iterator end() noexcept { return iterator(finish_, this); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_iterator begin() const noexcept { return cbegin(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_iterator end() const noexcept { return cend(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reverse_iterator rend() noexcept { return reverse_iterator(begin()); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reverse_iterator rbegin() const noexcept { return crbegin(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reverse_iterator rend() const noexcept { return crend(); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_iterator cbegin() const noexcept {
        return const_iterator(start_, this);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_iterator cend() const noexcept { return const_iterator(finish_, this); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reverse_iterator crbegin() const noexcept {
        return const_reverse_iterator(cend());
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reverse_iterator crend() const noexcept {
        return const_reverse_iterator(cbegin());
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 size_type size() const noexcept {
        return static_cast<size_type>(finish_ - start_);
    }

    NEFORCE_NODISCARD static constexpr size_type max_size() noexcept { return static_cast<size_type>(-1) / sizeof(T); }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 size_type capacity() const noexcept {
        return static_cast<size_type>(pair_.value - start_);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool empty() const noexcept { return start_ == finish_; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 pointer data() noexcept { return start_; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_pointer data() const noexcept { return start_; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 memory_view<T> view() noexcept { return {start_, size()}; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 memory_view<const T> view() const noexcept { return {start_, size()}; }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 memory_view<T> view(const size_type off, size_type count = npos) noexcept {
        count = _NEFORCE min(count, size() - off);
        return {start_ + off, count};
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 memory_view<const T> view(const size_type off,
                                                                    size_type count = npos) const noexcept {
        count = _NEFORCE min(count, size() - off);
        return {start_ + off, count};
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference front() noexcept {
        NEFORCE_DEBUG_VERIFY(!empty(), "front called on empty vector");
        return *start_;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reference front() const noexcept {
        NEFORCE_DEBUG_VERIFY(!empty(), "front called on empty vector");
        return *start_;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference back() noexcept {
        NEFORCE_DEBUG_VERIFY(!empty(), "back called on empty vector");
        return *(finish_ - 1);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reference back() const noexcept {
        NEFORCE_DEBUG_VERIFY(!empty(), "back called on empty vector");
        return *(finish_ - 1);
    }

    NEFORCE_CONSTEXPR20 void reserve(const size_type n) {
        NEFORCE_DEBUG_VERIFY(n < max_size(), "vector reserve out of allocate bounds.");
        if (capacity() >= n) {
            return;
        }
 
        size_type new_capacity = _NEFORCE max(capacity() * 2, n);
        pointer new_start = pair_.get_base().allocate(new_capacity);
        pointer new_finish = new_start;
 
        try {
            new_finish = _NEFORCE uninitialized_move(start_, finish_, new_start);
        } catch (...) {
            _NEFORCE destroy(new_start, new_finish);
            pair_.get_base().deallocate(new_start, new_capacity);
            throw;
        }
 
        _NEFORCE destroy(start_, finish_);
        deallocate();
        start_ = new_start;
        finish_ = new_finish;
        pair_.value = start_ + new_capacity;
    }

    NEFORCE_CONSTEXPR20 void resize(size_type new_size, const T& value) {
        if (new_size < size()) {
            vector::erase(begin() + new_size, end());
        } else {
            vector::insert(end(), new_size - size(), value);
        }
    }

    NEFORCE_CONSTEXPR20 void resize(const size_type new_size) { vector::resize(new_size, T()); }

    template <typename... Args>
    NEFORCE_CONSTEXPR20 void emplace(iterator position, Args&&... args) {
        if (finish_ != pair_.value) {
            if (position == end()) {
                _NEFORCE construct(finish_, _NEFORCE forward<Args>(args)...);
                ++finish_;
            } else {
                _NEFORCE construct(finish_, _NEFORCE move(*(finish_ - 1)));
                ++finish_;
                pointer pos_ptr = position.base();
                _NEFORCE move_backward(pos_ptr, finish_ - 2, finish_ - 1);
                _NEFORCE construct(pos_ptr, _NEFORCE forward<Args>(args)...);
            }
            return;
        }
 
        const size_type old_size = size();
        const size_type new_cap = old_size != 0 ? 2 * old_size : 1;
        pointer new_start = pair_.get_base().allocate(new_cap);
        pointer new_finish = new_start;
 
        try {
            new_finish = _NEFORCE uninitialized_move(begin(), position, new_start);
            _NEFORCE construct(new_finish, _NEFORCE forward<Args>(args)...);
            ++new_finish;
            new_finish = _NEFORCE uninitialized_move(position, end(), new_finish);
        } catch (...) {
            _NEFORCE destroy(new_start, new_finish);
            pair_.get_base().deallocate(new_start, new_cap);
            throw;
        }
 
        _NEFORCE destroy(begin(), end());
        deallocate();
 
        start_ = new_start;
        finish_ = new_finish;
        pair_.value = new_start + new_cap;
    }

    template <typename... Args>
    NEFORCE_CONSTEXPR20 void emplace_back(Args&&... args) {
        if (finish_ != pair_.value) {
            _NEFORCE construct(finish_, _NEFORCE forward<Args>(args)...);
            ++finish_;
        } else {
            vector::emplace(end(), _NEFORCE forward<Args>(args)...);
        }
    }

    NEFORCE_CONSTEXPR20 void push_back(const T& value) { vector::emplace_back(value); }

    NEFORCE_CONSTEXPR20 void push_back(T&& value) { vector::emplace_back(_NEFORCE move(value)); }

    NEFORCE_CONSTEXPR20 void pop_back() noexcept(is_nothrow_destructible_v<T>) {
        NEFORCE_DEBUG_VERIFY(!empty(), "pop called in an empty vector")
        _NEFORCE destroy(finish_ - 1);
        --finish_;
    }

    NEFORCE_CONSTEXPR20 T pop_back_v() noexcept(is_nothrow_destructible_v<T> && is_nothrow_move_constructible_v<T>) {
        NEFORCE_DEBUG_VERIFY(!empty(), "pop called in an empty vector")
        T value{_NEFORCE move(*(finish_ - 1))};
        _NEFORCE destroy(finish_ - 1);
        --finish_;
        return _NEFORCE move(value);
    }

    NEFORCE_CONSTEXPR20 void assign(size_type n, const value_type& value) {
        if (n > capacity()) {
            pointer new_start = pair_.get_base().allocate(n);
            pointer new_finish = new_start;
 
            try {
                new_finish = _NEFORCE uninitialized_fill_n(new_start, n, value);
            } catch (...) {
                _NEFORCE destroy(new_start, new_finish);
                pair_.get_base().deallocate(new_start, n);
                throw;
            }
 
            _NEFORCE destroy(start_, finish_);
            deallocate();
 
            start_ = new_start;
            finish_ = new_finish;
            pair_.value = start_ + n;
        } else if (n > size()) {
            _NEFORCE fill(begin(), end(), value);
            finish_ = _NEFORCE uninitialized_fill_n(finish_, n - size(), value);
        } else {
            _NEFORCE fill_n(begin(), n, value);
            vector::erase(begin() + n, end());
        }
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    NEFORCE_CONSTEXPR20 void assign(Iterator first, Iterator last) {
        vector::assign_aux(first, last);
    }

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

    NEFORCE_CONSTEXPR20 iterator insert(iterator position, const value_type& value) {
        size_type n = position - begin();
        vector::emplace(position, value);
        return begin() + n;
    }

    NEFORCE_CONSTEXPR20 iterator insert(iterator position, value_type&& value) {
        size_type n = position - begin();
        vector::emplace(position, _NEFORCE move(value));
        return begin() + n;
    }

    NEFORCE_CONSTEXPR20 iterator insert(iterator position) { return vector::insert(position, T()); }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    NEFORCE_CONSTEXPR20 void insert(iterator position, Iterator first, Iterator last) {
        vector::range_insert(position, first, last);
    }

    NEFORCE_CONSTEXPR20 void insert(iterator position, std::initializer_list<value_type> ilist) {
        vector::insert(position, ilist.begin(), ilist.end());
    }

    NEFORCE_CONSTEXPR20 void insert(iterator position, size_type n, const value_type& value) {
        if (n == 0) {
            return;
        }
 
        if (static_cast<size_type>(pair_.value - finish_) >= n) {
            const size_type elems_after = end() - position;
            iterator old_finish = end();
 
            if (elems_after > n) {
                _NEFORCE uninitialized_move(old_finish - n, old_finish, old_finish);
                finish_ += n;
                _NEFORCE move_backward(position, old_finish - n, old_finish);
                _NEFORCE fill_n(position, n, value);
            } else {
                _NEFORCE uninitialized_fill_n(finish_, n - elems_after, value);
                finish_ += n - elems_after;
                _NEFORCE uninitialized_move(position, old_finish, finish_);
                finish_ += elems_after;
                _NEFORCE fill(position, old_finish, value);
            }
        } else {
            const size_type old_size = size();
            const size_type len = old_size + _NEFORCE max(old_size, n);
 
            pointer new_start = pair_.get_base().allocate(len);
            pointer new_finish = _NEFORCE uninitialized_copy(begin(), position, new_start);
            new_finish = _NEFORCE uninitialized_fill_n(new_finish, n, value);
            new_finish = _NEFORCE uninitialized_copy(position, end(), new_finish);
 
            _NEFORCE destroy(start_, finish_);
            deallocate();
 
            start_ = new_start;
            finish_ = new_finish;
            pair_.value = new_start + len;
        }
    }

    NEFORCE_CONSTEXPR20 iterator erase(iterator first,
                                       iterator last) noexcept(is_nothrow_move_assignable_v<value_type> &&
                                                               is_nothrow_destructible_v<value_type>) {
        NEFORCE_DEBUG_VERIFY(_NEFORCE distance(first, last) >= 0, "vector erase out of ranges.");
 
        const auto elems_after = end() - last;
        if (elems_after > 0) {
            _NEFORCE move_backward(last, end(), first + elems_after);
        }
 
        pointer new_finish = finish_ - (last - first);
        _NEFORCE destroy(new_finish, finish_);
        finish_ = new_finish;
        return first;
    }

    NEFORCE_CONSTEXPR20 iterator erase(iterator position) noexcept(is_nothrow_move_assignable_v<value_type>) {
        if (position + 1 != end()) {
            _NEFORCE move(position + 1, end(), position);
        }
 
        --finish_;
        _NEFORCE destroy(finish_);
        return position;
    }

    NEFORCE_CONSTEXPR20 void shrink_to_fit() {
        if (capacity() == size()) {
            return;
        }
 
        if (size() == 0) {
            deallocate();
            start_ = finish_ = pair_.value = nullptr;
            return;
        }
 
        pointer new_start = pair_.get_base().allocate(size());
        pointer new_finish = new_start;
 
        try {
            new_finish = _NEFORCE uninitialized_move(start_, finish_, new_start);
        } catch (...) {
            _NEFORCE destroy(new_start, new_finish);
            pair_.get_base().deallocate(new_start, size());
            throw;
        }
 
        _NEFORCE destroy(start_, finish_);
        deallocate();
 
        start_ = new_start;
        finish_ = new_finish;
        pair_.value = new_start + size();
    }

    NEFORCE_CONSTEXPR20 void clear() noexcept(is_nothrow_destructible_v<value_type>) {
        if (empty()) {
            return;
        }
 
        _NEFORCE destroy(start_, finish_);
        finish_ = start_;
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reference at(const size_type position) const noexcept {
        NEFORCE_DEBUG_VERIFY(position < size(), "vector access out of range");
        return *(start_ + position);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference at(const size_type position) noexcept {
        NEFORCE_DEBUG_VERIFY(position < size(), "vector access out of range");
        return *(start_ + position);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 const_reference operator[](const size_type position) const noexcept {
        return at(position);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 reference operator[](const size_type position) noexcept {
        return at(position);
    }

    NEFORCE_CONSTEXPR20 void swap(vector& other) noexcept(is_nothrow_swappable_v<allocator_type>) {
        if (_NEFORCE addressof(other) == this) {
            return;
        }
 
        _NEFORCE swap(start_, other.start_);
        _NEFORCE swap(finish_, other.finish_);
        _NEFORCE swap(pair_, other.pair_);
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool equal_to(const vector& rhs) const
            noexcept(noexcept(_NEFORCE equal(cbegin(), cend(), rhs.cbegin()))) {
        return size() == rhs.size() && _NEFORCE equal(cbegin(), cend(), rhs.cbegin());
    }

    NEFORCE_NODISCARD NEFORCE_CONSTEXPR20 bool less_than(const vector& rhs) const
            noexcept(noexcept(_NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend()))) {
        return _NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend());
    }
};
 
#ifdef NEFORCE_STANDARD_17
template <typename T, typename Alloc>
vector(T, Alloc = Alloc()) -> vector<T, Alloc>;
 
template <typename Iterator, typename Alloc>
vector(Iterator, Iterator, Alloc = Alloc()) -> vector<iter_value_t<Iterator>, Alloc>;
#endif

using byte_vector = vector<byte_t>;
 // Container
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_VECTOR_HPP__