Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <list>
- #include <vector>
- class HashMap {
- private:
- int buckets_count_ = 0;
- int capacity_ = 0;
- int size_ = 0;
- using Bucket = std::list<int>;
- using Pucket = Bucket*;
- std::vector<Pucket> buckets_;
- int HashFunction(int key);
- std::vector<int> table_;
- void InsertHelper(int val);
- void DeleteHelper(int val);
- bool SearchHelper(int val);
- void FixCollision(int indx, int& item);
- public:
- HashMap(int size);
- void Insert(int val);
- void Delete(int val);
- void Search(int val);
- void Clear() {
- for (size_t i = 0; i < buckets_.size(); ++i) {
- if (buckets_[i] != nullptr) {
- delete buckets_[i];
- }
- }
- }
- };
- int HashMap::HashFunction(int key) { return (key & 0x7FFFFFFF) % capacity_; }
- HashMap::HashMap(int size) {
- capacity_ = size;
- table_ = std::vector<int>(size, INT32_MIN);
- buckets_ = std::vector<Pucket>(size, nullptr);
- }
- void HashMap::Insert(int val) { InsertHelper(val); }
- void HashMap::Delete(int val) { DeleteHelper(val); }
- void HashMap::Search(int val) {
- if (SearchHelper(val)) {
- std::cout << "YES\n";
- } else {
- std::cout << "NO\n";
- }
- }
- void HashMap::InsertHelper(int val) {
- int index = HashFunction(val);
- if (table_[index] != val) {
- if (size_ == capacity_) {
- table_.resize(size_ * 2, 0);
- capacity_ = size_ * 2;
- }
- size_++;
- table_[index] = val;
- } else {
- FixCollision(index, val);
- }
- }
- void HashMap::FixCollision(int indx, int& item) {
- Pucket temp = this->buckets_[indx];
- if (temp == nullptr) {
- this->buckets_[indx] = new Bucket();
- this->buckets_[indx]->push_back(item);
- } else {
- this->buckets_[indx]->push_back(item);
- }
- }
- bool HashMap::SearchHelper(int val) {
- int ind = HashFunction(val);
- Pucket pemp = buckets_[ind];
- if (table_[ind] == val) {
- return true;
- }
- if (pemp != nullptr) {
- return std::binary_search(pemp->begin(), pemp->end(), val);
- }
- return false;
- }
- void HashMap::DeleteHelper(int val) {
- int index = HashFunction(val);
- Pucket temp = buckets_[index];
- if (table_[index] != val) {
- return;
- }
- if (temp == nullptr && table_[index] == val) {
- table_[index] = INT32_MIN;
- size_--;
- } else {
- table_[index] = INT32_MIN;
- size_--;
- buckets_[index]->remove(val);
- }
- }
- void Requests() {
- int n = 0;
- std::cin >> n;
- HashMap ht(n);
- char s = 0;
- int req = 0;
- for (int i = 0; i < n; ++i) {
- std::cin >> s;
- if (s == '+') {
- std::cin >> req;
- ht.Insert(req);
- } else if (s == '-') {
- std::cin >> req;
- ht.Delete(req);
- } else {
- std::cin >> req;
- ht.Search(req);
- }
- }
- ht.Clear();
- }
- int main() {
- Requests();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement