C++杂交容器 vector+deque(veque)
_Kagamine_Rin_ · · 科技·工程
考虑到审核的原因，该文章不一定会实时更新。建议前往 luogu.me 观看。
创作原因（2025/8/26 11:34）：
@_Kagamine_Rin_ : 会慢得跟屎一样，最关键的是我要封装 || @AKPC : 用数组手写双端队列 || @_Kagamine_Rin_ : vector 在首尾添加很慢，deque 随机访问很慢，那能不能把这两个 STL 结合起来？？
我认为这个容器需要达到下列要求：
- 大部分操作需要不慢于
vector和deque的对应操作 - 所有操作需要比
vector和deque对应操作中的其中一个快 sizeof(veque) <= 40- 代码长度
\le 10240 \texttt{ Bytes} - 最低能够在
C++11 (GCC 7)的编译条件下运行
历史版本 0.9.0-beta
当前版本 0.9.1-beta
该版本已经达成了前三个目标。
sizeof(veque) == 32- 代码长度缩短至 24k，仍然未达成
- 目前至少需要 C++17 (GCC 7)，未达成
更新内容：
- 移除了原先与很多 STL 不兼容的情况。
- 仅对
private部分的函数或变量进行缩写，不影响使用。
#ifndef VEQUE_HEADER_GUARD
#define VEQUE_HEADER_GUARD
#include<algorithm>
#include<cstddef>
#include<cstring>
#include<iterator>
#include<limits>
#include<ratio>
#include<string>
#include<type_traits>
#include<stdexcept>
#include<utility>
//
namespace veque{
struct fast_resize_traits{
using allocation_before_front=std::ratio<1>;
using allocation_after_back=std::ratio<1>;
static constexpr auto resize_from_closest_side=true;
};
struct vector_compatible_resize_traits{
using allocation_before_front=std::ratio<1>;
using allocation_after_back=std::ratio<1>;
static constexpr auto resize_from_closest_side=false;
};
struct std_vector_traits{
using allocation_before_front=std::ratio<0>;
using allocation_after_back=std::ratio<1>;
static constexpr auto resize_from_closest_side=false;
};
struct no_reserve_traits{
using allocation_before_front=std::ratio<0>;
using allocation_after_back=std::ratio<0>;
static constexpr auto resize_from_closest_side=false;
};
template<typename T,typename RT=fast_resize_traits,typename Alc=std::allocator<T>>
class veque{
public:
using allocator_type=Alc;
using alloc_traits=std::allocator_traits<allocator_type>;
using value_type=T;
using reference=T&;
using const_reference=const T&;
using pointer=T*;
using const_pointer=const T*;
using iterator=T*;
using const_iterator=const T*;
using reverse_iterator=std::reverse_iterator<iterator>;
using const_reverse_iterator=std::reverse_iterator<const_iterator>;
using difference_type=std::ptrdiff_t;
using size_type=std::size_t;
using ssize_type=std::ptrdiff_t;
veque()noexcept(noexcept(Alc())):veque(Alc()){}
explicit veque(const Alc&a)noexcept:_data{0,a}{}
explicit veque(size_type n,const Alc&a=Alc()):veque(_aut{},n,a){_vcr(begin(),end());}
veque(size_type n,const T&value,const Alc&a=Alc()):veque(_aut{},n,a){_vcr(begin(),end(),value);}
template<typename It,typename ItCat=typename std::iterator_traits<It>::iterator_category>veque(It b,It e,const Alc&a=Alc()):veque(b,e,a,ItCat{}){}
veque(std::initializer_list<T>lst,const Alc&a=Alc()):veque(_aut{},lst.size(),a){_ccr(lst.begin(),lst.end(),begin());}
veque(const veque&o):veque(_aut{},o.size(),alloc_traits::select_on_container_copy_construction(o._al())){_ccr(o.begin(),o.end(),begin());}
template<typename ORT>veque(const veque<T,ORT,Alc>&o):veque(_aut{},o.size(),alloc_traits::select_on_container_copy_construction(o._al())){_ccr(o.begin(),o.end(),begin());}
template<typename ORT>veque(const veque<T,ORT,Alc>&o,const Alc&a):veque(_aut{},o.size(),a){_ccr(o.begin(),o.end(),begin());}
veque(veque&&o)noexcept{_swa(std::move(o));}
template<typename ORT>veque(veque<T,ORT,Alc>&&o)noexcept{_swa(std::move(o));}
template<typename ORT>veque(veque<T,ORT,Alc>&&o,const Alc&a)noexcept:veque(a){
if constexpr(!alloc_traits::is_always_equal::value)if(a!=o._al()){
auto _=veque(_aut{},o.size(),a);
_nmcr(o.begin(),o.end(),_.begin());
_swoa(std::move(_));return;
}_swoa(std::move(o));
}
~veque(){_d(begin(),end());}
veque&operator=(const veque&o){return _ca(o);}
template<typename ORT>veque&operator=(const veque<T,ORT,Alc>&o){return _ca(o);}
veque&operator=(veque&&o)noexcept(noexcept(alloc_traits::propagate_on_container_move_assignment::value||alloc_traits::is_always_equal::value)){return _ma(std::move(o));}
template<typename ORT>veque&operator=(veque<T,ORT,Alc>&&o)noexcept(noexcept(alloc_traits::propagate_on_container_move_assignment::value||alloc_traits::is_always_equal::value)){return _ma(std::move(o));}
veque&operator=(std::initializer_list<T>lst){_a(lst.begin(),lst.end());return*this;}
void assign(size_type cnt,const T&value){if(cnt>capacity_full())_swoa(veque(cnt,value,_al()));else _res(cnt,value);}
template<typename It,typename ItCat=typename std::iterator_traits<It>::iterator_category>void assign(It b,It e){_a(b,e,ItCat{});}
void assign(std::initializer_list<T>lst){_a(lst.begin(),lst.end());}
allocator_type get_allocator()const{return _al();}
reference at(size_type idx){if(idx>=size()){throw std::out_of_range("veque<T,ResizeTraits,Alloc>::at("+std::to_string(idx)+") out of range");}return(*this)[idx];}
const_reference at(size_type idx)const{if(idx>=size()){throw std::out_of_range("veque<T,ResizeTraits,Alloc>::at("+std::to_string(idx)+") out of range");}return(*this)[idx];}
reference operator[](size_type idx){return*(begin()+idx);}
const_reference operator[](size_type idx)const{return*(begin()+idx);}
reference front(){return(*this)[0];}
const_reference front()const{return(*this)[0];}
reference back(){return(*this)[size()-1];}
const_reference back()const{return(*this)[size()-1];}
T*data()noexcept{return begin();}
const T*data()const noexcept{return begin();}
const_iterator cbegin()const noexcept{return _sb()+_offset;}
iterator begin()noexcept{return _sb()+_offset;}
const_iterator begin()const noexcept{return cbegin();}
const_iterator cend()const noexcept{return _sb()+_offset+size();}
iterator end()noexcept{return _sb()+_offset+size();}
const_iterator end()const noexcept{return cend();}
const_reverse_iterator crbegin()const noexcept{return const_reverse_iterator(cend());}
reverse_iterator rbegin()noexcept{return reverse_iterator(end());}
const_reverse_iterator rbegin()const noexcept{return crbegin();}
const_reverse_iterator crend()const noexcept{return const_reverse_iterator(cbegin());}
reverse_iterator rend()noexcept{return reverse_iterator(begin());}
const_reverse_iterator rend()const noexcept{return crend();}
[[nodiscard]]bool empty()const noexcept{return size()==0;}
size_type size()const noexcept{return _size;}
ssize_type ssize()const noexcept{return _size;}
size_type max_size()const noexcept{
constexpr auto compile_time_limit=std::min(std::numeric_limits<ssize_type>::max()/sizeof(T),std::numeric_limits<size_type>::max()/_full_realloc::num);
auto runtime_limit=alloc_traits::max_size(_al());
return std::min(compile_time_limit,runtime_limit);
}
void reserve(size_type front,size_type back){
if(front>capacity_front() || back>capacity_back()){
auto allocated_before_begin=std::max(capacity_front(),front)-size();
auto allocated_after_begin=std::max(capacity_back(),back);
auto new_full_capacity=allocated_before_begin+allocated_after_begin;
if(new_full_capacity>max_size())
throw std::length_error("veque<T,ResizeTraits,Alloc>::reserve("+std::to_string(front)+","+std::to_string(back)+") exceeds max_size()");
_re(new_full_capacity,allocated_before_begin);
}
}
void reserve_front(size_type cnt){reserve(cnt,0);}
void reserve_back(size_type cnt){reserve(0,cnt);}
void reserve(size_type cnt){reserve(cnt,cnt);}
size_type capacity_front()const noexcept{return _offset+size();}
size_type capacity_back()const noexcept{return capacity_full()-_offset;}
size_type capacity_full()const noexcept{return _data._allocated;}
size_type capacity()const noexcept{return capacity_back();}
void shrink_to_fit(){if(size()<capacity_full())_re(size(),0);}
void clear() noexcept{
_d(begin(),end());
_size=0;
_offset=0;
if constexpr(std::ratio_greater_v<_unused_realloc,std::ratio<0>>){
using unused_front_ratio=std::ratio_divide<_front_realloc,_unused_realloc>;
_offset=capacity_full()*unused_front_ratio::num/unused_front_ratio::den;
}
}
iterator insert(const_iterator it,const T&value){return emplace(it,value);}
iterator insert(const_iterator it,T&&value){return emplace(it,std::move(value));}
iterator insert(const_iterator it,size_type cnt,const T&value){auto res=_is(it,cnt);_vcr(res,res+cnt,value);return res;}
template<typename It,typename ItCat=typename std::iterator_traits<It>::iterator_category>iterator insert(const_iterator it,It b,It e){return _i(it,b,e,ItCat{});}
iterator insert(const_iterator it,std::initializer_list<T>lst){return insert(it,lst.begin(),lst.end());}
template<typename...Args>
iterator emplace(const_iterator it,Args&&...args){
auto res=_is(it,1);
alloc_traits::construct(_al(),res,std::forward<Args>(args)...);
return res;
}
iterator erase(const_iterator it){return erase(it,std::next(it));}
iterator erase(const_iterator b,const_iterator e){
auto cnt=std::distance(b,e);
if constexpr(_rfcs){
auto elements_before=std::distance(cbegin(),b);
auto elements_after=std::distance(e,cend());
if( elements_before<elements_after){
_shb(begin(),b,cnt);
_mb(cnt);
return _mi(e);
}
}
_shf(e,end(),cnt);
_me(-cnt);
return _mi(b);
}
void push_back(const T&value){emplace_back(value);}
void push_back(T&&value){emplace_back(std::move(value));}
template<typename...Args>reference emplace_back(Args&&...args){
if(size()==capacity_back())_resab(size()+1);
alloc_traits::construct(_al(),end(),std::forward<Args>(args)...);
_me(1);
return back();
}
void push_front(const T&value){emplace_front(value);}
void push_front(T&&value){emplace_front(std::move(value));}
template<typename...Args>reference emplace_front(Args&&...args){
if(size()==capacity_front())_resaf(size()+1);
alloc_traits::construct(_al(),begin()-1,std::forward<Args>(args)...);
_mb(-1);
return front();
}
void pop_back(){alloc_traits::destroy(_al(),&back());_me(-1);}
T pop_back_element(){auto res(_ncm(back()));pop_back();return res;}
void pop_front(){alloc_traits::destroy(_al(),&front());_mb(1);}
T pop_front_element(){auto res(_ncm(front()));pop_front();return res;}
void resize_front(size_type cnt){_rf(cnt);}
void resize_front(size_type cnt,const T&value){_rf(cnt,value);}
void resize_back(size_type cnt){_rb(cnt);}
void resize_back(size_type cnt,const T&value){_rb(cnt,value);}
void resize(size_type cnt){_rb(cnt);}
void resize(size_type cnt,const T&value){_rb(cnt,value);}
template<typename ORT>void swap(veque<T,ORT,Alc>&o)noexcept(noexcept(alloc_traits::propagate_on_container_swap::value||alloc_traits::is_always_equal::value)){
if constexpr(alloc_traits::propagate_on_container_swap::value)_swa(std::move(o));
else{
if(_al()==o._al())_swoa(std::move(o));
else{
auto new_this=veque(_aut{},o.size(),_al());_nmcr(o.begin(),o.end(),new_this.begin());
auto new_o=veque(_aut{},size(),o._al());_nmcr(begin(),end(),new_o.begin());
_swoa(std::move(new_this));o._swoa(std::move(new_o));
}
}
}
private:
using _front_realloc=typename RT::allocation_before_front::type;
using _back_realloc=typename RT::allocation_after_back::type;
using _unused_realloc=std::ratio_add<_front_realloc,_back_realloc>;
using _full_realloc=std::ratio_add<std::ratio<1>,_unused_realloc>;
static constexpr auto _rfcs=RT::resize_from_closest_side;
static_assert(_front_realloc::den>0 );
static_assert(_back_realloc::den>0 );
static_assert(std::ratio_greater_equal_v<_front_realloc,std::ratio<0>>,"Reserving negative space is not well-defined");
static_assert(std::ratio_greater_equal_v<_back_realloc,std::ratio<0>>,"Reserving negative space is not well-defined");
static_assert(std::ratio_greater_equal_v<_unused_realloc,std::ratio<0>>,"Reserving negative space is not well-defined");
static constexpr auto _cdcd=std::is_same_v<allocator_type,std::allocator<T>>;
static constexpr auto _cccd=std::is_same_v<allocator_type,std::allocator<T>>;
static constexpr auto _cdd=std::is_same_v<allocator_type,std::allocator<T>>;
size_type _size=0;
size_type _offset=0;
struct Data:Alc{
T*_storage=nullptr;
size_type _allocated=0;
Data()=default;
Data(size_type size,const Alc&a):Alc{a},_storage{size?std::allocator_traits<Alc>::allocate(allocator(),size):nullptr},_allocated{size}{}
Data(const Data&)=delete;
Data(Data&&o){*this=std::move(o);}
~Data(){if(_storage)std::allocator_traits<Alc>::deallocate(allocator(),_storage,_allocated);}
Data&operator=(const Data&)=delete;
Data&operator=(Data&&o){
using std::swap;
if constexpr(!std::is_empty_v<Alc>)swap(allocator(),o.allocator());
swap(_allocated,o._allocated);
swap(_storage,o._storage);
return*this;
}
Alc&allocator(){return*this;}
const Alc&allocator()const{return*this;}
} _data;
template<typename It>veque(It b,It e,const Alc&a,std::input_iterator_tag):veque{a}{for(;b!=e;++b){push_back(*b);}}
template<typename It>veque(It b,It e,const Alc&a,std::forward_iterator_tag):veque(_aut{},std::distance(b,e),a){_ccr(b,e,begin());}
struct _aut{};
struct _rut{};
veque(_aut,size_type size,size_type allocated,size_type offset,const Alc&a):_size{size},_offset{offset},_data{allocated,a}{}
veque(_aut,size_type size,const Alc&a):veque(_aut{},size,size,0,a){}
veque(_rut,size_type size,const Alc&a):veque(_aut{},size,_cr(size),_co(size),a){}
static constexpr size_type _cr(size_type size){return size*_full_realloc::num/_full_realloc::den;}
static constexpr size_type _co(size_type size){return size*_front_realloc::num/_front_realloc::den;}
Alc&_al()noexcept{return _data.allocator();}
const Alc&_al()const noexcept{return _data.allocator();}
void _d(const_iterator b,const_iterator e){
if constexpr(std::is_trivially_destructible_v<T>&&_cdd){(void)b;(void)e;}
else{
auto start=_mi(b);
for(auto i=start;i!=e;++i)alloc_traits::destroy(_al(),i);
}
}
template<typename ORT>veque&_ca(const veque<T,ORT,Alc>&o){
if constexpr(alloc_traits::propagate_on_container_copy_assignment::value)
if constexpr(!alloc_traits::is_always_equal::value)
if(o._al()!=_al() || o.size()>capacity_full()){_swa(veque(o,o._al()));return *this;}
if(o.size()>capacity_full())_swoa(veque(o,_al()));
else _res(o.begin(),o.end());
return *this;
}
template<typename ORT>veque&_ma(veque<T,ORT,Alc>&&o)noexcept(noexcept(alloc_traits::propagate_on_container_move_assignment::value||alloc_traits::is_always_equal::value)){
if constexpr(!alloc_traits::is_always_equal::value){
if(_al()!=o._al()){
if constexpr(alloc_traits::propagate_on_container_move_assignment::value)_swa(std::move(o));
else{
if(o.size()>capacity_full())_swoa(veque(std::move(o),_al()));
else _res(std::move_iterator(o.begin()),std::move_iterator(o.end()));
}
return *this;
}
}
_swoa(std::move(o));
return *this;
}
template<typename...Args>void _vcr(const_iterator b,const_iterator e,const Args&...args){
static_assert(sizeof...(args)<=1,"This is for default-or copy-constructing");
if constexpr(std::is_trivially_copy_constructible_v<T>&&_cdcd){
if constexpr(sizeof...(args)==0)std::memset(_mi(b),0,std::distance(b,e)*sizeof(T));
else std::fill(_mi(b),_mi(e),args...);
}
else for(auto dest=_mi(b);dest!=e;++dest) alloc_traits::construct(_al(),dest,args...);
}
template<typename It>void _ccr(It b,It e,const_iterator dest){
static_assert(std::is_convertible_v<typename std::iterator_traits<It>::iterator_category,std::forward_iterator_tag>);
if constexpr(std::is_trivially_copy_constructible_v<T>&&_cccd)std::memcpy(_mi(dest),b,std::distance(b,e)*sizeof(T));
else for(;b!=e;++dest,++b)alloc_traits::construct(_al(),dest,*b);
}
template<typename It>void _a(It b,It e){
static_assert(std::is_convertible_v<typename std::iterator_traits<It>::iterator_category,std::forward_iterator_tag>);
if(std::distance(b,e)>static_cast<difference_type>(capacity_full()))_swoa(veque(b,e,_al()));
else _res(b,e);
}
template<typename It>void _a(It b,It e,std::forward_iterator_tag){_a(b,e);}
template<typename It>void _a(It b,It e,std::input_iterator_tag){clear();for(;b!=e;++b)push_back(*b);}
template<typename It>iterator _i(const_iterator it,It b,It e){
static_assert(std::is_convertible_v<typename std::iterator_traits<It>::iterator_category,std::forward_iterator_tag>);
auto res=_is(it,std::distance(b,e));
_ccr(b,e,res);
return res;
}
template<typename It>iterator _i(const_iterator it,It b,It e,std::forward_iterator_tag){return _i(it,b,e);}
template<typename It>iterator _i(const_iterator it,It b,It e,std::input_iterator_tag){auto allocated=veque(b,e);_i(it,allocated.begin(),allocated.end());}
template<typename ORT>void _swa(veque<T,ORT,Alc>&&o)noexcept{
std::swap(_size,o._size);
std::swap(_offset,o._offset);
std::swap(_data,o._data);
}
template<typename ORT>void _swoa(veque<T,ORT,Alc>&&o)noexcept{
std::swap(_size,o._size);
std::swap(_offset,o._offset);
std::swap(_data._allocated,o._data._allocated);
std::swap(_data._storage,o._data._storage);
}
template<typename...Args>void _rf(size_type cnt,const Args&...args){
difference_type delta=cnt-size();
if(delta>0){
if(cnt>capacity_front())_resaf(cnt);
_vcr(begin()-delta,begin(),args...);
}
else _d(begin(),begin()-delta);
_mb(-delta);
}
template<typename...Args>void _rb(size_type cnt,const Args&...args){
difference_type delta=cnt-size();
if(delta>0){
if(cnt>capacity_back())_resab(cnt);
_vcr(end(),end()+delta,args...);
}
else _d(end()+delta,end());
_me(delta);
}
void _resab(size_type cnt){
auto storage_needed=_cr(cnt);
auto current_capacity=capacity_full();
auto new_offset=_co(cnt);
if(storage_needed<=current_capacity){
auto distance=_offset-new_offset;
_shf(begin(),end(),distance );
_mb(-distance);
_me(-distance);
}
else _re(storage_needed,new_offset);
}
void _resaf(size_type cnt){
auto storage_needed=_cr(cnt);
auto current_capacity=capacity_full();
auto new_offset=cnt-size()+_co(cnt);
if(storage_needed<=current_capacity){
auto distance=new_offset-_offset;
_shb(begin(),end(),distance);
_mb(distance);
_me(distance);
}
else _re(storage_needed,new_offset);
}
void _re(size_type allocated,size_type offset){
auto tmp=veque(_aut{},size(),allocated,offset,_al());
_nmcr(begin(),end(),tmp.begin());
_swoa(std::move(tmp));
}
iterator _is(const_iterator it,size_type cnt){
auto required_size=size()+cnt;
auto can_shift_back=capacity_back()>=required_size;
if constexpr(std::ratio_greater_v<_front_realloc,std::ratio<0>>)
if(can_shift_back&&it==begin())can_shift_back=false;
if constexpr(_rfcs){
auto can_shift_front=capacity_front()>=required_size;
if constexpr(std::ratio_greater_v<_back_realloc,std::ratio<0>>)
if(can_shift_front&&it==end())can_shift_front=false;
if(can_shift_back&&can_shift_front){
auto index=std::distance(cbegin(),it);
if(index<=ssize()/2)can_shift_back=false;
else can_shift_front=false;
}
if(can_shift_front){_shf(begin(),it,cnt);_mb(-cnt);return _mi(it)-cnt;}
}
if(can_shift_back){_shb(it,end(),cnt);_me(cnt);return _mi(it);}
auto tmp=veque(_rut{},required_size,_al());
auto index=std::distance(cbegin(),it);
auto insertion_point=begin()+index;
_nmcr(begin(),insertion_point,tmp.begin());
_nmcr(insertion_point,end(),tmp.begin()+index+cnt);
_swa(std::move(tmp));
return begin()+index;
}
void _shf(const_iterator b,const_iterator e,size_type cnt){
if(e==begin())return;
auto element_cnt=std::distance(b,e);
auto start=_mi(b);
if(element_cnt>0){
auto dest=start-cnt;
if constexpr(std::is_trivially_copyable_v<T>&&std::is_trivially_copy_constructible_v<T>&&_cccd)std::memmove(dest,start,element_cnt*sizeof(T));
else{
auto src=start;
auto dest_construct_end=std::min(begin(),_mi(e)-cnt);
for(;dest<dest_construct_end;++src,++dest)_nmc(dest,src);
for(;src!=e;++src,++dest)_nma(dest,src);
}
}
_d(std::max(cbegin(),e-cnt),e);
}
void _shb(const_iterator b,const_iterator e,size_type cnt){
auto start=_mi(b);
if(b==end())return;
auto element_cnt=std::distance(b,e);
if(element_cnt>0){
if constexpr(std::is_trivially_copyable_v<T>&&std::is_trivially_copy_constructible_v<T>&&_cccd)std::memmove(start+cnt,start,element_cnt*sizeof(T));
else{
auto src=_mi(e-1);
auto dest=src+cnt;
auto dest_construct_end=std::max(end()-1,dest-element_cnt);
for(;dest>dest_construct_end;--src,--dest)_nmc(dest,src);
for(;src!=b-1;--src,--dest)_nma(dest,src);
}
}
_d(b,std::min(cend(),b+cnt));
}
template<typename It>void _res(It b,It e){
static_assert(std::is_convertible_v<typename std::iterator_traits<It>::iterator_category,std::forward_iterator_tag>);
auto cnt=std::distance(b,e);
auto size_delta=static_cast<difference_type>(cnt-size());
auto ib=_sb()+(capacity_full()-cnt)/2;
if(size()==0)_ccr(b,e,ib);
else if(size_delta==0){std::copy(b,e,begin());return;}
else if(size_delta<0){
ib=std::clamp(ib,begin(),end()-cnt);_d(begin(),ib);
auto ideal_end=std::copy(b,e,ib);_d(ideal_end,end());
}
else{
ib=std::clamp(ib,end()-cnt,begin());
auto src=b;
auto copy_src=src+std::distance(ib,begin());_ccr(src,copy_src,ib);
std::copy(copy_src,copy_src+ssize(),begin());_ccr(copy_src+ssize(),e,end());
}
_mb(std::distance(begin(),ib));
_me(std::distance(end(),ib+cnt));
}
void _res(size_type cnt,const T&value){
auto size_delta=static_cast<difference_type>(cnt-size());
auto ib=_sb();
if constexpr(std::ratio_greater_v<_unused_realloc,std::ratio<0>>){
using ideal_begin_ratio=std::ratio_divide<_front_realloc,_unused_realloc>;
ib+=(capacity_full()-cnt)*ideal_begin_ratio::num/ideal_begin_ratio::den;
}
if(size()==0)_vcr(ib,ib+cnt,value);
else if(size_delta==0){std::fill(begin(),end(),value);return;}
else if(size_delta<0){
ib=std::clamp(ib,begin(),end()-cnt);_d(begin(),ib);
std::fill(ib,ib+cnt,value);_d(ib+cnt,end());
}else{
ib+=_co(capacity_full()-cnt)/2;_vcr(ib,begin(),value);
std::fill(begin(),end(),value);_vcr(end(),ib+cnt,value);
}
_mb(std::distance(begin(),ib));
_me(std::distance(end(),ib+cnt));
}
static decltype(auto)_ncm(T&t){
if constexpr(std::is_nothrow_move_constructible_v<T>)return std::move(t);
else return t;
}
void _nmc(iterator dest,iterator src){
if constexpr(std::is_trivially_copy_constructible_v<T>&&_cccd)*dest=*src;
else alloc_traits::construct(_al(),dest,_ncm(*src));
}
void _nmcr(iterator b,iterator e,iterator dest){
auto size=std::distance(b,e);
if(size){
if constexpr(std::is_trivially_copy_constructible_v<T>&&_cccd)std::memcpy(dest,b,size*sizeof(T));
else for(;b!=e;++dest,++b)_nmc(dest,b);
}
}
static void _nma(iterator dest,iterator src){if constexpr(std::is_nothrow_move_assignable_v<T>)*dest=std::move(*src);else*dest=*src;}
static void _nmar(iterator b,iterator e,iterator src){for(auto dest=b;dest!=e;++dest,++src)_nma(dest,src);}
void _mb(difference_type cnt)noexcept{_size-=cnt;_offset+=cnt;}
void _me(difference_type cnt)noexcept{_size+=cnt;}
iterator _mi(const_iterator i){return begin()+std::distance(cbegin(),i);}
const_iterator _sb()const noexcept{return _data._storage;}
iterator _sb()noexcept{return _data._storage;}
};
#define tp template<typename T,typename LRT,typename LA,typename RRT,typename RA>
#define arg const veque<T,LRT,LA>&lhs,const veque<T,RRT,RA>&rhs
tp inline bool operator==(arg){return std::equal(lhs.begin(),lhs.end(),rhs.begin(),rhs.end());}
tp inline bool operator!=(arg){return!(lhs==rhs);}
tp inline bool operator<(arg){return std::lexicographical_compare(lhs.begin(),lhs.end(),rhs.begin(),rhs.end());}
tp inline bool operator<=(arg){return!(rhs<lhs);}
tp inline bool operator>(arg){return(rhs<lhs);}
tp inline bool operator>=(arg){return!(lhs<rhs);}
#undef tp
#undef arg
template<typename T,typename RT,typename A>inline void swap(veque<T,RT,A>&lhs,veque<T,RT,A>&rhs)noexcept(noexcept(lhs.swap(rhs))){lhs.swap(rhs);}
template<typename It,typename A=std::allocator<typename std::iterator_traits<It>::value_type>>veque(It,It,A=A())->veque<typename std::iterator_traits<It>::value_type,fast_resize_traits,A>;
}
namespace std{
template<typename T,typename RT,typename A>struct hash<veque::veque<T,RT,A>>{
size_t operator()(const veque::veque<T,RT,A>&v)const{
size_t hash=0; auto hasher=std::hash<T>();
for(auto&&val:v) hash^=hasher(val)+0x9e3779b9+(hash<<6)+(hash>>2);
return hash;
}
};
}
#endif
int main(){
}
/*
被更改的变量名
InputIt->It
(L/R)Alloc->A
Allocator->Alc
alloc->a
(L/R/Other)ResizeTraits->RT
ideal_begin->ib
count->cnt
_allocate_uninitialized_tag->_aut
_reallocate_uninitialized_tag->_rut
replacement->tmp
Other->O
other->o
_storage_begin->_sb
_mutable_iterator->_mi
_move_end->_me
_move_begin->_mb
_nothrow_move_assign_range->_nmar
_nothrow_move_assign->_nma
_nothrow_move_construct_range->_nmcr
_nothrow_move_construct->_nmc
_nothrow_construct_move->_ncm
_reassign_existing_storage->_res
_shift_back->_shb
_shift_front->_shf
_insert_storage->_is
_reallocate->_re
_reallocate_space_at_front->_resaf
_reallocate_space_at_back->_resab
_resize_back->_rb
_resize_front->_rf
_swap_without_allocator->_swoa
_swap_with_allocator->_swa
_insert->_i
_assign->_a
_copy_construct_range->_ccr
_value_construct_range->_vcr
_move_assignment->_ma
_copy_assignment->_ca
_destroy->_d
_allocator->_al
_calc_offset->_co
_calc_reallocation->_cr
_calls_destructor_directly->_cdd
_calls_copy_constructor_directly->_cccd
_calls_default_constructor_directly->_cdcd
_resize_from_closest_side->_rfcs
*/