Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <vector>
- #include <iostream>
- #include <initializer_list>
- #include <iterator>
- #include <list>
- #include <exception>
- #include <string>
- #include <ctime>
- #include <unordered_map>
- #include <utility>
- template<class KeyType, class ValueType, class Hash = std::hash<KeyType>>
- class HashMap {
- public:
- typedef typename std::list<std::pair<const KeyType, ValueType>>::iterator iterator;
- typedef typename std::list<std::pair<const KeyType, ValueType>>::const_iterator const_iterator;
- private:
- std::vector<std::vector<iterator>> Data;
- std::list<std::pair<const KeyType, ValueType>> Pairs;
- std::list<size_t> NotEmptyCells;
- Hash hasher;
- std::vector<bool> isEmpty;
- std::vector<std::list<size_t>::iterator> NotEmptyPtr;
- public:
- HashMap(Hash hasher_init = Hash()) : hasher(hasher_init),
- isEmpty(std::vector<bool>(765322, true)) {
- Data.resize(765322);
- NotEmptyPtr.resize(765322);
- }
- Hash hash_function() const {
- return hasher;
- }
- HashMap(const std::initializer_list<std::pair<const KeyType, ValueType>>& l,
- Hash hasher_init = Hash()) : hasher(hasher_init),
- isEmpty(std::vector<bool>(765322, true)) {
- Data.resize(765322);
- NotEmptyPtr.resize(765322);
- for (auto el : l) {
- insert(el);
- }
- }
- template <class iterate>
- HashMap(iterate begin, iterate end, Hash hasher_init = Hash()) : hasher(hasher_init),
- isEmpty(std::vector<bool>(765322, true)) {
- Data.resize(765322);
- NotEmptyPtr.resize(765322);
- for (iterate it = begin; it != end; ++it) {
- insert(*it);
- }
- }
- const_iterator begin() const {
- return const_iterator(Pairs.cbegin());
- }
- iterator begin() {
- return iterator(Pairs.begin());
- }
- const_iterator end() const {
- return const_iterator(Pairs.cend());
- }
- iterator end() {
- return iterator(Pairs.end());
- }
- void insert(const std::pair<const KeyType, ValueType>& key) {
- size_t hash = hasher(key.first) % 765322;
- if (find(key.first) == Pairs.end()) {
- Pairs.push_back(key);
- Data[hash].push_back(--Pairs.end());
- if (isEmpty[hash]) {
- NotEmptyCells.push_back(hash);
- isEmpty[hash] = true;
- NotEmptyPtr[hash] = --NotEmptyCells.end();
- }
- }
- }
- void erase(const KeyType& key) {
- size_t hash = hasher(key) % 765322;
- auto it = Data[hash].begin();
- for (it = Data[hash].begin(); it != Data[hash].end(); ++it) {
- if ((*it)->first == key) {
- break;
- }
- }
- if (it != Data[hash].end()) {
- Pairs.erase(*it);
- Data[hash].erase(it);
- if (Data[hash].empty()) {
- isEmpty[hash] = true;
- NotEmptyCells.erase(NotEmptyPtr[hash]);
- }
- }
- }
- size_t size() const {
- return Pairs.size();
- }
- bool empty() const {
- return Pairs.empty();
- }
- void clear() {
- Pairs.clear();
- for (auto empty : NotEmptyCells) {
- Data[empty].clear();
- isEmpty[empty] = true;
- }
- }
- ValueType& operator[](const KeyType& key) {
- if (find(key) != Pairs.end()) {
- size_t hash = hasher(key) % 765322;
- for (auto i : Data[hash]) {
- if (i->first == key) {
- return i->second;
- }
- }
- }
- else {
- insert(std::make_pair(key, ValueType()));
- return (--Pairs.end())->second;
- }
- }
- const ValueType& at(const KeyType& key) const {
- if (find(key) != Pairs.end()) {
- size_t hash = hasher(key) % 765322;
- for (auto i : Data[hash]) {
- if ((*i).first == key) {
- return (*i).second;
- }
- }
- }
- else {
- throw std::out_of_range("I HATE PCFS");
- }
- }
- iterator find(const KeyType& key) {
- size_t hash = hasher(key) % 765322;
- for (auto it : Data[hash]) {
- if ((*it).first == key)
- return it;
- }
- return Pairs.end();
- }
- const_iterator find(const KeyType& key) const {
- size_t hash = hasher(key) % 765322;
- for (auto it : Data[hash]) {
- if ((*it).first == key)
- return it;
- }
- return Pairs.cend();
- }
- };
- std::string check(HashMap<int, int> a, std::unordered_map<int, int> b) {
- if (a.empty() && !b.empty()) {
- return "a is empty, b is not";
- }
- if (!a.empty() && b.empty()) {
- return "b is empty, a is not";
- }
- if (a.size() > b.size()) {
- return "a is bigger than b";
- }
- if (b.size() > a.size()) {
- return "b is bigger than a";
- }
- for (auto i : a) {
- if (b.find(i.first) == b.end()) {
- std::string err = "b does not have ";
- err += i.first;
- }
- if (b[i.first] != i.second) {
- std::string err = "b has another value for ";
- err += i.first;
- }
- }
- for (auto i : b) {
- if (a.find(i.first) == a.end()) {
- std::string err = "a does not have ";
- err += i.first;
- }
- if (a[i.first] != i.second) {
- std::string err = "a has another value for ";
- err += i.first;
- }
- }
- return "OK!";
- }
- int main() {
- const size_t commands = 1001;
- const size_t maxrand = 603;
- const size_t maxnum = 200;
- srand(time(0));
- clock_t timer = clock();
- HashMap<int, int> a{ { 1,3 },{ 4,2 },{ 3,5 } };
- std::unordered_map<int, int> b{ { 1,3 },{ 4,2 },{ 3,5 } };
- for (size_t i = 0; i < commands; ++i) {
- size_t num = i;
- if (num < 100) {
- int key = rand() % maxnum - maxnum / 2;
- int value = rand() % maxnum - maxnum / 2;
- //std::cout << "Adding " << key << " " << value << std::endl;
- a[key] = value;
- //std::cout << a[key];
- b[key] = value;
- }
- else if (num < 500) {
- int key = rand() % maxnum - maxnum / 2;
- int value = rand() % maxnum - maxnum / 2;
- //std::cout << "Inserting " << key << " " << value << std::endl;
- a.insert(std::pair<int, int>(key, value));
- b.insert(std::pair<int, int>(key, value));
- }
- else if (num < 1000) {
- int key = rand() % maxnum - maxnum / 2;
- std::cout << "Erasing " << key << std::endl;
- a.erase(key);
- b.erase(key);
- }
- else {
- std::cout << "Clearing ";
- a.clear();
- b.clear();
- }
- std::string s = check(a, b);
- //std::cout << s << std::endl;
- if (s != "OK!") { throw(-1); }
- }
- std::cout << (float)(clock() - timer) / CLOCKS_PER_SEC;
- std::cout << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement