Last active

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist
View Ouput
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
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
View Ouput
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
#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.