map

// -*- C++ -*-
#ifndef _MY_MAP_H
#define _MY_MAP_H 1

#include"alloc.h"

namespace stl_with_memory_pool{

template<class T,class U> concept __rv_as=std::is_constructible_v<U,T&&>;
template<class T> concept __trans=requires{typename T::is_transparent;};

template<class Key, class T, class Compare=std::less<Key>,
	class Allocator=allocator<std::pair<const Key, T>>
> struct map{
	using key_type=Key;
	using mapped_type=T;
	using value_type=std::pair<const Key, T>;
	using size_type=uint32_t;
	using difference_type=int;
	using key_compare=Compare;
	using allocator_type=Allocator;
	using reference=value_type&;
	using const_reference=const value_type&;
	using pointer=typename std::allocator_traits<Allocator>::pointer;
	using const_pointer=typename std::allocator_traits<Allocator>::const_pointer;

	struct iterator;
	struct const_iterator;

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

struct value_compare{
friend struct map;
protected:
	Compare comp;
	value_compare(Compare c):comp(c){}
public:
	bool operator()(const value_type& lhs, const value_type& rhs)const{
		return comp(lhs.first, rhs.first);
	}
};

key_compare key_comp()const{return _Cmp;}
value_compare value_comp()const{return value_compare(_Cmp);}

private:

bool _Lt(const Key& a,const Key& b)const{return _Cmp(a,b);}
bool _Eq(const Key& a,const Key& b)const{return !_Lt(a,b) && !_Lt(b,a);}
template<class X,class Y,__trans=Compare>
bool _Lt(const X& a,const Y& b)const{return a<b;}
template<class X,class Y,__trans=Compare>
bool _Eq(const X& a,const Y& b)const{return !(a<b) && !(b<a);}

template<bool b,class A,class B> struct _If_else{using type=B;};
template<class A,class B> struct _If_else<true,A,B>{using type=A;};
template<class A,class B> struct _Tight_pair{
	A first;
	[[no_unique_address]] B second;
	_Tight_pair(const A& a,const B& b):first(a),second(b){}
	_Tight_pair(A&& a,B&& b):first(std::move(a)),second(std::move(b)){}
};

using _Vl=typename _If_else<std::is_empty_v<T>,_Tight_pair<Key,T>,std::pair<Key,T>>::type;

static constexpr int B=32;
struct _Node{
	short n,fa_id;
	alignas(_Vl) char _dat[2*B*sizeof(_Vl)]; //bypass initialization
	_Node **ch,*fa;

	constexpr _Vl* dat(){return (_Vl*)_dat;}
	constexpr const _Vl* dat()const{return (const _Vl*)_dat;}
	_Node(const _Node& rhs):n(rhs.n),fa_id(rhs.fa_id),ch(rhs.ch),fa(rhs.fa){
		for(short i=0;i<rhs.n;i++)
			std::construct_at(dat()+i,rhs.dat()[i]);
	}
	_Node& operator=(const _Node&)=delete;
};
_Node* _Root;size_type _Sz;Compare _Cmp;

using _Node_alloc=typename std::allocator_traits<Allocator>::template rebind_alloc<_Node>;
using _Ptr_alloc=typename std::allocator_traits<Allocator>::template rebind_alloc<_Node*>;
using _T_alloc=typename std::allocator_traits<Allocator>::template rebind_alloc<T>;

constexpr static bool _Leaf(const _Node& x){return !x.ch;}

iterator _Make_it(_Node*p,short k){return iterator(_Root,p,k);}
const_iterator _Make_cit(const _Node*p,short k)const{return const_iterator(_Root,p,k);}
static iterator _To_it(const const_iterator&o){return iterator(o.rt,(_Node*)o.p,o.k);}

static const _Node* _Find_first(const _Node* p){ //can return nullptr
	while(!_Leaf(*p))p=p->ch[0];
	return p->n?p:nullptr;
}
static const _Node* _Find_last(const _Node* p){ //can return nullptr
	while(!_Leaf(*p))p=p->ch[p->n];
	return p->n?p:nullptr;
}

template<class K> const_iterator _Find(const K& x)const{
	const _Node* p=_Root;
	for(short i;;p=p->ch[i]){
		for(i=0;i<p->n && _Lt(p->dat()[i].first,x);i++);
		if(i<p->n && !_Lt(x,p->dat()[i].first))return _Make_cit(p,i);
		if(_Leaf(*p))return _Make_cit(nullptr,0);
	}
}

_Node* _New_node(short n,short id,_Node* fa){
	_Node* p=_Node_alloc().allocate(1);
	p->n=n;p->fa_id=id;p->fa=fa;p->ch=nullptr;
	return p;
}

template<class K> std::pair<iterator,bool> _Find_or_insert(K&& x){
	_Node* p=_Root;short i;
	for(;;p=p->ch[i]){
		for(i=0;i<p->n && _Lt(p->dat()[i].first,x);i++);
		if(i<p->n && !_Lt(x,p->dat()[i].first))return {_Make_it(p,i),false};
		if(_Leaf(*p))break;
	}

	for(short j=p->n-1;j>=i;j--){
		if(j+1<p->n)p->dat()[j+1]=std::move(p->dat()[j]);
		else std::construct_at(p->dat()+j+1,std::move(p->dat()[j]));
	}
	if(i<p->n)p->dat()[i].first=std::forward<K>(x);
	else std::construct_at(std::addressof(p->dat()[i].first),std::forward<K>(x));
	p->n++;_Sz++;
	iterator ret(_Root,p,i);bool fix=false;

	auto split=[&]{
		_Node* f=p->fa;short id=p->fa_id;
		for(short j=f->n;j>id;j--){
			f->ch[j+1]=f->ch[j],f->ch[j+1]->fa_id++;
			if(j<f->n)f->dat()[j]=std::move(f->dat()[j-1]);
			else std::construct_at(f->dat()+j,std::move(f->dat()[j-1]));
		}
		constexpr short l=B,r=B-1;
		if(id<f->n)f->dat()[id]=std::move(p->dat()[l]);
		else std::construct_at(f->dat()+id,std::move(p->dat()[l]));
		p->dat()[l].~_Vl();f->n++;
		_Node* q=_New_node(r,id+1,f);
		for(short j=l+1;j<2*B;j++)
			std::construct_at(q->dat()+j-l-1,std::move(p->dat()[j])),
			p->dat()[j].~_Vl();
		if(p->ch){
			q->ch=_Ptr_alloc().allocate(2*B+1);
			for(short j=l+1;j<=2*B;j++)
				q->ch[j-l-1]=p->ch[j],q->ch[j-l-1]->fa=q,
				q->ch[j-l-1]->fa_id-=l+1;
		}
		if(!fix){
			if(i==l)ret=_Make_it(f,id),i=id;
			else{
				fix=true;
				if(i>l)ret=_Make_it(q,i-l-1);
			}
		}
		p->n=l;f->ch[id+1]=q;
	};

	for(;p!=_Root && p->n==2*B;p=p->fa)split();
	if(p==_Root && p->n==2*B){
		_Root=_New_node(0,0,nullptr);
		p->fa=_Root;p->fa_id=0;
		_Root->ch=_Ptr_alloc().allocate(2*B+1);
		_Root->ch[0]=p;split();
	}
	return {ret,true};
}

_Vl _Erase(iterator pos){
	_Node* p=pos.p;short i=pos.k;
	_Vl ret=std::move(p->dat()[i]);
	if(!_Leaf(*p)){
		_Node* q=(_Node*)_Find_first(p->ch[i+1]);
		p->dat()[i]=std::move(q->dat()[0]);
		p=q,i=0;
	}
	for(short j=i;j+1<p->n;j++)p->dat()[j]=std::move(p->dat()[j+1]);
	p->dat()[--p->n].~_Vl();
	for(_Node *f=p->fa;p!=_Root && p->n<B-1;p=f,f=p->fa){
		int id=p->fa_id;
		if(id<f->n && f->ch[id+1]->n>=B){
			_Node *q=f->ch[id+1];
			std::construct_at(p->dat()+p->n++,std::move(f->dat()[id]));
			if(!_Leaf(*p))(p->ch[p->n]=q->ch[0])->fa=p,p->ch[p->n]->fa_id=p->n;
			f->dat()[id]=std::move(q->dat()[0]);
			for(short i=0;i+1<q->n;i++)q->dat()[i]=std::move(q->dat()[i+1]);
			q->dat()[--q->n].~_Vl();
			if(!_Leaf(*q))
				for(short i=0;i<=q->n;i++)
					(q->ch[i]=q->ch[i+1])->fa_id--;
			break;
		}
		if(id && f->ch[id-1]->n>=B){
			_Node *q=f->ch[id-1];
			std::construct_at(p->dat()+p->n,std::move(p->dat()[p->n-1]));
			for(short i=p->n-1;i;i--)p->dat()[i]=std::move(p->dat()[i-1]);
			p->dat()[0]=std::move(f->dat()[id-1]);
			if(!_Leaf(*p)){
				for(short i=p->n;~i;i--)(p->ch[i+1]=p->ch[i])->fa_id++;
				(p->ch[0]=q->ch[q->n])->fa=p,p->ch[0]->fa_id=0;
			}
			p->n++;
			f->dat()[id-1]=std::move(q->dat()[q->n-1]);
			q->dat()[--q->n].~_Vl();
			break;
		}
		if(id==f->n)p=f->ch[--id];
		_Node *q=f->ch[id+1];
		std::construct_at(p->dat()+p->n,std::move(f->dat()[id]));
		for(short i=0;i<q->n;i++)
			std::construct_at(p->dat()+p->n+1+i,std::move(q->dat()[i])),
			q->dat()[i].~_Vl();
		if(!_Leaf(*q))
			for(short i=0;i<=q->n;i++)
				(p->ch[i+p->n+1]=q->ch[i])->fa=p,
				p->ch[i+p->n+1]->fa_id=i+p->n+1;
		p->n+=q->n+1;
		for(short i=id;i+1<f->n;i++)
			f->dat()[i]=std::move(f->dat()[i+1]);
		f->dat()[--f->n].~_Vl();
		for(short i=id+1;i<=f->n;i++)(f->ch[i]=f->ch[i+1])->fa_id--;
	}
	if(p==_Root && !p->n && !_Leaf(*p))_Root=p->ch[0];
	_Sz--;return ret;
}

void _Copy_from(_Node* p,const _Node* other){
	if(_Leaf(*other))return;
	p->ch=_Ptr_alloc().allocate(2*B+1);
	for(short i=0;i<=p->n;i++){
		p->ch[i]=_Node_alloc().allocate(1);
		std::construct_at(p->ch[i],*other->ch[i]);
		p->ch[i]->fa=p;
		_Copy_from(p->ch[i],other->ch[i]);
	}
}

void _Del_node(_Node* p){
	for(short i=0;i<p->n;i++)
		p->dat()[i].~_Vl();
	if(!_Leaf(*p))
		for(short i=0;i<=p->n;i++)
			_Del_node(p->ch[i]);
}

template<class K> const_iterator _L_bound(const K& key)const{
	const _Node *p=_Root;auto now=_Make_cit(nullptr,0);
	for(short i;;p=p->ch[i]){
		for(i=0;i<p->n && _Lt(p->dat()[i].first,key);i++);
		if(i<p->n)now=_Make_cit(p,i);
		if(_Leaf(*p))return now;
	}
}
template<class K> const_iterator _U_bound(const K& key)const{
	const _Node *p=_Root;auto now=_Make_cit(nullptr,0);
	for(short i;;p=p->ch[i]){
		for(i=0;i<p->n && !_Lt(key,p->dat()[i].first);i++);
		if(i<p->n)now=_Make_cit(p,i);
		if(_Leaf(*p))return now;
	}
}
template<class K>
std::pair<const_iterator,const_iterator> _Eq_range(const K& key)const{
	const _Node *p=_Root;auto now=_Make_cit(nullptr,0);
	for(short i;;p=p->ch[i]){
		for(i=0;i<p->n && _Lt(p->dat()[i].first,key);i++);
		if(i<p->n){
			now=_Make_cit(p,i);
			if(!_Lt(key,p->dat()[i].first)){
				auto b=now++;return {b,now};
			}
		}
		if(_Leaf(*p))return {now,now};
	}
}

public:
struct iterator{
friend struct const_iterator;
friend struct map;
using difference_type=map::difference_type;
using value_type=map::value_type;
private:
	const _Node*rt; _Node*p; short k;
public:
	iterator(const _Node*rt=nullptr,_Node*p=nullptr,short k=0):rt(rt),p(p),k(k){}
	bool operator==(const auto&rhs)const{
		if(p==rhs.p && p==nullptr)return true;
		return p==rhs.p && k==rhs.k;
	}
	value_type& operator*()const{return *(value_type*)(p->dat()+k);}
	value_type* operator->()const{return (value_type*)(p->dat()+k);}
	iterator& operator++(){
		if(!_Leaf(*p))p=(_Node*)_Find_first(p->ch[k+1]),k=0;
		else{
			if(k+1<p->n)++k;else{
				while(p!=rt && p->fa_id==p->fa->n)p=p->fa;
				if(p==rt)p=nullptr,k=0;
				else k=p->fa_id,p=p->fa;
			}
		}
		return *this;
	}
	iterator operator++(int){
		auto res=*this;++*this;
		return res;
	}
	iterator& operator--(){
		if(p==nullptr)p=(_Node*)_Find_last(rt),k=p->n-1;
		else if(!_Leaf(*p))p=(_Node*)_Find_last(p->ch[k]),k=p->n-1;
		else if(k)--k;
		else{
			while(p!=rt && !p->fa_id)p=p->fa;
			if(p==rt)p=nullptr,k=0;
			else k=p->fa_id-1,p=p->fa;
		}
		return *this;
	}
	iterator operator--(int){
		auto res=*this;--*this;
		return res;
	}
};

struct const_iterator{
friend struct iterator;
friend struct map;
using difference_type=map::difference_type;
using value_type=const map::value_type;
private:
	const _Node*rt,*p; short k;
public:
	const_iterator(const _Node*rt=nullptr,const _Node*p=nullptr,short k=0)
		:rt(rt),p(p),k(k){}
	const_iterator(const iterator&rhs):rt(rhs.rt),p(rhs.p),k(rhs.k){}
	bool operator==(const auto&rhs)const{
		if(p==rhs.p && p==nullptr)return true;
		return p==rhs.p && k==rhs.k;
	}
	value_type& operator*()const{return *(value_type*)(p->dat()+k);}
	value_type* operator->()const{return (value_type*)(p->dat()+k);}
	const_iterator& operator++(){
		if(!_Leaf(*p))p=_Find_first(p->ch[k+1]),k=0;
		else{
			if(k+1<p->n)++k;else{
				while(p!=rt && p->fa_id==p->fa->n)p=p->fa;
				if(p==rt)p=nullptr,k=0;
				else k=p->fa_id,p=p->fa;
			}
		}
		return *this;
	}
	const_iterator operator++(int){
		auto res=*this;++*this;
		return res;
	}
	const_iterator& operator--(){
		if(p==nullptr)p=_Find_last(rt),k=p->n-1;
		else if(!_Leaf(*p))p=_Find_last(p->ch[k]),k=p->n-1;
		else if(k)--k;
		else{
			while(p!=rt && !p->fa_id)p=p->fa;
			if(p==rt)p=nullptr,k=0;
			else k=p->fa_id-1,p=p->fa;
		}
		return *this;
	}
	const_iterator operator--(int){
		auto res=*this;--*this;
		return res;
	}
};

size_type size()const{return _Sz;}
size_type max_size()const{return 1e9;}
[[nodiscard]] bool empty()const{return !_Sz;}

allocator_type get_allocator()const{return Allocator{};}

iterator begin(){return _Make_it((_Node*)_Find_first(_Root),0);}
const_iterator begin()const{return _Make_cit(_Find_first(_Root),0);}
const_iterator cbegin()const{return _Make_cit(_Find_first(_Root),0);}
iterator end(){return _Make_it(nullptr,0);}
const_iterator end()const{return _Make_cit(nullptr,0);}
const_iterator cend()const{return _Make_cit(nullptr,0);}
reverse_iterator rbegin(){return reverse_iterator{end()};}
const_reverse_iterator rbegin()const{return const_reverse_iterator{end()};}
const_reverse_iterator crbegin()const{return const_reverse_iterator{end()};}
reverse_iterator rend(){return reverse_iterator{begin()};}
const_reverse_iterator rend()const{return const_reverse_iterator{begin()};}
const_reverse_iterator crend()const{return const_reverse_iterator{begin()};}

map():_Sz(0),_Cmp(Compare()){
	_Root=_New_node(0,0,nullptr);
}
explicit map(const Compare& comp, const Allocator& =Allocator()):_Sz(0),_Cmp(comp){
	_Root=_New_node(0,0,nullptr);
}
explicit map(const Allocator&):map(){}
template<std::input_iterator InputIt>
map(InputIt first,InputIt last,const Compare& comp=Compare(),const Allocator& =Allocator()):map(comp){
	while(first!=last)insert(*first++);
}
template<std::input_iterator InputIt>
map(InputIt first,InputIt last,const Allocator&):map(){
	while(first!=last)insert(*first++);
}
map(const map& other):_Sz(other._Sz),_Cmp(other._Cmp){
	_Root=_Node_alloc().allocate(1);
	std::construct_at(_Root,*other._Root);
	_Copy_from(_Root,other._Root);
}
map(const map& other,const Allocator&):map(other){}
map(map&& other)noexcept:_Root(other._Root),_Sz(other._Sz),_Cmp(other._Cmp){
	other._Sz=0;other._Root=_New_node(0,0,nullptr);
}
map(map&& other,const Allocator&)noexcept:map(std::move(other)){}
map(std::initializer_list<value_type> init,
	const Compare& comp=Compare(),
	const Allocator& =Allocator()):map(init.begin(),init.end(),comp){}
map(std::initializer_list<value_type> init,
	const Allocator& alloc):map(init.begin(),init.end(),alloc){}

~map(){if(_Root)_Del_node(_Root);}

map& operator=(const map& other){
	this->~map();
	std::construct_at(this,other);
	return *this;
}
map& operator=(map&& other)noexcept{
	this->~map();
	std::construct_at(this,std::move(other));
	return *this;
}
map& operator=(std::initializer_list<value_type> ilist){
	this->~map();
	std::construct_at(this,ilist);
	return *this;
}

void swap(map& other)noexcept{
	std::swap(_Sz,other._Sz);
	std::swap(_Root,other._Root);
	std::swap(_Cmp,other._Cmp);
}

iterator find(const Key& key){return _To_it(_Find(key));}
const_iterator find(const Key& key)const{return _Find(key);}
template<class K, __trans=Compare>
	iterator find(const K& x){return _To_it(_Find(x));}
template<class K, __trans=Compare>
	const_iterator find(const K& x)const{return _Find(x);}

T& at(const Key& key){
	iterator k=find(key);
	if(k.p)return k->second;
	throw std::out_of_range("Debug your code and then use operator[] instead");
}
const T& at(const Key& key)const{
	const_iterator k=find(key);
	if(k.p)return k->second;
	throw std::out_of_range("Debug your code and then use operator[] instead");
}

std::pair<iterator,bool> insert(const value_type& value){
	auto ret=_Find_or_insert(value.first);
	if(!std::is_empty_v<T> && ret.second)
		std::construct_at(std::addressof(ret.first->second),value.second);
	return ret;
}
std::pair<iterator,bool> insert(value_type&& value){
	auto ret=_Find_or_insert(std::move(value.first));
	if(!std::is_empty_v<T> && ret.second)
		std::construct_at(std::addressof(ret.first->second),std::move(value.second));
	return ret;
}
template<__rv_as<value_type> P>
std::pair<iterator,bool> insert(P&& value){
	auto ret=_Find_or_insert(std::move(value.first));
	if(!std::is_empty_v<T> && ret.second)
		std::construct_at(std::addressof(ret.first->second),std::move(value.second));
	return ret;
}
template<std::input_iterator InputIt>
void insert(InputIt first,InputIt last){
	while(first!=last)insert(*first++);
}
void insert(std::initializer_list<value_type> ilist){
	insert(ilist.begin(),ilist.end());
}

template<class M>
std::pair<iterator,bool> insert_or_assign(const key_type& k,M&& obj){
	auto ret=_Find_or_insert(k);
	if constexpr(!std::is_empty_v<T>){
		if(!ret.second)ret.first->second=std::move(obj);
		else std::construct_at(std::addressof(ret.first->second),std::move(obj));
	}
	return ret;
}
template<class M>
std::pair<iterator,bool> insert_or_assign(key_type&& k,M&& obj){
	auto ret=_Find_or_insert(std::move(k));
	if constexpr(!std::is_empty_v<T>){
		if(!ret.second)ret.first->second=std::move(obj);
		else std::construct_at(std::addressof(ret.first->second),std::move(obj));
	}
	return ret;
}

template<class... Args>
std::pair<iterator,bool> emplace(Args&&... args){
	_Vl value(std::forward<Args>(args)...);
	auto ret=_Find_or_insert(std::move(value.first));
	if(!std::is_empty_v<T> && ret.second)
		std::construct_at(std::addressof(ret.first->second),std::move(value.second));
	return ret;
}

template<class... Args>
std::pair<iterator,bool> try_emplace(const Key& k,Args&&... args){
	auto ret=_Find_or_insert(k);
	if(!std::is_empty_v<T> && ret.second)
		std::construct_at(std::addressof(ret.first->second),std::forward<Args>(args)...);
	return ret;
}
template<class... Args>
std::pair<iterator,bool> try_emplace(Key&& k,Args&&... args){
	auto ret=_Find_or_insert(std::move(k));
	if(!std::is_empty_v<T> && ret.second)
		std::construct_at(std::addressof(ret.first->second),std::forward<Args>(args)...);
	return ret;
}

T& operator[](const Key& key){
	auto r=_Find_or_insert(key);
	if(!std::is_empty_v<T> && r.second){
		auto a=_T_alloc();
		std::allocator_traits<_T_alloc>::construct(a,std::addressof(r.first->second));
	}
	return r.first->second;
}
T& operator[](Key&& key){
	auto r=_Find_or_insert(std::move(key));
	if(!std::is_empty_v<T> && r.second){
		auto a=_T_alloc();
		std::allocator_traits<_T_alloc>::construct(a,std::addressof(r.first->second));
	}
	return r.first->second;
}

_Vl erase(const_iterator pos){return _Erase(_To_it(pos));}
_Vl erase(iterator pos){return _Erase(pos);}
std::optional<_Vl> erase(const Key& key){
	auto it=_To_it(_Find(key));
	if(it==end())return std::nullopt;
	return _Erase(it);
}
template<class K,__trans=Compare> requires(!std::convertible_to<K,iterator> &&
	!std::convertible_to<K,const_iterator>)
std::optional<_Vl> erase(K&& x){
	auto it=_To_it(_Find(x));
	if(it==end())return std::nullopt;
	return _Erase(it);
}

iterator erase_and_get_next(iterator pos){
	return lower_bound(_Erase(pos).first);
}
iterator erase_and_get_next(const_iterator pos){
	return lower_bound(_Erase(_To_it(pos)).first);
}
iterator erase(const_iterator first,const_iterator last){
	auto it=first;
	if(last==cend())
		while(it!=last)it=erase_and_get_next(it);
	else{
		Key ed=last->first;
		while(_Lt(*it,ed))it=erase_and_get_next(it);
	}
	return _To_it(it);
}

void clear(){
	this->~map();
	_Sz=0;_Root=_New_node(0,0,nullptr);
}

iterator lower_bound(const Key& key){return _To_it(_L_bound(key));}
const_iterator lower_bound(const Key& key)const{return _L_bound(key);}
template<class K,__trans=Compare>
iterator lower_bound(const K& key){return _To_it(_L_bound(key));}
template<class K,__trans=Compare>
const_iterator lower_bound(const K& key)const{return _L_bound(key);}

iterator upper_bound(const Key& key){return _To_it(_U_bound(key));}
const_iterator upper_bound(const Key& key)const{return _U_bound(key);}
template<class K,__trans=Compare>
iterator upper_bound(const K& key){return _To_it(_U_bound(key));}
template<class K,__trans=Compare>
const_iterator upper_bound(const K& key)const{return _U_bound(key);}

std::pair<iterator,iterator> equal_range(const Key& key){
	auto r=_Eq_range(key);
	return {_To_it(r.first),_To_it(r.second)};
}
std::pair<const_iterator,const_iterator> equal_range(const Key& key)const{
	return _Eq_range(key);
}
template<class K,__trans=Compare>
std::pair<iterator,iterator> equal_range(const K& key){
	auto r=_Eq_range(key);
	return {_To_it(r.first),_To_it(r.second)};
}
template<class K,__trans=Compare>
std::pair<const_iterator,const_iterator> equal_range(const K& key)const{
	return _Eq_range(key);
}

bool contains(const Key& key)const{return _Find(key)!=cend();}
template<class K,__trans=Compare>
bool contains(const K& x)const{return _Find(x)!=cend();}

size_type count(const Key& key)const{return _Find(key)!=cend();}
template<class K,__trans=Compare>
bool count(const K& x)const{return _Find(x)!=cend();}
};

template<class Key,class T,class Compare,class Alloc>
bool operator==(const map<Key,T,Compare,Alloc>& lhs,
	const map<Key,T,Compare,Alloc>& rhs){
	if(lhs.size()!=rhs.size())return 0;
	for(auto it=lhs.cbegin(),it1=rhs.cbegin();
		it!=lhs.cend();++it,++it1){
		if(*it!=*it1)return 0;
	}
	return 1;
}

template<class Key,class T,class Compare,class Alloc>
auto operator<=>(const map<Key,T,Compare,Alloc>& lhs,
	const map<Key,T,Compare,Alloc>& rhs){
	for(auto it=lhs.cbegin(),it1=rhs.cbegin();
		it!=lhs.cend() && it1!=rhs.cend();
		++it,++it1)
		if(auto k=*it<=>*it1;k!=std::weak_ordering::equivalent)return k;
	return lhs.size()<=>rhs.size();
}
}

#define Map stl_with_memory_pool::map
namespace std{
	template<class Key,class T,class Compare,class Alloc>
	void swap(Map<Key,T,Compare,Alloc>& lhs,
		Map<Key,T,Compare,Alloc>& rhs){
		lhs.swap(rhs);
	}

	template<class Key,class T,class Compare,class Alloc,class Pred>
	auto erase_if(Map<Key,T,Compare,Alloc>& c,Pred pred){
		auto old_size = c.size();
		for (auto i = c.begin(), last = c.end(); i != last; ) {
			if (pred(*i)) {
				i = c.erase_and_get_next(i);
			} else {
				++i;
			}
		}
		return old_size - c.size();
	}
}
#undef Map

#endif