Advertisement
Derga

Untitled

Oct 1st, 2020
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <forward_list>
  4.  
  5. using namespace std;
  6.  
  7. static const int hash_map_size = 10003;
  8.  
  9. int polynom_hash(const string& key) {
  10.     const int a = 123;
  11.  
  12.     int h = key[0];
  13.     for (int i = 1; i < key.size(); ++i) {
  14.         h = (key[i] + a * h) % hash_map_size;
  15.     }
  16.  
  17.     return h;
  18. }
  19.  
  20. int main() {
  21.     vector <forward_list <pair<string, int>>> v(hash_map_size);
  22.  
  23.     int number_of_operations;
  24.     cin >> number_of_operations;
  25.  
  26.     for (int i = 0; i < number_of_operations; ++i) {
  27.         string command;
  28.         string key;
  29.         cin >> command >> key;
  30.         auto& chain = v[polynom_hash(key)];
  31.         bool operation_complete = false;
  32.  
  33.         if (command == "put") {
  34.             int value;
  35.             cin >> value;
  36.             for (auto& elem : chain) {
  37.                 if (elem.first == key) {
  38.                     elem.second = value;
  39.                     operation_complete = true;
  40.                     break;
  41.                 }
  42.             }
  43.             if (!operation_complete) {
  44.                 chain.emplace_front(key, value);
  45.             }
  46.             continue;
  47.         }
  48.  
  49.         if (command == "get") {
  50.             for (const auto& elem : chain) {
  51.                 if (elem.first == key) {
  52.                     cout << elem.second << '\n';
  53.                     operation_complete = true;
  54.                     break;
  55.                 }
  56.             }
  57.             if (!operation_complete) {
  58.                 cout << -1 << '\n';
  59.             }
  60.             continue;
  61.         }
  62.        
  63.         if (command == "delete") {
  64.             auto slow = chain.begin();
  65.             auto fast = chain.begin();
  66.            
  67.             while (fast != chain.end() && fast->first != key) {
  68.                 slow = fast;
  69.                 fast++;
  70.             }
  71.            
  72.             if (fast == chain.end()) {
  73.                 cout << "error" << '\n';
  74.                 continue;
  75.             }
  76.  
  77.             if (fast != slow) {
  78.                 chain.erase_after(slow);
  79.             } else {
  80.                 chain.pop_front();
  81.             }
  82.             cout << "ok" << '\n';
  83.         }
  84.     }
  85.  
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement