custom map, C++ (gcc)

Language: Layout:

#include <cstddef>
#include <cstdint>
#include <random>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <cstdio>

using std::size_t;
using std::int32_t;
using std::int64_t;
using std::vector;
using std::unordered_map;
using std::map;
using std::printf;
using std::accumulate;
using std::sort;

template <typename _Key, typename _Val>
class custom_map
{
public:
    struct container 
    {
        _Key key;
        _Val val;
    };
    
    vector<container> w;
    
    _Val& operator[](const _Key& __k)
    {
        int start = 0;
        int end = w.size();
        size_t id = 0;
        _Key k;
        while (start<end)
        {
            id = start + ((end - start) >>1);
            k = w[id].key;
            if (k > __k) {
                end = id;
            } else if (k < __k) {
                start = id + 1;
            } else
                return (w[id].val);
        };
        container n;
        n.key = __k;
        if (id<w.size() && k < __k)
            id++;
        w.insert(w.begin() + id,n);
        return (w[id].val);
    }
};

vector<int32_t> gen(size_t n)
{
    const int32_t M=100000000;
    std::minstd_rand rng(1);
    vector<int32_t> ret(n,0);
    for(size_t i=0;i<n/2;++i) ret[i]=std::uniform_int_distribution<int32_t>(-M,+M)(rng);
    for(size_t i=0;i<n/2;++i) ret[i+(n+1)/2]=-ret[i];
    return ret;
}

double solve1(const vector<int32_t> &v)
{
    unordered_map<int32_t,int> w;
    w.reserve(v.size());
    for (size_t i=0; i<v.size(); i++)
    {
        w[v[i]]=i;
    }
    double t = clock();
    for (size_t i=0; i<v.size(); i++)
    {
        w[v[i]]++;
    }
    return t;
}

double solve2(const vector<int32_t> &v)
{
    map<int32_t,int> w;
    for (size_t i=0; i<v.size(); i++)
    {
        w[v[i]]=i;
    }
    double t = clock();
    for (size_t i=0; i<v.size(); i++)
    {
        w[v[i]]++;
    }
    return t;
}

bool func(custom_map<int32_t,int>::container& a, custom_map<int32_t,int>::container&b)
{
    return a.key < b.key;
}

double solve3(const vector<int32_t> &v)
{
    custom_map<int32_t,int> w;
    w.w.reserve(v.size());
    custom_map<int32_t,int>::container c;
    for (size_t i=0; i<v.size(); i++)
    {
        c.key=v[i];
        c.val=i;
        w.w.push_back(c);
    }
    sort(w.w.begin(),w.w.end(),&func);
    double t = clock();
    for (size_t i=0; i<v.size(); i++)
    {
        w[v[i]]++;
    }
    return t;
}

double solve4(const vector<int32_t> &v)
{
    size_t h = 256;
    custom_map<int32_t,int> w[h];
    for (size_t i=0; i<h; i++)
    {
        w[i].w.reserve(v.size()/h);
    }
    custom_map<int32_t,int>::container c;
    for (size_t i=0; i<v.size(); i++)
    {
        c.key=v[i];
        c.val=i;
        w[(c.key>>4) & 0xFF].w.push_back(c);
    }
    for (size_t i=0; i<h; i++)
        sort(w[i].w.begin(),w[i].w.end(),&func);
    double t = clock();
    for (size_t i=0; i<v.size(); i++)
    {
        w[(v[i]>>4)  & 0xFF][v[i]]++;
    }
    return t;
}

int main()
{
    printf("n         :     hash_map                                map                          custom sort_map                          custom hash_map\n");
    printf("              full  (    find) ms    per n\n");
    for(size_t i=4;i<20;++i)
    {
        size_t n=1ull<<i;
        printf("%-10zu:",n);
        vector<int32_t> v=gen(n);
        double t1,t2,t3,t4;
        double st1,st2,st3,st4;
        t1=clock();
        st1=solve1(v);
        double at1=clock();
        st1=at1-st1;
        t1=at1-t1;
        t2=clock();
        st2=solve2(v);
        double at2=clock();
        st2= at2-st2;
        t2 = at2-t2;
        t3 = clock();
        st3 = solve3(v);
        double at3=clock();
        st3= at3-st3;
        t3 = at3-t3;
        t4 = clock();
        st4 = solve4(v);
        double at4=clock();
        st4= at4-st4;
        t4 = at4-t4;
        t1 = t1 * 1000.0 / CLOCKS_PER_SEC;
        t2 = t2 * 1000.0 / CLOCKS_PER_SEC;
        t3 = t3 * 1000.0 / CLOCKS_PER_SEC;
        t4 = t4 * 1000.0 / CLOCKS_PER_SEC;
        st1 = st1 * 1000.0 / CLOCKS_PER_SEC;
        st2 = st2 * 1000.0 / CLOCKS_PER_SEC;
        st3 = st3 * 1000.0 / CLOCKS_PER_SEC;
        st4 = st4 * 1000.0 / CLOCKS_PER_SEC;
        printf("%8.3f (%8.3f) ms %8.3f   ",t1,st1,t1/n*1000000.0);
        printf("%8.3f (%8.3f) ms %8.3f   ",t2,st2,t2/n*1000000.0);
        printf("%8.3f (%8.3f) ms %8.3f   ",t3,st3,t3/n*1000000.0);
        printf("%8.3f (%8.3f) ms %8.3f   ",t4,st4,t4/n*1000000.0);
        printf("\n");
    }
    return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 1.23 sec, absolute running time: 2.51 sec, cpu time: 3.02 sec, memory peak: 27 Mb, absolute service time: 3,77 sec