#include <tr1/unordered_map>
#include <stdio.h>
#include <string>

int main() {
    typedef std::tr1::unordered_map<std::string, int> HashMap;
    HashMap mapNumber;
    mapNumber["one"] = 1;
    mapNumber["two"] = 2;
    std::tr1::hash<std::string> hashFunc = mapNumber.hash_function();
    for (HashMap::const_iterator it = mapNumber.begin();
            it != mapNumber.end(); it++) {
        printf("%s(hash code: %d) -> %d\n", it->first.c_str(),
                hashFunc(it->first), it->second);
    }
    return 0;
}

#include <tr1/unordered_map>
#include <map>
#include <stdio.h>
#include <string>
#include <sys/time.h>
#include <time.h>
#include <stdlib.h>

std::map<std::string, int> rbtreeMap;
std::tr1::unordered_map<std::string, int> hashMap;

void printtime() {
    struct timeval tm;
    gettimeofday(&tm, NULL);
    printf("%lu, %lu\n", tm.tv_sec, tm.tv_usec);
}

void initRbtreeMap(int init_count) {
    for (int i = 0; i < init_count; i++) {
        int r = rand() % init_count;
        char str[16] = {0};
        snprintf(str, sizeof str, "%d", r);
        rbtreeMap[str] = r;
    }
    printf("rb tree map size %d\n", rbtreeMap.size());
}

void initHashMap(int init_count) {
    for (int i = 0; i < init_count; i++) {
        int r = rand() % init_count;
        char str[16] = {0};
        snprintf(str, sizeof str, "%d", r);
        hashMap[str] = r;
    }
    printf("hash map size %d\n", hashMap.size());
}

void testRbtreeMap(int init_count, int test_count) {
    int hit = 0, miss = 0;
    for (int i = 0; i < test_count; i++) {
        int r = rand() % init_count;
        char str[16] = {0};
        snprintf(str, sizeof str, "%d", r);
        if (rbtreeMap.find(str) == rbtreeMap.end()) {
            miss++;
        } else {
            hit++;
        }
    }
    printf("rb tree hit count %d miss count %d\n",
            hit, miss);
}

void testHashMap(int init_count, int test_count) {
    int hit = 0, miss = 0;
    for (int i = 0; i < test_count; i++) {
        int r = rand() % init_count;
        char str[16] = {0};
        snprintf(str, sizeof str, "%d", r);
        if (hashMap.find(str) == hashMap.end()) {
            miss++;
        } else {
            hit++;
        }
    }
    printf("hash tree hit count %d miss count %d\n",
            hit, miss);
}

int main() {
    srand(time(NULL));
    int init_count = 500 * 1000;
    printtime();
    initRbtreeMap(init_count);
    printtime();
    initHashMap(init_count);
    printtime();
    int test_count = 10 * 1000 * 1000;
    testRbtreeMap(init_count, test_count);
    printtime();
    testHashMap(init_count, test_count);
    printtime();
    return 0;
}