#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sys/time.h>
#include <inttypes.h>

using namespace std;

struct Big {
    int data[5];
    int id;
    Big(int _id): id(_id){}
};

bool bigcmp(const Big& lhs, const Big& rhs) {return lhs.id > rhs.id;}
bool bigcmpm1(const Big& lhs, const Big& rhs) {return lhs.id < rhs.id;}
bool pbigcmp(const Big* lhs, const Big* rhs) {return lhs->id > rhs->id;}
bool pbigcmpm1(const Big* lhs, const Big* rhs) {return lhs->id < rhs->id;}

typedef uint64_t u64;
static u64 nsec() {
        struct timeval tv;
        if(gettimeofday(&tv, 0) < 0)
                return -1;
        return (u64)tv.tv_sec*1000*1000*1000 + tv.tv_usec*1000;
}

const u64 nsec_in_sec = 1000*1000*1000;
class stats {
        double n, M2, _mean;
public:
        stats():n(0),M2(0),_mean(0){}
        stats& add(double x) {
                n++;
                double delta = x - _mean;
                _mean += delta/n;
                M2 += delta*(x-_mean);
                return *this;
        }
        double mean() {return _mean;}
        double stddev() {return sqrt(M2/n);}
};


int main(int, char**) {
    stats p,v;
    const int SZ = 500000;
    vector<Big> b;
    vector<Big*> pb;
    for (int i=0; i<SZ; i++) {
        b.push_back(Big(i));
        pb.push_back(new Big(i));
    }
    for (int times=10; times>0; times--) {
        u64 start = nsec();
        sort(b.begin(), b.end(), bigcmp);
        sort(b.begin(), b.end(), bigcmpm1);
        v.add(nsec()-start);
    }
    for (int times=10; times>0; times--) {
        u64 start = nsec();
        sort(pb.begin(), pb.end(), pbigcmp);
        sort(pb.begin(), pb.end(), pbigcmpm1);
        p.add(nsec()-start);
    }
    cout << "By value   " << v.mean()/nsec_in_sec << " sec std " 
        << v.stddev()/nsec_in_sec << " sec" << endl;
    cout << "By pointer " << p.mean()/nsec_in_sec << " sec std " 
        << p.stddev()/nsec_in_sec << " sec" << endl;
}