论写unordered_map的难度

我发现C++标准库的哈希最坏时是O(n)，所以我就抄袭了一下Java的红黑树保底O(log n)
结果我写了好几天，DeepSeek给的评价依然是玩具级，太阴了。
下面展示一下我的代码：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using lf=double;
template<class Key,class T,class Hash=std::hash<Key>,class KeyEqual=std::equal_to<Key>>
struct unordered_map{
    struct TreeNode{
        const Key key;
        T val;
        TreeNode *next,*left,*right,*parent;
        bool red;
        TreeNode(const Key&key=Key(),const T&val=T()):key(key),val(val),next(0),left(0),right(0),parent(0),red(1){}
    };
    struct Bucket{
        TreeNode* head;
        bool isTree;
        Bucket():head(0),isTree(0){}
    };
    using key_type=Key;
    using mapped_type=T;
    using value_type=pair<const Key,T>;
    using size_type=size_t;
    using hasher=Hash;
    using key_equal=KeyEqual;
    static const int TREEIFY_THRESHOLD=8,UNTREEIFY_THRESHOLD=6,INIT_CAP=16;
    static constexpr lf LOAD_FACTOR=0.75;
    vector<Bucket>b;
    size_type sz,cap;
    Hash hf;
    KeyEqual eq;
    struct const_iterator;
    struct iterator{
        unordered_map* map;
        size_type idx;
        TreeNode* p;
        iterator(unordered_map*map=0,size_type idx=0,TreeNode*p=0):map(map),idx(idx),p(p){}
        TreeNode&operator*()const{return*p;}
        TreeNode*operator->()const{return p;}
        bool operator==(const iterator&o)const{return p==o.p;}
        bool operator!=(const iterator&o)const{return p!=o.p;}
        bool operator==(const const_iterator&o)const{return p==o.p;}
        bool operator!=(const const_iterator&o)const{return p!=o.p;}
        iterator&operator++(){
            if(!p)return*this;
            if(map->b[idx].isTree){
                if(p->right){
                    p=p->right;
                    while(p->left)p=p->left;
                }else{
                    TreeNode*q=p->parent;
                    while(q&&p==q->right){p=q;q=q->parent;}
                    p=q;
                }
                if(p)return*this;
            }else{
                p=p->next;
                if(p)return*this;
            }
            for(size_type i=idx+1;i<map->cap;i++){
                if(map->b[i].head){
                    idx=i;
                    p=map->b[i].head;
                    if(map->b[i].isTree)while(p->left)p=p->left;
                    return*this;
                }
            }
            idx=map->cap;
            p=0;
            return*this;
        }
        iterator operator++(int){iterator t=*this;++*this;return t;}
        iterator&operator--(){
            if(p==0){
                for(size_type i=map->cap;i-->0;){
                    if(map->b[i].head){
                        idx=i;
                        p=map->b[i].head;
                        if(map->b[i].isTree)while(p->right)p=p->right;
                        return*this;
                    }
                }
                return*this;
            }
            if(map->b[idx].isTree){
                if(p->left){
                    p=p->left;
                    while(p->right)p=p->right;
                }else{
                    TreeNode*q=p->parent;
                    while(q&&p==q->left){p=q;q=q->parent;}
                    p=q;
                }
                if(p)return*this;
            }else{
                TreeNode*head=map->b[idx].head;
                if(p!=head){
                    TreeNode*q=head;
                    while(q->next!=p)q=q->next;
                    p=q;
                    return*this;
                }
            }
            for(size_type i=idx;i-->0;){
                if(map->b[i].head){
                    idx=i;
                    p=map->b[i].head;
                    if(map->b[i].isTree)while(p->right)p=p->right;
                    return*this;
                }
            }
            idx=0;
            p=0;
            return*this;
        }
        iterator operator--(int){iterator t=*this;--*this;return t;}
    };
    struct const_iterator{
        const unordered_map* map;
        size_type idx;
        TreeNode* p;
        const_iterator(const unordered_map*map=0,size_type idx=0,TreeNode*p=0):map(map),idx(idx),p(p){}
        const_iterator(const iterator&o):map(o.map),idx(o.idx),p(o.p){}
        const TreeNode&operator*()const{return*p;}
        const TreeNode*operator->()const{return p;}
        bool operator==(const const_iterator&o)const{return p==o.p;}
        bool operator!=(const const_iterator&o)const{return p!=o.p;}
        const_iterator&operator++(){
            if(!p)return*this;
            if(map->b[idx].isTree){
                if(p->right){
                    p=p->right;
                    while(p->left)p=p->left;
                }else{
                    TreeNode*q=p->parent;
                    while(q&&p==q->right){p=q;q=q->parent;}
                    p=q;
                }
                if(p)return*this;
            }else{
                p=p->next;
                if(p)return*this;
            }
            for(size_type i=idx+1;i<map->cap;i++){
                if(map->b[i].head){
                    idx=i;
                    p=map->b[i].head;
                    if(map->b[i].isTree)while(p->left)p=p->left;
                    return*this;
                }
            }
            idx=map->cap;
            p=0;
            return*this;
        }
        const_iterator operator++(int){const_iterator t=*this;++*this;return t;}
        const_iterator&operator--(){
            if(p==0){
                for(size_type i=map->cap;i-->0;){
                    if(map->b[i].head){
                        idx=i;
                        p=map->b[i].head;
                        if(map->b[i].isTree)while(p->right)p=p->right;
                        return*this;
                    }
                }
                return*this;
            }
            if(map->b[idx].isTree){
                if(p->left){
                    p=p->left;
                    while(p->right)p=p->right;
                }else{
                    TreeNode*q=p->parent;
                    while(q&&p==q->left){p=q;q=q->parent;}
                    p=q;
                }
                if(p)return*this;
            }else{
                TreeNode*head=map->b[idx].head;
                if(p!=head){
                    TreeNode*q=head;
                    while(q->next!=p)q=q->next;
                    p=q;
                    return*this;
                }
            }
            for(size_type i=idx;i-->0;){
                if(map->b[i].head){
                    idx=i;
                    p=map->b[i].head;
                    if(map->b[i].isTree)while(p->right)p=p->right;
                    return*this;
                }
            }
            idx=0;
            p=0;
            return*this;
        }
        const_iterator operator--(int){const_iterator t=*this;--*this;return t;}
    };
    unordered_map():sz(0),cap(INIT_CAP){b.assign(cap,Bucket());}
    explicit unordered_map(size_type n):sz(0),cap(INIT_CAP){
        size_type need=(size_type)(n/LOAD_FACTOR)+1;
        while(cap<need)cap<<=1;
        b.assign(cap,Bucket());
    }
    unordered_map(size_type n,const Hash&h,const KeyEqual&e):sz(0),cap(INIT_CAP),hf(h),eq(e){
        size_type need=(size_type)(n/LOAD_FACTOR)+1;
        while(cap<need)cap<<=1;
        b.assign(cap,Bucket());
    }
    template<class InputIt>
    unordered_map(InputIt first,InputIt last):sz(0),cap(INIT_CAP){
        b.assign(cap,Bucket());
        for(auto it=first;it!=last;++it)insert(*it);
    }
    unordered_map(initializer_list<value_type>il):sz(0),cap(INIT_CAP){
        b.assign(cap,Bucket());
        for(auto&v:il)insert(v);
    }
    size_type hash(const Key&key)const{return hashWith(hf,key,cap);}
    static size_type hashWith(const Hash&hf,const Key&key,size_type cap){return(size_type)hf(key)&(cap-1);}
    bool keq(const Key&a,const Key&b)const{return eq(a,b);}
    void rotateLeft(TreeNode*&root,TreeNode*x){
        TreeNode*y=x->right;
        x->right=y->left;
        if(y->left)y->left->parent=x;
        y->parent=x->parent;
        if(!x->parent)root=y;
        else if(x==x->parent->left)x->parent->left=y;
        else x->parent->right=y;
        y->left=x;
        x->parent=y;
    }
    void rotateRight(TreeNode*&root,TreeNode*x){
        TreeNode*y=x->left;
        x->left=y->right;
        if(y->right)y->right->parent=x;
        y->parent=x->parent;
        if(!x->parent)root=y;
        else if(x==x->parent->right)x->parent->right=y;
        else x->parent->left=y;
        y->right=x;
        x->parent=y;
    }
    void insertFix(TreeNode*&root,TreeNode*z){
        while(z->parent&&z->parent->red){
            TreeNode*g=z->parent->parent;
            if(z->parent==g->left){
                TreeNode*u=g->right;
                if(u&&u->red){z->parent->red=u->red=0;g->red=1;z=g;}
                else{
                    if(z==z->parent->right){z=z->parent;rotateLeft(root,z);}
                    z->parent->red=0;
                    g->red=1;
                    rotateRight(root,g);
                }
            }else{
                TreeNode*u=g->left;
                if(u&&u->red){z->parent->red=u->red=0;g->red=1;z=g;}
                else{
                    if(z==z->parent->left){z=z->parent;rotateRight(root,z);}
                    z->parent->red=0;
                    g->red=1;
                    rotateLeft(root,g);
                }
            }
        }
        root->red=0;
    }
    void insertTree(TreeNode*&root,TreeNode*z){
        TreeNode*y=0,*x=root;
        while(x){y=x;x=z->key<x->key?x->left:x->right;}
        z->parent=y;
        if(!y)root=z;
        else if(z->key<y->key)y->left=z;
        else y->right=z;
        z->left=z->right=0;
        z->red=1;
        insertFix(root,z);
    }
    TreeNode*findTree(TreeNode*root,const Key&key)const{
        while(root){
            if(keq(key,root->key))return root;
            root=key<root->key?root->left:root->right;
        }
        return 0;
    }
    void transplant(TreeNode*&root,TreeNode*u,TreeNode*v){
        if(!u->parent)root=v;
        else if(u==u->parent->left)u->parent->left=v;
        else u->parent->right=v;
        if(v)v->parent=u->parent;
    }
    TreeNode*minimum(TreeNode*x)const{while(x->left)x=x->left;return x;}
    TreeNode*successor(TreeNode*x)const{
        if(x->right)return minimum(x->right);
        TreeNode*q=x->parent;
        while(q&&x==q->right){x=q;q=q->parent;}
        return q;
    }
    void deleteFix(TreeNode*&root,TreeNode*x,TreeNode*xp,bool wasLeft){
        while(x!=root&&(!x||!x->red)){
            TreeNode*parent=x?x->parent:xp;
            bool left=x?x==parent->left:wasLeft;
            if(left){
                TreeNode*w=parent->right;
                if(!w){x=parent;xp=x->parent;wasLeft=xp&&x==xp->left;continue;}
                if(w->red){w->red=0;parent->red=1;rotateLeft(root,parent);w=parent->right;}
                if((!w->left||!w->left->red)&&(!w->right||!w->right->red)){
                    w->red=1;
                    x=parent;
                    xp=x->parent;
                    wasLeft=xp&&x==xp->left;
                }else{
                    if(!w->right||!w->right->red){if(w->left)w->left->red=0;w->red=1;rotateRight(root,w);w=parent->right;}
                    w->red=parent->red;
                    parent->red=0;
                    if(w->right)w->right->red=0;
                    rotateLeft(root,parent);
                    x=root;
                    xp=0;
                }
            }else{
                TreeNode*w=parent->left;
                if(!w){x=parent;xp=x->parent;wasLeft=xp&&x==xp->left;continue;}
                if(w->red){w->red=0;parent->red=1;rotateRight(root,parent);w=parent->left;}
                if((!w->right||!w->right->red)&&(!w->left||!w->left->red)){
                    w->red=1;
                    x=parent;
                    xp=x->parent;
                    wasLeft=xp&&x==xp->left;
                }else{
                    if(!w->left||!w->left->red){if(w->right)w->right->red=0;w->red=1;rotateLeft(root,w);w=parent->left;}
                    w->red=parent->red;
                    parent->red=0;
                    if(w->left)w->left->red=0;
                    rotateRight(root,parent);
                    x=root;
                    xp=0;
                }
            }
        }
        if(x)x->red=0;
    }
    bool deleteTree(TreeNode*&root,const Key&key){
        TreeNode*z=findTree(root,key);
        if(!z)return 0;
        TreeNode*y=z,*x=0,*xp=0;
        bool wasLeft=0,yr=y->red;
        if(!z->left){x=z->right;xp=z->parent;wasLeft=xp&&z==xp->left;transplant(root,z,z->right);}
        else if(!z->right){x=z->left;xp=z->parent;wasLeft=xp&&z==xp->left;transplant(root,z,z->left);}
        else{
            y=minimum(z->right);
            yr=y->red;
            x=y->right;
            if(y->parent==z){xp=y;wasLeft=0;if(x)x->parent=y;}
            else{
                xp=y->parent;
                wasLeft=y==xp->left;
                transplant(root,y,y->right);
                y->right=z->right;
                y->right->parent=y;
            }
            transplant(root,z,y);
            y->left=z->left;
            y->left->parent=y;
            y->red=z->red;
        }
        delete z;
        if(!yr)deleteFix(root,x,xp,wasLeft);
        return 1;
    }
    void freeTree(TreeNode*h){
        if(!h)return;
        freeTree(h->left);
        freeTree(h->right);
        delete h;
    }
    int countTree(TreeNode*h)const{
        if(!h)return 0;
        return 1+countTree(h->left)+countTree(h->right);
    }
    TreeNode*untreeify(TreeNode*h){
        vector<pair<Key,T>>kv;
        function<void(TreeNode*)>d=[&](TreeNode*p){
            if(!p)return;
            d(p->left);
            kv.push_back({p->key,p->val});
            d(p->right);
        };
        d(h);
        freeTree(h);
        TreeNode*head=0;
        for(auto it=kv.rbegin();it!=kv.rend();++it){
            TreeNode*n=new TreeNode(it->first,it->second);
            n->next=head;
            head=n;
        }
        return head;
    }
    TreeNode*treeify(TreeNode*h){
        vector<pair<Key,T>>kv;
        for(TreeNode*p=h;p;p=p->next)kv.push_back({p->key,p->val});
        while(h){TreeNode*n=h->next;delete h;h=n;}
        TreeNode*root=0;
        for(auto&x:kv)insertTree(root,new TreeNode(x.first,x.second));
        return root;
    }
    bool insertInto(vector<Bucket>&nb,size_type ncp,const Key&key,const T&val){
        size_type i=hashWith(hf,key,ncp);
        Bucket&bk=nb[i];
        if(!bk.head){
            bk.head=new TreeNode(key,val);
            bk.isTree=0;
            return 1;
        }
        if(bk.isTree){
            TreeNode*e=findTree(bk.head,key);
            if(e){e->val=val;return 0;}
            insertTree(bk.head,new TreeNode(key,val));
            return 1;
        }
        for(TreeNode*p=bk.head;p;p=p->next)if(keq(p->key,key)){p->val=val;return 0;}
        TreeNode*n=new TreeNode(key,val);
        n->next=bk.head;
        bk.head=n;
        int len=0;
        for(TreeNode*p=bk.head;p;p=p->next)++len;
        if(len>=TREEIFY_THRESHOLD){bk.head=treeify(bk.head);bk.isTree=1;}
        return 1;
    }
    void doRehash(size_type ncp){
        vector<pair<Key,T>>all;
        for(auto&bk:b){
            if(!bk.head)continue;
            if(bk.isTree){
                function<void(TreeNode*)>d=[&](TreeNode*p){
                    if(!p)return;
                    d(p->left);
                    all.push_back({p->key,p->val});
                    d(p->right);
                };
                d(bk.head);
            }else{
                for(TreeNode*p=bk.head;p;p=p->next)all.push_back({p->key,p->val});
            }
        }
        vector<Bucket>nb(ncp,Bucket());
        size_type newSz=0;
        try{
            for(auto&x:all)if(insertInto(nb,ncp,x.first,x.second))++newSz;
        }catch(...){
            for(auto&bk:nb){
                if(!bk.head)continue;
                if(bk.isTree)freeTree(bk.head);
                else while(bk.head){TreeNode*n=bk.head->next;delete bk.head;bk.head=n;}
            }
            throw;
        }
        for(auto&bk:b){
            if(!bk.head)continue;
            if(bk.isTree)freeTree(bk.head);
            else while(bk.head){TreeNode*n=bk.head->next;delete bk.head;bk.head=n;}
        }
        b.swap(nb);
        cap=ncp;
        sz=newSz;
    }
    TreeNode*findNode(size_type i,const Key&key)const{
        const Bucket&bk=b[i];
        if(!bk.head)return 0;
        if(bk.isTree)return findTree(bk.head,key);
        for(TreeNode*p=bk.head;p;p=p->next)if(keq(p->key,key))return p;
        return 0;
    }
    pair<iterator,bool> insertNoRehash(const Key&key,const T&val){
        size_type i=hash(key);
        bool ins=insertInto(b,cap,key,val);
        if(ins)++sz;
        return{iterator(this,i,findNode(i,key)),ins};
    }
    pair<iterator,bool> insert(const value_type&v){
        const Key&key=v.first;
        const T&val=v.second;
        auto r=insertNoRehash(key,val);
        if(r.second&&sz>cap*LOAD_FACTOR){
            doRehash(cap<<1);
            size_type i=hash(key);
            return{iterator(this,i,findNode(i,key)),1};
        }
        return r;
    }
    iterator insert(const_iterator,const value_type&v){return insert(v).first;}
    template<class InputIt>
    void insert(InputIt first,InputIt last){for(auto it=first;it!=last;++it)insert(*it);}
    void insert(initializer_list<value_type>il){for(auto&v:il)insert(v);}
    iterator find(const Key&key){
        size_type i=hash(key);
        TreeNode*p=findNode(i,key);
        if(!p)return end();
        return iterator(this,i,p);
    }
    const_iterator find(const Key&key)const{
        size_type i=hash(key);
        TreeNode*p=findNode(i,key);
        if(!p)return end();
        return const_iterator(this,i,p);
    }
    size_type count(const Key&key)const{return find(key)==end()?0:1;}
    size_type erase(const Key&key){
        size_type i=hash(key);
        Bucket&bk=b[i];
        if(!bk.head)return 0;
        if(bk.isTree){
            if(deleteTree(bk.head,key)){
                --sz;
                if(countTree(bk.head)<=UNTREEIFY_THRESHOLD){
                    bk.head=untreeify(bk.head);
                    bk.isTree=0;
                }
                return 1;
            }
            return 0;
        }
        TreeNode*pv=0;
        for(TreeNode*p=bk.head;p;pv=p,p=p->next){
            if(keq(p->key,key)){
                if(pv)pv->next=p->next;
                else bk.head=p->next;
                delete p;
                --sz;
                return 1;
            }
        }
        return 0;
    }
    iterator erase(const_iterator it){
        if(it==end())return end();
        size_type i=it.idx;
        TreeNode*p=it.p;
        TreeNode*succ=0;
        if(b[i].isTree){
            succ=successor(p);
            if(!succ){
                for(size_type j=i+1;j<cap;j++){
                    if(b[j].head){
                        TreeNode*q=b[j].head;
                        if(b[j].isTree)while(q->left)q=q->left;
                        succ=q;
                        break;
                    }
                }
            }
        }else{
            if(p->next)succ=p->next;
            else{
                for(size_type j=i+1;j<cap;j++){
                    if(b[j].head){
                        TreeNode*q=b[j].head;
                        if(b[j].isTree)while(q->left)q=q->left;
                        succ=q;
                        break;
                    }
                }
            }
        }
        Key nk=succ?succ->key:Key();
        bool hasNext=(succ!=0);
        if(b[i].isTree){
            if(!deleteTree(b[i].head,it->key))return end();
            --sz;
            if(countTree(b[i].head)<=UNTREEIFY_THRESHOLD){
                b[i].head=untreeify(b[i].head);
                b[i].isTree=0;
            }
        }else{
            TreeNode*pv=0;
            for(TreeNode*q=b[i].head;q;pv=q,q=q->next){
                if(q==it.p){
                    if(pv)pv->next=q->next;
                    else b[i].head=q->next;
                    delete q;
                    --sz;
                    break;
                }
            }
        }
        if(hasNext)return find(nk);
        return end();
    }
    iterator erase(const_iterator first,const_iterator last){
        iterator r=end();
        while(first!=last){
            auto nx=first;
            ++nx;
            r=erase(first);
            first=nx;
        }
        return r;
    }
    T& operator[](const Key&key){
        auto r=insert({key,T()});
        return r.first->val;
    }
    T& at(const Key&key){
        auto it=find(key);
        if(it==end())throw out_of_range("unordered_map::at");
        return it->val;
    }
    const T& at(const Key&key)const{
        auto it=find(key);
        if(it==end())throw out_of_range("unordered_map::at");
        return it->val;
    }
    void clear(){
        for(auto&bk:b){
            if(!bk.head)continue;
            if(bk.isTree)freeTree(bk.head);
            else while(bk.head){TreeNode*n=bk.head->next;delete bk.head;bk.head=n;}
            bk.head=0;
            bk.isTree=0;
        }
        sz=0;
    }
    size_type size()const{return sz;}
    bool empty()const{return sz==0;}
    size_type bucket_count()const{return cap;}
    lf load_factor()const{return(lf)sz/cap;}
    lf max_load_factor()const{return LOAD_FACTOR;}
    void reserve(size_type n){
        size_type need=(size_type)(n/LOAD_FACTOR)+1;
        if(need>cap){
            size_type p=1;
            while(p<need){if(p==0)break;p<<=1;}
            if(p>0)doRehash(p);
        }
    }
    void rehash(size_type n){
        size_type need=n<INIT_CAP?INIT_CAP:n;
        size_type p=1;
        while(p<need){if(p==0)break;p<<=1;}
        if(p>cap&&p>0)doRehash(p);
    }
    iterator begin(){
        for(size_type i=0;i<cap;i++){
            if(b[i].head){
                TreeNode*p=b[i].head;
                if(b[i].isTree)while(p->left)p=p->left;
                return iterator(this,i,p);
            }
        }
        return end();
    }
    iterator end(){return iterator(this,cap,0);}
    const_iterator begin()const{
        for(size_type i=0;i<cap;i++){
            if(b[i].head){
                TreeNode*p=b[i].head;
                if(b[i].isTree)while(p->left)p=p->left;
                return const_iterator(this,i,p);
            }
        }
        return end();
    }
    const_iterator end()const{return const_iterator(this,cap,0);}
    const_iterator cbegin()const{return begin();}
    const_iterator cend()const{return end();}
    void swap(unordered_map&o){
        std::swap(b,o.b);
        std::swap(sz,o.sz);
        std::swap(cap,o.cap);
        std::swap(hf,o.hf);
        std::swap(eq,o.eq);
    }
};
int main(){cout<<0;}