#include <iostream>
#include <map>
#include <unordered_map>
#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 maps
map<vector<int>, void*> s;
unordered_map<vector<int>, void*> 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 map
double start = clock();
// for each vector
for (auto& vec : vectors) {
// if it's not present
if (!s.count(vec)) {
// insert it
s[vec] = nullptr;
}
}
double finish = clock();
cout << "Tree map: " << (finish - start) / CLOCKS_PER_SEC << " s" << endl;
// Hash map
start = clock();
// for each vector
for (auto& vec : vectors) {
// if it's not present
if (!hs.count(vec)) {
// insert it
hs[vec] = nullptr;
}
}
finish = clock();
cout << "Hash map: " << (finish - start) / CLOCKS_PER_SEC << " s" << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGN0aW1lPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIEJvb3N0IGhhc2ggZnVuY3Rpb24gZm9yIGFycmF5cywgaXQncyBwcmV0dHkgZ29vZAp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIHZvaWQgaGFzaF9jb21iaW5lKHN0ZDo6c2l6ZV90JiBzZWVkLCBUIGNvbnN0JiB2KQp7CiAgICBzZWVkIF49IHN0ZDo6aGFzaDxUPigpKHYpICsgMHg5ZTM3NzliOSArIChzZWVkIDw8IDYpICsgKHNlZWQgPj4gMik7Cn0KCm5hbWVzcGFjZSBzdGQKewp0ZW1wbGF0ZTx0eXBlbmFtZSBUPgpzdHJ1Y3QgaGFzaDx2ZWN0b3I8VD4+CnsKdHlwZWRlZiB2ZWN0b3I8VD4gYXJndW1lbnRfdHlwZTsKdHlwZWRlZiBzdGQ6OnNpemVfdCByZXN1bHRfdHlwZTsKCnJlc3VsdF90eXBlIG9wZXJhdG9yKCkoYXJndW1lbnRfdHlwZSBjb25zdCYgaW4pIGNvbnN0CnsKCXNpemVfdCBzaXplID0gaW4uc2l6ZSgpOwoJc2l6ZV90IHNlZWQgPSAwOwoJZm9yIChzaXplX3QgaSA9IDA7IGkgPCBzaXplOyBpKyspIHsKCQloYXNoX2NvbWJpbmUoc2VlZCwgaW5baV0pOwoJfQoJcmV0dXJuIHNlZWQ7Cn0KfTsKfQovLyBFbmQgb2YgYm9vc3QgaGFzaCBmdW5jdGlvbgoKY29uc3QgaW50IFZFQ1RPUlMgPSAxMDAwOwpjb25zdCBpbnQgTEVOR1RIID0gMTAwICogMTAwMDsKCmludCBtYWluKCkgewoJLy8gVGVzdCBtYXBzCgltYXA8dmVjdG9yPGludD4sIHZvaWQqPiBzOwoJdW5vcmRlcmVkX21hcDx2ZWN0b3I8aW50Piwgdm9pZCo+IGhzOwoJLy8gQWxsIHZlY3RvcnMKCXZlY3Rvcjx2ZWN0b3I8aW50Pj4gdmVjdG9yczsKCS8vIEdlbmVyYXRpb24KCWZvciAoaW50IGkgPSAwOyBpIDwgVkVDVE9SUzsgKytpKSB7CgkJdmVjdG9yPGludD4gY3VyOwoJCWZvciAoaW50IGogPSAwOyBqIDwgTEVOR1RIOyArK2opIHsKCQkJY3VyLnB1c2hfYmFjayhyYW5kKCkpOwoJCX0KCQl2ZWN0b3JzLmVtcGxhY2VfYmFjayhzdGQ6Om1vdmUoY3VyKSk7Cgl9CgkvLyBUcmVlIG1hcAoJZG91YmxlIHN0YXJ0ID0gY2xvY2soKTsKCS8vIGZvciBlYWNoIHZlY3RvcgoJZm9yIChhdXRvJiB2ZWMgOiB2ZWN0b3JzKSB7CgkJLy8gaWYgaXQncyBub3QgcHJlc2VudAoJCWlmICghcy5jb3VudCh2ZWMpKSB7CgkJCS8vIGluc2VydCBpdAoJCQlzW3ZlY10gPSBudWxscHRyOwoJCX0KCX0KCWRvdWJsZSBmaW5pc2ggPSBjbG9jaygpOwoJY291dCA8PCAiVHJlZSBtYXA6ICIgPDwgKGZpbmlzaCAtIHN0YXJ0KSAvIENMT0NLU19QRVJfU0VDIDw8ICIgcyIgPDwgZW5kbDsKCS8vIEhhc2ggbWFwCglzdGFydCA9IGNsb2NrKCk7CgkvLyBmb3IgZWFjaCB2ZWN0b3IKCWZvciAoYXV0byYgdmVjIDogdmVjdG9ycykgewoJCS8vIGlmIGl0J3Mgbm90IHByZXNlbnQKCQlpZiAoIWhzLmNvdW50KHZlYykpIHsKCQkJLy8gaW5zZXJ0IGl0CgkJCWhzW3ZlY10gPSBudWxscHRyOwoJCX0KCX0KCWZpbmlzaCA9IGNsb2NrKCk7Cgljb3V0IDw8ICJIYXNoIG1hcDogIiA8PCAoZmluaXNoIC0gc3RhcnQpIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgIiBzIiA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0=