testcode

// ---------------------------------------------------------------------------------------------

#include <iostream>
#include <vector>
#include <list>
#include <initializer_list>
#include <sstream>
#include <cassert>
#include <cstring>
#include <set>
#include <algorithm>
#include <random>
#include <chrono>
#include <limits>
#include <array>
#include <fstream>

#include "../avl/avl-array-C++-1.2.1/src/avl_array.hpp"

template<typename T>
struct MyAlloc
{
    typedef T value_type;

    MyAlloc() = default;
    template<typename U> MyAlloc(const MyAlloc<U>&) {}

    T* allocate(int n)
    {
        T* p = buffer+cnt;
        cnt += n;
        return p;
    }
    void deallocate(T*, int n)
    {
        dcnt+=n;
        if(cnt==dcnt)
            cnt=dcnt=0;
    }
private:
    static T buffer[64];
    static int cnt,dcnt;
};

template<typename T>
T MyAlloc<T>::buffer[64];

template<typename T>
int MyAlloc<T>::cnt = 0;

template<typename T>
int MyAlloc<T>::dcnt = 0;

typedef unsigned short T;

namespace detail
{

    const int DIST = 20000;
    const int AVGSZ = 23;
    const int NTH = 11;

    std::default_random_engine generator( (unsigned int)std::chrono::system_clock::now().time_since_epoch().count() );
    std::uniform_int_distribution<T> distribution(0,DIST);

    T makeone()
    {
        return distribution(generator);
    }

    T nth_element( const std::multiset<T>& mst, int n )
    {
        auto iter = mst.begin();
        std::advance(iter,n);
        return *iter;
    }

    T alt_0( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            dummy += makeone();
        }
        return dummy;
    }

    T alt_1( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            std::vector<T> vt;
            vt.reserve(AVGSZ);
            for( int i=0; i<AVGSZ; ++i )
                vt.push_back( makeone() );
            nth_element( vt.begin(), vt.begin()+NTH, vt.end() );
            dummy += vt[NTH];
        }
        return dummy;
    }

    T alt_2( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            std::multiset<T> mst;
            for( int i=0; i<AVGSZ; ++i )
                mst.insert( makeone() );
            dummy += nth_element( mst, NTH );
        }
        return dummy;
    }

    T alt_2b( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            std::set<T> st;
            for( int i=0; i<AVGSZ; ++i )
                st.insert( makeone() );
            auto iter = st.begin();
            std::advance(iter,NTH );
            dummy += *iter;
        }
        return dummy;
    }

    T alt_3( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            std::list<T> lt;
            for( int i=0; i<AVGSZ; ++i )
            {
                auto val = makeone();
                auto iter = std::lower_bound( lt.begin(), lt.end(), val );
                lt.insert( iter, val );
                if( lt.size() > (NTH+1) )
                    lt.pop_back();
            }
            dummy += lt.back();
        }
        return dummy;
    }

    T alt_3b( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            std::list<T,MyAlloc<int>> lt;
            for( int i=0; i<AVGSZ; ++i )
            {
                auto val = makeone();
                auto iter = std::lower_bound( lt.begin(), lt.end(), val );
                lt.insert( iter, val );
                if( lt.size() > (NTH+1) )
                    lt.pop_back();
            }
            dummy += lt.back();
        }
        return dummy;
    }

    T alt_4( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            mkr::avl_array<T> aat;
            for( int i=0; i<AVGSZ; ++i )
            {
                aat.insert_sorted(makeone());
            }
            dummy += aat[NTH];
        }
        return dummy;
    }

    T alt_5( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            mkr::avl_array<T> aat;
            for( int i=0; i<AVGSZ; ++i )
            {
                aat.insert_sorted(makeone());
                if( aat.size() > (NTH+1) )
                    aat.pop_back();
            }
            dummy += aat[NTH];
        }
        return dummy;
    }

    T alt_6( int reps )
    {
        T dummy = 0;
        for( int r=0; r<reps; ++r )
        {
            unsigned char hist[DIST+2] = {0};
            for( int i=0; i<AVGSZ; ++i )
            {
                T val = makeone();
                hist[val] += 1;
            }
            size_t idx=0;
            size_t rem=NTH;
            T nth;
            while(true)
            {
                if( hist[idx] > rem )
                {
                    nth = idx;
                    break;
                }
                rem -= hist[idx];
                ++idx;
            }
            dummy += nth;
        }
        return dummy;
    }

    template<typename T>
    auto timeit( T f, int reps ) -> auto
    {
        using clk = std::chrono::high_resolution_clock;
        auto t1 = clk::now();
        f(reps);
        auto t2 = clk::now();
        return std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    }

}

int main()
{

    using namespace std;
    using namespace detail;

    #ifndef NDEBUG
    const int REPS = 5000;
    #else
    const int REPS = 100000;
    #endif

    ofstream out("result.txt");

    out << "testing "<< REPS << " repetitions" << endl;

    out << "variant 0, no-op (for overhead measure)" << endl;
    out << timeit( alt_0, REPS ) << " ms" << endl;

    out << "variant 1, vector + nth_element" << endl;
    out << timeit( alt_1, REPS ) << " ms" << endl;

    out << "variant 2, multiset + advance" << endl;
    out << timeit( alt_2, REPS ) << " ms" << endl;

    out << "variant 2b, set (not fully conformant)" << endl;
    out << timeit( alt_2b, REPS ) << " ms" << endl;

    out << "variant 3, list + lower_bound" << endl;
    out << timeit( alt_3, REPS ) << " ms" << endl;

    out << "variant 3b, list + block-allocator" << endl;
    out << timeit( alt_3b, REPS ) << " ms" << endl;

    out << "variant 4, avl-tree + insert_sorted" << endl;
    out << timeit( alt_4, REPS ) << " ms" << endl;

    out << "variant 4b, avl-tree + prune" << endl;
    out << timeit( alt_5, REPS ) << " ms" << endl;

    out << "variant 5, histogram" << endl;
    out << timeit( alt_6, REPS ) << " ms" << endl;

    cout << endl << "done" << endl;

    // fgetc(stdin);
}