SHARE
TWEET

Untitled

a guest Dec 11th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3.  
  4. const int prime=3571;
  5.  
  6. int _hash(std::string key, int len, int prime){
  7.     int hash=len;
  8.     for(int i=0;i<len;i++){
  9.         hash= (hash<<5)^(hash>>27)^key[i];
  10.     }
  11.     return hash % prime;
  12. }
  13.  
  14. template <class type2>
  15. struct pair{
  16.     std::string key_;
  17.     type2 value;
  18. };
  19.  
  20. template <class type2>
  21. class map{
  22.     private:
  23.         //vector<pair> mas_;
  24.         int size;
  25.         pair<type2>** hash;
  26.         friend class itmap;
  27.     public:
  28.         map(){
  29.             size=0;
  30.             hash=new pair<type2>* [prime];
  31.             for(int i=0;i<prime;++i){
  32.                 hash[i]=nullptr;
  33.             }
  34.         }
  35.  
  36.         ~map(){
  37.             for(int i=0;i<prime;++i){
  38.                 if(hash[i]!=nullptr){
  39.                     delete [] hash[i];
  40.                 }
  41.             }
  42.             delete []  hash;
  43.         }
  44.  
  45.         class itmap{
  46.             private:
  47.                 pair<type2>** curr;
  48.             public:
  49.                 itmap(pair<type2>** a){
  50.                     curr=a;
  51.                 }
  52.                 itmap operator- (int n){
  53.                     for(int i=0;i<n;++i){
  54.                         --curr;
  55.                     }
  56.                     return curr;
  57.                 }
  58.  
  59.                 itmap operator+ (int n){
  60.                     for(int i=0;i<n;++i){
  61.                         ++curr;
  62.                     }
  63.                     return curr;
  64.                 }
  65.                
  66.                 itmap operator++(){
  67.                     while(1){
  68.                         ++curr;
  69.                         if(*(curr)!=nullptr){
  70.                             return curr;
  71.                         }
  72.                     }
  73.                 }
  74.  
  75.                 itmap operator--(){
  76.                     while(1){
  77.                         --curr;
  78.                         if(*(curr)!=nullptr){
  79.                             return curr;
  80.                         }
  81.                     }
  82.                 }
  83.                 auto operator*(){ return *curr;}
  84.         };
  85.  
  86.         void insert(std::string key,type2 a){
  87.             if(size==prime){
  88.                 std::cout<<"mass full"<<std::endl;
  89.                 return;
  90.             }
  91.             int b=_hash(key,key.size(),prime);
  92.             if (hash[b]==nullptr || hash[b]->key_==key){
  93.                 if(hash[b]==nullptr){
  94.                     hash[b]=new pair<type2> [1];
  95.                     hash[b]->key_=key;
  96.                     hash[b]->value=a;
  97.                     size++;
  98.                     return;
  99.                 }
  100.                 hash[b]->key_=key;
  101.                 hash[b]->value;
  102.                 return;
  103.             }
  104.             //          std::cout<<key<<std::endl;
  105.             while(true){
  106.                 b=(b+1)%prime;
  107.                 if (hash[b]==nullptr || hash[b]->key_==key){
  108.                     if(hash[b]==nullptr){
  109.                         hash[b]=new pair<type2> [1];
  110.                         hash[b]->key_=key;
  111.                         hash[b]->value=a;
  112.                         size++;
  113.                         return;
  114.                     }
  115.                     hash[b]->key_=key;
  116.                     hash[b]->value;
  117.                     return;
  118.                 }
  119.  
  120.             }
  121.         }  
  122.  
  123.         type2* find(std::string key){
  124.             int b=_hash(key,key.size(),prime);
  125.             int p=b;
  126.             if(hash[b]!=nullptr){
  127.                 if(hash[b]->key_==key){
  128.                     return &hash[b]->value;
  129.                 }
  130.                 b=(b+1)%prime;
  131.                 while(hash[b]!=nullptr && p!=b && _hash(hash[b]->key_,hash[b]->key_.size(),prime)==p){
  132.                     if(hash[b]->key_==key){
  133.                         return &(hash[b]->value);
  134.                     }
  135.                     b=(b+1)%prime;
  136.                 }
  137.                 std::cout<<"no such element"<<std::endl;
  138.                 return NULL;
  139.             }
  140.             b=(b+1)%prime;
  141.             while(hash[b]==nullptr && b!=p){
  142.                 b=(b+1)%prime;
  143.             }
  144.             if(b==p){
  145.                 std::cout<<"no such elem"<<std::endl;
  146.                 return NULL;
  147.             }
  148.             while(hash[b]!=nullptr && p!=b && _hash(hash[b]->key_,hash[b]->key_.size(),prime)==p){
  149.                 if(hash[b]->key_==key){
  150.                     return &(hash[b]->value);
  151.                 }
  152.                 b=(b+1)%prime;
  153.             }
  154.             std::cout<<"no such element"<<std::endl;
  155.             return NULL;
  156.         }
  157.  
  158.         void delet(std::string key){
  159.             int b=_hash(key,key.size(),prime);
  160.             if(hash[b]==nullptr){
  161.                 std::cout<<"no such element"<<std::endl;
  162.                 return;
  163.             }
  164.             if(hash[b]->key_==key){
  165.                 size--;
  166.                 delete [] hash[b];
  167.                 hash[b]=nullptr;
  168.                 return;
  169.             }
  170.  
  171.             int p=b;
  172.             b=(b+1)%prime;
  173.             while(hash[b]!=nullptr && p!=b && _hash(hash[b]->key_,hash[b]->key_.size(),prime)==p){
  174.                 if(hash[b]->key_==key){
  175.                     size--;
  176.                     delete [] hash[b];
  177.                     hash[b]=nullptr;
  178.                     return;
  179.                 }
  180.                 b=(b+1)%prime;
  181.             }
  182.             std::cout<<"no such element"<<std::endl;
  183.  
  184.         }
  185.  
  186.         int getsize(){
  187.             return size;
  188.         }
  189.  
  190.         void print(){
  191.             for(int i=0;i<prime;i++){
  192.                 if(hash[i]!=nullptr){
  193.                     std::cout<<hash[i]->key_<<" :"<<_hash(hash[i]->key_,hash[i]->key_.size(),prime)<< ": "<<hash[i]->value<<std::endl;
  194.                 }
  195.             }
  196.         }
  197.  
  198.         itmap begin() {
  199.             if(size==0)
  200.                 return NULL;
  201.             for(int i=0;i<prime;++i){
  202.                 if(hash[i]!=nullptr){
  203.                     itmap t(&hash[i]);
  204.                     return t;
  205.                 }
  206.             }
  207.         }
  208.         itmap end() {
  209.             if(size==0)
  210.                 return NULL;
  211.             for(int i=prime-1;i>-1;--i){
  212.                 if(hash[i]!=nullptr){
  213.                     itmap t(&hash[i]);
  214.                     return t;
  215.                 }
  216.             }
  217.         }
  218.  
  219. };
  220.  
  221. int main(){
  222.     map<std::string> a;
  223.     std::string s="asd";
  224.     for(int i=0;i<100;++i){
  225.         char b=i;
  226.         std::string c=s+b,m=c+'a';
  227.         a.insert(c,m);
  228.     }
  229.     /*
  230.     for(int i=0;i<50;++i){
  231.         char b=i;
  232.         std::string c=s+b;
  233.         a.delet(c);
  234.     }
  235.     std::cout<<a.getsize()<<std::endl;*/
  236.     map<std::string>::itmap b=a.begin();
  237.     for(int i=0;i<10;i++){
  238.     b+5;
  239.     (*b)->value="pobeda";
  240.     }
  241.     //std::cout<<(*b)->key_<<" : "<<(*(b))->value<<std::endl;
  242.     a.print();
  243.     return 0;
  244. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top