#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
#include <ctime>

using namespace std;

// Boost hash function for arrays, it's pretty good
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
    seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{
template<typename T>
struct hash<vector<T>>
{
typedef vector<T> argument_type;
typedef std::size_t result_type;

result_type operator()(argument_type const& in) const
{
	size_t size = in.size();
	size_t seed = 0;
	for (size_t i = 0; i < size; i++) {
		hash_combine(seed, in[i]);
	}
	return seed;
}
};
}
// End of boost hash function

const int VECTORS = 1000;
const int LENGTH = 100 * 1000;

int main() {
	// Test sets
	set<vector<int>> s;
	unordered_set<vector<int>> hs;
	// All vectors
	vector<vector<int>> vectors;
	// Generation
	for (int i = 0; i < VECTORS; ++i) {
		vector<int> cur;
		for (int j = 0; j < LENGTH; ++j) {
			cur.push_back(rand());
		}
		vectors.emplace_back(std::move(cur));
	}
	// Tree set
	double start = clock();
	// for each vector
	for (auto& vec : vectors) {
		// if it's not present
		if (!s.count(vec)) {
			// insert it
			s.insert(vec);
		}
	}
	double finish = clock();
	cout << "Tree set: " << (finish - start) / CLOCKS_PER_SEC << " s" << endl;
	// Hash set
	start = clock();
	// for each vector
	for (auto& vec : vectors) {
		// if it's not present
		if (!hs.count(vec)) {
			// insert it
			hs.insert(vec);
		}
	}
	finish = clock();
	cout << "Hash set: " << (finish - start) / CLOCKS_PER_SEC << " s" << endl;
	return 0;
}