Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <chrono>
#include <unordered_set>
using namespace std::chrono;
template<typename Key>
class trivial_unordered_set {
using Bucket = std::vector<Key>;
std::vector<Bucket> buckets;
size_t size_ = 0;
public:
trivial_unordered_set() {
buckets.resize(2<<14);
}
size_t size(){ return size_; }
void insert(const Key &key) {
auto hash = std::hash<Key>()(key);
auto & bucket = buckets[hash % buckets.size()];
for (auto &e : bucket)
if (e == key)
return;
bucket.push_back(key);
size_++;
}
bool find(const Key &key) {
auto hash = std::hash<Key>()(key);
const auto & bucket = buckets[hash % buckets.size()];
for (auto &e : bucket)
if (e == key)
return true;
return false;
}
};
int main(){
trivial_unordered_set<int> set;
auto t1 = high_resolution_clock::now();
for (int i = 0; i < 1000000; ++i)
set.insert(i);
auto t2 = high_resolution_clock::now();
for (int i = 0; i < 1000000; ++i)
set.find(i);
auto t3 = high_resolution_clock::now();
std::cout << duration_cast<microseconds>(t2-t1).count()/1000.0 << "\n";
std::cout << duration_cast<microseconds>(t3-t2).count()/1000.0 << "\n";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.