gistfile1.txt

#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";
}