Skip to content

@detunized /Ouput
Last active

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Map without reserve
size: 0
bucket_count: 23
load_factor: 0
Allocation count: 0
size: 0
bucket_count: 23
load_factor: 0
Reallocation:
size: 23
bucket_count: 53
load_factor: 0.433962
Reallocation:
size: 53
bucket_count: 109
load_factor: 0.486239
Reallocation:
size: 109
bucket_count: 227
load_factor: 0.480176
Reallocation:
size: 227
bucket_count: 467
load_factor: 0.486081
Reallocation:
size: 467
bucket_count: 953
load_factor: 0.490031
Reallocation:
size: 953
bucket_count: 2029
load_factor: 0.469689
Reallocation:
size: 2029
bucket_count: 4349
load_factor: 0.466544
Reallocation:
size: 4349
bucket_count: 8783
load_factor: 0.495161
Reallocation:
size: 8783
bucket_count: 17749
load_factor: 0.494845
Reallocation:
size: 17749
bucket_count: 35933
load_factor: 0.493947
Reallocation:
size: 35933
bucket_count: 72817
load_factor: 0.49347
Reallocation:
size: 72817
bucket_count: 147793
load_factor: 0.492696
Reallocation:
size: 147793
bucket_count: 299951
load_factor: 0.492724
Reallocation:
size: 299951
bucket_count: 608903
load_factor: 0.492609
Reallocation:
size: 608903
bucket_count: 1236397
load_factor: 0.492482
Allocation count: 1000015
size: 1000000
bucket_count: 1236397
load_factor: 0.808802
0: 550454
1: 445645
2: 180174
3: 48593
4: 9708
5: 1568
6: 231
7: 22
8: 2
Map with reserve
size: 0
bucket_count: 23
load_factor: 0
Allocation count: 1
size: 0
bucket_count: 2144977
load_factor: 0
Allocation count: 1000000
size: 1000000
bucket_count: 2144977
load_factor: 0.466205
0: 1346008
1: 626748
2: 146625
3: 22663
4: 2669
5: 248
6: 15
7: 1
#include <unordered_map>
#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <stdlib.h>
using namespace std;
size_t allocation_count = 0;
void *operator new(size_t size)
{
++allocation_count;
return malloc(size);
}
void *operator new[](size_t size)
{
++allocation_count;
return malloc(size);
}
void operator delete(void *p)
{
if (p != nullptr)
free(p);
}
void operator delete[](void *p)
{
if (p != nullptr)
free(p);
}
class CountAllocations
{
public:
CountAllocations()
{
allocation_count = 0;
}
~CountAllocations()
{
cout << "Allocation count: " << allocation_count << "\n\n";
}
};
int random(int min, int max)
{
return rand() % (max - min + 1) + min;
}
string random_string(size_t length)
{
static string chars{"_0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
string s(length, ' ');
for (auto &c: s)
c = chars[random(0, chars.size() - 1)];
return s;
}
void print_map_info(unordered_map<string, int> const &m)
{
cout << " size: " << m.size() << '\n'
<< "bucket_count: " << m.bucket_count() << '\n'
<< " load_factor: " << m.load_factor() << "\n\n";
}
void populate_map(vector<string> const &keys, size_t reserve)
{
unordered_map<string, int> m;
print_map_info(m);
{
CountAllocations c;
if (reserve > 0)
m.reserve(reserve);
}
print_map_info(m);
{
CountAllocations c;
auto bucket_count = m.bucket_count();
for (int i = 0; i < keys.size(); ++i)
{
m[keys[i]] = i;
if (m.bucket_count() != bucket_count)
{
bucket_count = m.bucket_count();
cout << "Reallocation:\n";
print_map_info(m);
}
}
}
print_map_info(m);
map<size_t, size_t> d;
for (size_t i = 0; i < m.bucket_count(); ++i)
++d[m.bucket_size(i)];
for (auto i: d)
cout << i.first << ": " << i.second << '\n';
}
int main(int argc, char const *argv[])
{
size_t const N = 1 * 1000 * 1000;
srand(time(nullptr));
vector<string> keys(N);
for (auto &i: keys)
i = random_string(random(25, 50));
cout << "Map without reserve\n\n";
populate_map(keys, 0);
cout << "Map with reserve\n\n";
populate_map(keys, N);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.