Advertisement
rudolf222222

Untitled

Nov 30th, 2022
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.76 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <list>
  4. #include <vector>
  5.  
  6. class HashMap {
  7.  private:
  8.   int buckets_count_ = 0;
  9.   int capacity_ = 0;
  10.   int size_ = 0;
  11.   using Bucket = std::list<int>;
  12.   using Pucket = Bucket*;
  13.   std::vector<Pucket> buckets_;
  14.   int HashFunction(int key);
  15.   std::vector<int> table_;
  16.   void InsertHelper(int val);
  17.   void DeleteHelper(int val);
  18.   bool SearchHelper(int val);
  19.   void FixCollision(int indx, int& item);
  20.  
  21.  public:
  22.   HashMap(int size);
  23.   void Insert(int val);
  24.   void Delete(int val);
  25.   void Search(int val);
  26.   void Clear() {
  27.     for (size_t i = 0; i < buckets_.size(); ++i) {
  28.       if (buckets_[i] != nullptr) {
  29.         delete buckets_[i];
  30.       }
  31.     }
  32.   }
  33. };
  34.  
  35. int HashMap::HashFunction(int key) { return (key & 0x7FFFFFFF) % capacity_; }
  36. HashMap::HashMap(int size) {
  37.   capacity_ = size;
  38.   table_ = std::vector<int>(size, INT32_MIN);
  39.   buckets_ = std::vector<Pucket>(size, nullptr);
  40. }
  41. void HashMap::Insert(int val) { InsertHelper(val); }
  42. void HashMap::Delete(int val) { DeleteHelper(val); }
  43. void HashMap::Search(int val) {
  44.   if (SearchHelper(val)) {
  45.     std::cout << "YES\n";
  46.   } else {
  47.     std::cout << "NO\n";
  48.   }
  49. }
  50. void HashMap::InsertHelper(int val) {
  51.   int index = HashFunction(val);
  52.   if (table_[index] != val) {
  53.     if (size_ == capacity_) {
  54.       table_.resize(size_ * 2, 0);
  55.       capacity_ = size_ * 2;
  56.     }
  57.     size_++;
  58.     table_[index] = val;
  59.   } else {
  60.     FixCollision(index, val);
  61.   }
  62. }
  63. void HashMap::FixCollision(int indx, int& item) {
  64.   Pucket temp = this->buckets_[indx];
  65.   if (temp == nullptr) {
  66.     this->buckets_[indx] = new Bucket();
  67.     this->buckets_[indx]->push_back(item);
  68.   } else {
  69.     this->buckets_[indx]->push_back(item);
  70.   }
  71. }
  72. bool HashMap::SearchHelper(int val) {
  73.   int ind = HashFunction(val);
  74.   Pucket pemp = buckets_[ind];
  75.   if (table_[ind] == val) {
  76.     return true;
  77.   }
  78.   if (pemp != nullptr) {
  79.     return std::binary_search(pemp->begin(), pemp->end(), val);
  80.   }
  81.   return false;
  82. }
  83. void HashMap::DeleteHelper(int val) {
  84.   int index = HashFunction(val);
  85.   Pucket temp = buckets_[index];
  86.   if (table_[index] != val) {
  87.     return;
  88.   }
  89.   if (temp == nullptr && table_[index] == val) {
  90.     table_[index] = INT32_MIN;
  91.     size_--;
  92.   } else {
  93.     table_[index] = INT32_MIN;
  94.     size_--;
  95.     buckets_[index]->remove(val);
  96.   }
  97. }
  98.  
  99. void Requests() {
  100.   int n = 0;
  101.   std::cin >> n;
  102.   HashMap ht(n);
  103.   char s = 0;
  104.   int req = 0;
  105.   for (int i = 0; i < n; ++i) {
  106.     std::cin >> s;
  107.     if (s == '+') {
  108.       std::cin >> req;
  109.       ht.Insert(req);
  110.     } else if (s == '-') {
  111.       std::cin >> req;
  112.       ht.Delete(req);
  113.     } else {
  114.       std::cin >> req;
  115.       ht.Search(req);
  116.     }
  117.   }
  118.   ht.Clear();
  119. }
  120. int main() {
  121.   Requests();
  122.   return 0;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement