vector_stacked.h

/*  -*- C++ -*-
 * vector_stacked.h
 * 
 * Copyright 2018,2020 Daniel Kondor <kondor.dani@gmail.com>
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following disclaimer
 *   in the documentation and/or other materials provided with the
 *   distribution.
 * * Neither the name of the  nor the names of its
 *   contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * 
 */


#ifndef VECTOR_STACKED_H
#define VECTOR_STACKED_H

#include <limits>
#include <new>
#include <stdexcept>
#include <vector>
#include <type_traits>
#include <iterator>
#include <stdlib.h>
#include <string.h>


/* constexpr if support only for c++17 or newer */
#if __cplusplus >= 201703L
#define CONSTEXPR constexpr
#else
#define CONSTEXPR
#endif

#ifdef USE_LIBDIVIDE
#include "libdivide.h"
namespace stacked_vector {
    
    struct divider {
        size_t n;
        libdivide::divider<size_t> div;
        
        explicit divider(size_t x):n(x),div(x) { }
        
        bool operator == (size_t x) const { return n == x; }
        bool operator != (size_t x) const { return n != x; }
        bool operator < (size_t x) const { return n < x; }
        bool operator <= (size_t x) const { return n <= x; }
        bool operator > (size_t x) const { return n > x; }
        bool operator >= (size_t x) const { return n >= x; }
    };
    
    size_t operator / (size_t x, const divider& d) { return x / d.div; }
    size_t& operator /= (size_t& x, const divider& d) { x /= d.div; return x; }
    size_t operator * (size_t x, const divider& d) { return x * d.n; }
    size_t& operator *= (size_t& x, const divider& d) { x *= d.n; return x; }
    
    size_t operator + (size_t x, const divider& d) { return x + d.n; }
    size_t& operator += (size_t& x, const divider& d) { x += d.n; return x; }
    size_t operator - (size_t x, const divider& d) { return x - d.n; }
    size_t& operator -= (size_t& x, const divider& d) { x -= d.n; return x; }
    
    bool operator == (size_t x, const divider& d) { return d == x; }
    bool operator != (size_t x, const divider& d) { return d != x; }
    bool operator > (size_t x, const divider& d) { return d < x; }
    bool operator >= (size_t x, const divider& d) { return d <= x; }
    bool operator < (size_t x, const divider& d) { return d > x; }
    bool operator <= (size_t x, const divider& d) { return d >= x; }
    
}
#endif


namespace stacked_vector {

        template<class It>
        struct at_least_forward_iterator {
            constexpr static bool value =
                std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::forward_iterator_tag >::value ||
                std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::bidirectional_iterator_tag >::value ||
                std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::random_access_iterator_tag >::value
#if __cplusplus >= 202000L
                || std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::contiguous_iterator_tag >::value
#endif
                ;
        };
        template<class It>
        struct at_least_input_iterator {
            constexpr static bool value = at_least_forward_iterator<It>::value || 
                std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::input_iterator_tag >::value;
        };
        

template <class T>
using std_vector_wrapper = std::vector<T>;

template <class T, template<class> class vector_type = std_vector_wrapper>
class vector {
    protected:
        vector_type<T*> stack;
        size_t p_size; 
        size_t p_capacity; 
        size_t p_stack_size; 
#ifdef USE_LIBDIVIDE
        divider max_grow;
#else
        size_t max_grow; 
#endif
        static constexpr size_t p_max_capacity = std::numeric_limits<size_t>::max() / sizeof(T);
                
        template<class U = T>
        bool copy_or_move(U* target, size_t new_size,
                typename std::enable_if< std::is_nothrow_move_constructible<U>::value >::type* = 0) {
            size_t i;
            for(i=0;i<p_size;i++) {
                if(i<new_size) new(target + i) U(std::move(stack[0][i]));
                stack[0][i].~U();
            }
            return true;
        }
        template<class U = T>
        bool copy_or_move(U* target, size_t new_size,
                typename std::enable_if< ! std::is_nothrow_move_constructible<U>::value >::type* = 0) {
            size_t copy_size = p_size < new_size ? p_size : new_size;
            U* tmp = std::uninitialized_copy(stack[0], stack[0] + copy_size, target);
            if(tmp != target + copy_size) return false;
            for(size_t i=0;i<p_size;i++) stack[0][i].~U();
        }
        
        bool change_size(size_t new_size) {
            if(new_size > max_grow) return false;
            if(new_size == p_stack_size) return true;
            T* new_array = (T*)malloc(sizeof(T)*new_size);
            if(!new_array) return false;
            if(stack.size() == 0) {
                try {
                    stack.push_back(new_array);
                }
                catch(std::bad_alloc& x) {
                    free(new_array);
                    return false;
                }
            }
            else {
                if(!copy_or_move<T>(new_array,new_size)) {
                    free(new_array);
                    return false;
                }
                free(stack[0]);
                stack[0] = new_array;
            }
            p_capacity = new_size;
            p_stack_size = new_size;
            if(new_size < p_size) p_size = new_size;
            return true;
        }
        bool grow_vector(size_t minimum_size = 0) {
            size_t new_size = minimum_size;
            if(!new_size) {
                if(p_stack_size == max_grow) return grow_one();
                new_size = p_stack_size*2UL;
                if(!new_size) new_size = 1UL;
            }
            if(new_size > max_grow) 
#ifdef USE_LIBDIVIDE
                new_size = max_grow.n;
#else
                new_size = max_grow;
#endif      
            if(!change_size(new_size)) return false;
            while(minimum_size > p_capacity) if(!grow_one()) return false;
            return true;
        }
        
        bool grow_one() {
            // maximum number of elements in stack such that p_capacity will not overflow
            size_t max_stack_size = std::numeric_limits<size_t>::max() / p_stack_size;
            if(stack.size() >= max_stack_size) return false;
            T* new_array = (T*)malloc(sizeof(T)*p_stack_size);
            if(!new_array) return false;
            try {
                stack.push_back(new_array);
            }
            catch(std::bad_alloc& x) {
                free(new_array);
                return false;
            }
            p_capacity += p_stack_size;
            return true;
        }
        
        std::pair<size_t,size_t> get_indices(size_t i) const {
#ifdef USE_LIBDIVIDE
            size_t i1 = i / max_grow;
            size_t i2 = (i - i1*max_grow);
#else
            size_t i1 = i / max_grow;
            size_t i2 = i % max_grow;
#endif
            return std::pair<size_t,size_t>(i1,i2);
        }
        
        T* get_addr(size_t i) { auto x = get_indices(i); return stack[x.first] + x.second; }        
        const T* get_addr(size_t i) const { auto x = get_indices(i); return stack[x.first] + x.second; }        
        T& get_ref(size_t i) { auto x = get_indices(i); return stack[x.first][x.second]; }      
        const T& get_ref(size_t i) const { auto x = get_indices(i); return stack[x.first][x.second]; }
    
    public:
        /* types */
        typedef T value_type;
        typedef size_t size_type;
        typedef ssize_t difference_type;
        typedef T& reference;
        typedef const T& const_reference;
        typedef T* pointer;
        typedef const T* const_pointer; 
        
        /* Constructors */
        
        vector() noexcept : p_size(0),p_capacity(0),p_stack_size(0),max_grow(131072) { }
        explicit vector(size_t count, const T& value = T(), size_t max_grow_ = 131072);
        template<class It, typename std::enable_if<at_least_input_iterator<It>::value, int>::type = 0>
        vector(It first, It last, size_t max_grow_ = 131072);
        vector(const vector& v);
        vector(vector&& v);
        /* 5. assignment */
        vector& operator = (const vector& v);
        vector& operator = (vector&& v);
        /* 6. swap */
        void swap(vector& v);
        
        /* Destructor */
        ~vector() {
            /* call destructors of existing elements -- these are not allowed to throw an exception! */
            if(p_size) resize(0);
            for(auto x : stack) free(x);
        }
        
        
        /* Basic access to members */
        
        size_t size() const { return p_size; }
        size_t capacity() const { return p_capacity; }
        size_t max_size() const { return p_max_capacity; }
        size_t max_capacity() const { return p_max_capacity; }
        bool empty() const { return p_size == 0; }
        size_t get_stack_array_size() const {
#ifdef USE_LIBDIVIDE
            return max_grow.n;
#else
            return max_grow;
#endif
        }
        
        
        
        /* data access functions
         * similarly to std::vector, only at() checks bounds, all other versions
         * result in undefined behavior if an out of bounds is attempted */
        
        T& operator[](size_t i) { return get_ref(i); }
        const T& operator[](size_t i) const { return get_ref(i); }
        T& at(size_t i) { if(i < p_size) return get_ref(i); throw std::out_of_range("vector::at(): index out of range!\n"); }
        const T& at(size_t i) const { if(i < p_size) return get_ref(i); throw std::out_of_range("vector::at(): index out of range!\n"); }
        T& front() { return stack[0][0]; }
        const T& front() const { return stack[0][0]; }
        T& back() { return get_ref(p_size-1); }
        const T& back() const { return get_ref(p_size-1); }
        
        /* reserve memory */
        bool reserve_nothrow(size_t n);
        void reserve(size_t n) { if(!reserve_nothrow(n)) throw std::bad_alloc(); }
        void shrink_to_fit(size_t new_capacity = 0);
        
        /* insert /create elements at the end of the vector
         * versions that throw an exception if out of memory */
        void push_back(const T& x);
        void push_back(T&& x);
        template<class... Args> T& emplace_back(Args&&... args);
        /* versions that return false if out of memory -- note: any exceptions
         * from T's (copy / move) constructor are propagated, i.e. still can
         * throw an exception if those throw */
        bool push_back_nothrow(const T& x);
        bool push_back_nothrow(T&& x);
        template<class... Args> bool emplace_back_nothrow(Args&&... args);
        
        /* remove elements -- T's destructor should not throw exception! */
        void clear() { while(p_size) pop_back(); }
        void pop_back() {
            if(p_size) {
                --p_size;
                get_ref(p_size).~T();
            }
        }
        
        bool resize_nothrow(size_t count);
        bool resize_nothrow(size_t count, const T& x);
        void resize(size_t count) { if(!resize_nothrow(count)) throw std::bad_alloc(); }
        void resize(size_t count, const T& x) { if(!resize_nothrow(count,x)) throw std::bad_alloc(); }
    
    protected:  
        template<bool is_const>
        class iterator_base {
            public:
                typedef std::random_access_iterator_tag iterator_category;
                typedef T value_type;
                typedef T* pointer;
                typedef T& reference;
                typedef ssize_t difference_type;
                /*
      typedef typename _Iterator::iterator_category iterator_category;
      typedef typename _Iterator::value_type        value_type;
      typedef typename _Iterator::difference_type   difference_type;
      typedef typename _Iterator::pointer           pointer;
      typedef typename _Iterator::reference         reference;
    */
    
                friend class iterator_base<!is_const>;
                friend class vector<T,vector_type>;
            
            protected:
                typedef typename std::conditional<is_const, const vector, vector>::type vector_type1;
                vector_type1* v;
                size_t pos;
                
                /* make non-const iterator from const iterator -- only possible from within the vector 
                template<bool is_const_ = is_const>
                iterator_base(const iterator_base<true>& it, typename std::enable_if<is_const_>::type* = 0 ):v(it.v),pos(it.pos) { } */
                                
            public:
                iterator_base():v(0),pos(0) { }
                explicit iterator_base(vector_type1& v_, size_t pos_ = 0):v(&v_),pos(pos_) { }
                explicit iterator_base(vector_type1* v_, size_t pos_ = 0):v(v_),pos(pos_) { }
                
                /* any iterator can be copied from non-const iterator;
                 * this is not explicit so comparison operators can auto-convert */
                iterator_base(const iterator_base<false>& it):v(it.v),pos(it.pos) { }
                /* only const iterator can be copied from const iterator */
                template<bool is_const_ = is_const>
                iterator_base(const iterator_base<true>& it, typename std::enable_if<is_const_>::type* = 0 ):v(it.v),pos(it.pos) { }
                
                
                
                reference operator * () {
                    return (*v)[pos];
                }
                pointer operator -> () {
                    return &((*v)[pos]);
                }

                template<bool is_const2> bool operator == (const iterator_base<is_const2>& i) const { return pos == i.pos; }

                template<bool is_const2> bool operator != (const iterator_base<is_const2>& i) const { return pos != i.pos; }
                
                template<bool is_const2> bool operator < (const iterator_base<is_const2>& i) const { return pos < i.pos; }
                template<bool is_const2> bool operator > (const iterator_base<is_const2>& i) const { return pos > i.pos; }
                template<bool is_const2> bool operator <= (const iterator_base<is_const2>& i) const { return pos <= i.pos; }
                template<bool is_const2> bool operator >= (const iterator_base<is_const2>& i) const { return pos >= i.pos; }
                
                iterator_base& operator ++() { ++pos; return *this; }
                iterator_base operator ++(int) { iterator_base<is_const> i(*this); ++pos; return i; }
                iterator_base& operator --() { --pos; return *this; }
                iterator_base operator --(int) { iterator_base<is_const> i(*this); --pos; return i; }
                
                iterator_base& operator +=(ssize_t i) { pos += i; return *this; }
                iterator_base& operator -=(ssize_t i) { pos -= i; return *this; }
                iterator_base operator +(ssize_t i) const { iterator_base<is_const> it(*this); it += i; return it; }
                iterator_base operator -(ssize_t i) const { iterator_base<is_const> it(*this); it -= i; return it; }
                
                template<bool is_const2> ssize_t operator - (const iterator_base<is_const2>& i) const {
                    return ((ssize_t)pos) - ((ssize_t)(i.pos));
                }
                
                typename std::conditional<is_const, const reference, reference>::type operator [] (ssize_t i) { return (*v)[pos+i]; }
        };
        
        bool insert_helper(size_t pos, size_t new_pos);
        
        iterator_base<false> make_iterator(size_t pos) { return iterator_base<false>(*this,pos); }
        iterator_base<false> make_iterator(iterator_base<true> pos) { return iterator_base<false>(*this,pos.pos); }
        iterator_base<true> make_iterator(size_t pos) const { return iterator_base<true>(*this,pos); }
    
    public:
        typedef iterator_base<false> iterator;
        typedef iterator_base<true> const_iterator;
        
        iterator begin() { return iterator(*this,0); } 
        const_iterator begin() const { return const_iterator(*this,0); } 
        const_iterator cbegin() const { return const_iterator(*this,0); } 
        iterator end() { return iterator(*this,p_size); } 
        const_iterator end() const { return const_iterator(*this,p_size); } 
        const_iterator cend() const { return const_iterator(*this,p_size); } 
        
        iterator erase(const_iterator pos); 
        iterator erase(const_iterator first, const_iterator last); 
        
        /* inserts that do not throw exception when out of memory,
         * instead they return whether the insert was successful
         * the res iterator is updated to point to the inserted element
         * if the insert is successful, otherwise it is not changed */
         
        bool insert_nothrow(const_iterator pos, iterator& res, const T& x);
        bool insert_nothrow(const_iterator pos, iterator& res, T&& x);
        bool insert_nothrow(const_iterator pos, iterator& res, size_t count, const T& x);
        template<class InputIt, typename std::enable_if<at_least_input_iterator<InputIt>::value, int>::type = 0>
        bool insert_nothrow(const_iterator pos, iterator& res, InputIt first, InputIt last);

        iterator insert(const_iterator pos, const T& x) {
            iterator res;
            if(insert_nothrow(pos,res,x)) return res;
            else throw std::bad_alloc();
        }
        iterator insert(const_iterator pos, T&& x) {
            iterator res;
            if(insert_nothrow(pos,res,std::forward<T>(x))) return res;
            else throw std::bad_alloc();
        }
        iterator insert(const_iterator pos, size_t count, const T& x) {
            iterator res;
            if(insert_nothrow(pos,res,count,x)) return res;
            else throw std::bad_alloc();
        }
        template<class InputIt, typename std::enable_if<at_least_input_iterator<InputIt>::value, int>::type = 0>
        iterator insert(const_iterator pos, InputIt first, InputIt last) {
            iterator res;
            if(insert_nothrow(pos,res,first,last)) return res;
            else throw std::bad_alloc();
        }
};


template <class T, template<class> class vector_type>
auto operator + (ssize_t i, const typename vector<T,vector_type>::iterator& it) -> typename vector<T,vector_type>::iterator {
    typename vector<T,vector_type>::iterator it2(it);
    it2 += i;
    return it2;
}

template <class T, template<class> class vector_type>
auto operator + (ssize_t i, const typename vector<T,vector_type>::const_iterator& it) -> typename vector<T,vector_type>::const_iterator {
    typename vector<T,vector_type>::const_iterator it2(it);
    it2 += i;
    return it2;
}



/* Constructors */
template <class T, template<class> class vt>
vector<T,vt>::vector(size_t count, const T& value, size_t max_grow_) :
        p_size(0),p_capacity(0),p_stack_size(0),max_grow(max_grow_) {
    reserve(count);
    for(;p_size < count; ++p_size) new(get_addr(p_size)) T(value);
}

template <class T, template<class> class vt> template<class It,
    typename std::enable_if< at_least_input_iterator<It>::value, int>::type >
vector<T,vt>::vector(It first, It last, size_t max_grow_) :
         p_size(0),p_capacity(0),p_stack_size(0),max_grow(max_grow_) {
    for(; first != last; ++first) push_back(*first);
}

template <class T, template<class> class vt>
vector<T,vt>::vector(const vector<T,vt>& v) : p_size(0),p_capacity(0),p_stack_size(0),max_grow(v.max_grow) {
    reserve(v.size());
    for(;p_size < v.size(); ++p_size) new(get_addr(p_size)) T(v[p_size]);
}

template <class T, template<class> class vt>
void vector<T,vt>::swap(vector<T,vt>& v) {
    using std::swap;
    swap(stack, v.stack);
    swap(p_size, v.p_size);
    swap(p_capacity, v.p_capacity);
    swap(p_stack_size, v.p_stack_size);
    swap(max_grow, v.max_grow);
}

template <class T, template<class> class vt>
vector<T,vt>::vector(vector<T,vt>&& v) : p_size(0),p_capacity(0),p_stack_size(0),max_grow(v.max_grow) {
    swap(v);
}

template <class T, template<class> class vt>
vector<T,vt>& vector<T,vt>::operator = (const vector<T,vt>& v) {
    resize(0);
    shrink_to_fit(v.size());
    reserve(v.size());
    for(;p_size < v.size(); ++p_size) new(get_addr(p_size)) T(v[p_size]);
    return *this;
}

template <class T, template<class> class vt>
vector<T,vt>& vector<T,vt>::operator = (vector<T,vt>&& v) {
    resize(0);
    for(auto x : stack) free(x);
    stack.resize(0);
    swap(v);
}

template <class T, template<class> class vt>
bool vector<T,vt>::reserve_nothrow(size_t n) {
    if(n > p_max_capacity) return false;
    if(n <= p_capacity) return true;
    return grow_vector(n);
}

template <class T, template<class> class vt>
void vector<T,vt>::shrink_to_fit(size_t new_capacity) {
    if(new_capacity < p_size) new_capacity = p_size;
    if(new_capacity > p_capacity) return;
    if(new_capacity > max_grow) {
#ifdef USE_LIBDIVIDE
        size_t tmp = new_capacity / max_grow;
        if(new_capacity - tmp*max_grow) new_capacity += max_grow;
#else
        if(new_capacity % max_grow) new_capacity += max_grow;
#endif
        while(p_capacity > new_capacity) {
            free(stack.back());
            stack.pop_back();
            p_capacity -= max_grow;
        }
    }
    else {
        size_t new_stack_size = (new_capacity > 0)?1:0;
        for(size_t i = new_stack_size; i < stack.size(); i++) free(stack[i]);
        stack.resize(new_stack_size);
        if(new_capacity) change_size(new_capacity);
    }
    stack.shrink_to_fit();
}


/* insert /create elements at the end of the vector */
template <class T, template<class> class vt>
void vector<T,vt>::push_back(const T& x) {
    if(!push_back_nothrow(x)) throw std::bad_alloc();
}
template <class T, template<class> class vt>
void vector<T,vt>::push_back(T&& x) {
    if(!push_back_nothrow(std::forward<T>(x))) throw std::bad_alloc();
}
template<class T, template<class> class vt> template<class... Args>
T& vector<T,vt>::emplace_back(Args&&... args) {
    if(!emplace_back_nothrow(std::forward<Args>(args)...)) throw std::bad_alloc();
    return back();
}
template <class T, template<class> class vt>
bool vector<T,vt>::push_back_nothrow(const T& x) {
    if(p_size == p_capacity) if(!grow_vector()) return false;
    new(get_addr(p_size)) T(x); /* copy constructor -- might still throw an exception */
    p_size++;
    return true;
}
template <class T, template<class> class vt>
bool vector<T,vt>::push_back_nothrow(T&& x) {
    if(p_size == p_capacity) if(!grow_vector()) return false;
    new(get_addr(p_size)) T(std::forward<T>(x)); /* move constructor -- might throw an exception */
    p_size++;
    return true;
}
template<class T, template<class> class vt> template<class... Args>
bool vector<T,vt>::emplace_back_nothrow(Args&&... args) {
    if(p_size == p_capacity) if(!grow_vector()) return false;
    new(get_addr(p_size)) T(std::forward<Args>(args)...); /* constructor -- might throw an exception */
    p_size++;
    return true;
}



template <class T, template<class> class vt>
bool vector<T,vt>::resize_nothrow(size_t count) {
    if(count == p_size) return true;
    if(!count) { clear(); return true; }
    if(count < p_size) {
        do { pop_back(); } while(p_size > count);
        return true;
    }
    /* here count > p_size */
    if(count > p_capacity) if(!grow_vector(count)) return false;
    for(; p_size < count; p_size++) new(get_addr(p_size)) T();
    return true;
}
template <class T, template<class> class vt>
bool vector<T,vt>::resize_nothrow(size_t count, const T& x) {
    if(count == p_size) return true;
    if(!count) { clear(); return true; }
    if(count < p_size) {
        do { pop_back(); } while(p_size > count);
        return true;
    }
    /* here count > p_size */
    if(count > p_capacity) if(!grow_vector(count)) return false;
    for(; p_size < count; p_size++) new(get_addr(p_size)) T(x);
    return true;
}


template <class T, template<class> class vt>
typename vector<T,vt>::iterator vector<T,vt>::erase(vector<T,vt>::const_iterator pos) {
    if(pos.pos >= p_size) throw std::out_of_range("vector::erase(): iterator out of bounds!\n");
    for(size_t p2 = pos.pos; p2 + 1 < p_size; p2++) get_ref(p2) = std::move(get_ref(p2+1));
    p_size--;
    get_ref(p_size).~T();
    return make_iterator(pos.pos);
}
template <class T, template<class> class vt>
typename vector<T,vt>::iterator vector<T,vt>::erase(vector<T,vt>::const_iterator first, vector<T,vt>::const_iterator last) {
    if(first.pos >= p_size) throw std::out_of_range("vector::erase(): iterator out of bounds!\n");
    ssize_t dist = last - first;
    if(!dist) return make_iterator(first);
    if(dist < 0) throw std::out_of_range("vector::erase(): invalid iterators!\n");
    for(size_t p2 = first.pos; p2 + dist < p_size; p2++) get_ref(p2) = std::move(get_ref(p2+dist));
    
    size_t new_size = p_size - dist;
    for(;p_size > new_size; --p_size) get_ref(p_size-1).~T();
    return make_iterator(first);
}
        


/* move elements to new position from given position
 * requires that new_pos >= pos and p_size > pos */
template <class T, template<class> class vt>
bool vector<T,vt>::insert_helper(size_t pos, size_t new_pos) {
    size_t diff = new_pos - pos;
    if(p_size > p_max_capacity - diff || !reserve_nothrow(p_size + diff)) return false;
    size_t remaining = p_size - pos;
    
    for(size_t i = 0; i < diff; i++) {
        size_t j = p_size + i;
        new(get_addr(j)) T(std::move(get_ref( p_size - diff + i )));
    }
    for(size_t i = p_size - diff; i > pos; i--) get_ref(i - 1UL + diff) = std::move(get_ref(i - 1UL));
    p_size += diff;
    return true;
}



template <class T, template<class> class vt>
bool vector<T,vt>::insert_nothrow(vector<T,vt>::const_iterator pos, vector<T,vt>::iterator& res, const T& x) {
    res = make_iterator(pos);
    if(pos == cend()) return push_back_nothrow(x);
    if(!insert_helper(pos.pos,pos.pos+1)) return false;
    get_ref(pos.pos) = x;
    return true;
}

template <class T, template<class> class vt>
bool vector<T,vt>::insert_nothrow(vector<T,vt>::const_iterator pos, vector<T,vt>::iterator& res, T&& x) {
    res = make_iterator(pos);
    if(pos == cend()) return push_back_nothrow(std::forward<T>(x));
    if(!insert_helper(pos.pos,pos.pos+1)) return false;
    get_ref(pos.pos) = std::move(x);
    return true;
}


template <class T, template<class> class vt>
bool vector<T,vt>::insert_nothrow(vector<T,vt>::const_iterator pos, vector<T,vt>::iterator& res, size_t count, const T& x) {
    res = make_iterator(pos);
    if(pos == cend()) return resize_nothrow(p_size + count, x);
    if(!insert_helper(pos.pos,pos.pos+count)) return false;
    for(size_t i = 0; i < count; i++) get_ref(pos.pos + i) = x;
    return true;
}


template <class T, template<class> class vt> template<class InputIt,
    typename std::enable_if<at_least_input_iterator<InputIt>::value, int>::type >
bool vector<T,vt>::insert_nothrow(vector<T,vt>::const_iterator pos, vector<T,vt>::iterator& res, InputIt first, InputIt last) {
    res = make_iterator(pos);
    if(first != last) {
        if CONSTEXPR(at_least_forward_iterator<InputIt>::value) {
            ssize_t dist = std::distance(first,last);
            if(dist < 0) return false;
            
            if(pos == cend()) {
                if(!reserve_nothrow(p_size + dist)) return false;
                for(; first != last; ++first) push_back(*first);
                return true;
            }
            
            if(!insert_helper(pos.pos,pos.pos+dist)) return false;
            for(size_t i = pos.pos; first != last; ++first, i++) get_ref(i) = *first;
        }
        else {
            vector<T,vt>::iterator tmp;
            for(size_t i = pos.pos; first != last; ++first, i++)
                if(!insert_nothrow(vector<T,vt>::iterator(*this,i),tmp,*first)) return false;
        }
    }
    return true;
}



} // namespace stacked_vector

#undef CONSTEXPR

#endif