#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <chrono>
#include <algorithm>
using Entry = std:: tuple < std:: string , int , int > ;
int main( int argc, char ** argv)
{
const auto t_0 = std:: chrono :: high_resolution_clock :: now ( ) ;
std:: vector < Entry> v;
v.reserve ( argc * 1000 * 1000 ) ;
for ( std:: size_t i = 0 ; i < v.capacity ( ) ; ++ i )
{
v.emplace_back ( argv[ 0 ] , 0 , 0 ) ;
}
const auto t_1 = std:: chrono :: high_resolution_clock :: now ( ) ;
std:: vector < Entry* > pv;
pv.reserve ( argc * 1000 * 1000 ) ;
for ( std:: size_t i = 0 ; i < pv.capacity ( ) ; ++ i )
{
pv.push_back ( new std:: tuple < std:: string , int , int > ( argv[ 0 ] , 0 , 0 ) ) ;
}
const auto t_2 = std:: chrono :: high_resolution_clock :: now ( ) ;
auto rv = [ & ] ( )
{
std:: sort ( v.begin ( ) , v.end ( ) , [ ] ( const Entry& a, const Entry& b) { return a < b; } ) ;
return std:: get < 1 > ( v.back ( ) ) ;
} ( ) ;
const auto t_3 = std:: chrono :: high_resolution_clock :: now ( ) ;
auto rpv = [ & ] ( )
{
std:: sort ( pv.begin ( ) , pv.end ( ) , [ ] ( const Entry* a, const Entry* b) { return * a < * b; } ) ;
return std:: get < 1 > ( * pv.back ( ) ) ;
} ( ) ;
const auto t_4 = std:: chrono :: high_resolution_clock :: now ( ) ;
for ( auto & e : pv )
{
delete e;
}
const auto t_5 = std:: chrono :: high_resolution_clock :: now ( ) ;
std:: cout << ( t_1 - t_0) .count ( ) << " for construction of v\n "
<< ( t_3 - t_2) .count ( ) << " for sorting v\n "
<< ( t_3 - t_2) .count ( ) + ( t_1 - t_0) .count ( ) << " in total for v\n "
<< ( t_2 - t_1) .count ( ) << " for construction of pv\n "
<< ( t_4 - t_3) .count ( ) << " for sorting pv\n "
<< ( t_5 - t_4) .count ( ) << " for destruction of pv\n "
<< ( t_2 - t_1) .count ( ) + ( t_4 - t_3) .count ( ) + ( t_5 - t_4) .count ( ) << " in total for pv\n " ;
return rpv - rv;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDxjaHJvbm8+CiNpbmNsdWRlIDxhbGdvcml0aG0+Cgp1c2luZyBFbnRyeSA9IHN0ZDo6dHVwbGU8c3RkOjpzdHJpbmcsIGludCwgaW50PjsKCmludCBtYWluKGludCBhcmdjLCBjaGFyKiogYXJndikKewoJY29uc3QgYXV0byB0XzAgPSBzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsKCXN0ZDo6dmVjdG9yPEVudHJ5PiB2OwoJdi5yZXNlcnZlKGFyZ2MgKiAxMDAwICogMTAwMCk7Cglmb3IgKCBzdGQ6OnNpemVfdCBpID0gMDsgaSA8IHYuY2FwYWNpdHkoKTsgKytpICkKCXsKCQl2LmVtcGxhY2VfYmFjayhhcmd2WzBdLCAwLCAwKTsKCX0KCWNvbnN0IGF1dG8gdF8xID0gc3RkOjpjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CglzdGQ6OnZlY3RvcjxFbnRyeSo+IHB2OwoJcHYucmVzZXJ2ZShhcmdjICogMTAwMCAqIDEwMDApOwoJZm9yICggc3RkOjpzaXplX3QgaSA9IDA7IGkgPCBwdi5jYXBhY2l0eSgpOyArK2kgKQoJewoJCXB2LnB1c2hfYmFjayhuZXcgc3RkOjp0dXBsZTxzdGQ6OnN0cmluZywgaW50LCBpbnQ+KGFyZ3ZbMF0sIDAsIDApKTsKCX0KCWNvbnN0IGF1dG8gdF8yID0gc3RkOjpjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CglhdXRvIHJ2ID0gWyZdKCkKCXsKCQlzdGQ6OnNvcnQodi5iZWdpbigpLCB2LmVuZCgpLCBbXShjb25zdCBFbnRyeSYgYSwgY29uc3QgRW50cnkmIGIpIHsgcmV0dXJuIGEgPCBiOyB9KTsKCQlyZXR1cm4gc3RkOjpnZXQ8MT4odi5iYWNrKCkpOwoJfSgpOwoJY29uc3QgYXV0byB0XzMgPSBzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsKCWF1dG8gcnB2ID0gWyZdKCkKCXsKCQlzdGQ6OnNvcnQocHYuYmVnaW4oKSwgcHYuZW5kKCksIFtdKGNvbnN0IEVudHJ5KiBhLCBjb25zdCBFbnRyeSogYikgeyByZXR1cm4gKmEgPCAqYjsgfSk7CgkJcmV0dXJuIHN0ZDo6Z2V0PDE+KCpwdi5iYWNrKCkpOwoJfSgpOwoJY29uc3QgYXV0byB0XzQgPSBzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsKCWZvciAoIGF1dG8mIGUgOiBwdiApCgl7CgkJZGVsZXRlIGU7Cgl9Cgljb25zdCBhdXRvIHRfNSA9IHN0ZDo6Y2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpOwoJc3RkOjpjb3V0IDw8ICh0XzEgLSB0XzApLmNvdW50KCkgPDwgIiBmb3IgY29uc3RydWN0aW9uIG9mIHZcbiIKCSAgICAgICAgICA8PCAodF8zIC0gdF8yKS5jb3VudCgpIDw8ICIgZm9yIHNvcnRpbmcgdlxuIgoJICAgICAgICAgIDw8ICh0XzMgLSB0XzIpLmNvdW50KCkgKyAodF8xIC0gdF8wKS5jb3VudCgpIDw8ICIgaW4gdG90YWwgZm9yIHZcbiIKCSAgICAgICAgICA8PCAodF8yIC0gdF8xKS5jb3VudCgpIDw8ICIgZm9yIGNvbnN0cnVjdGlvbiBvZiBwdlxuIgoJICAgICAgICAgIDw8ICh0XzQgLSB0XzMpLmNvdW50KCkgPDwgIiBmb3Igc29ydGluZyBwdlxuIgoJICAgICAgICAgIDw8ICh0XzUgLSB0XzQpLmNvdW50KCkgPDwgIiBmb3IgZGVzdHJ1Y3Rpb24gb2YgcHZcbiIKCSAgICAgICAgICA8PCAodF8yIC0gdF8xKS5jb3VudCgpICsgKHRfNCAtIHRfMykuY291bnQoKSArICh0XzUgLSB0XzQpLmNvdW50KCkgPDwgIiBpbiB0b3RhbCBmb3IgcHZcbiI7CglyZXR1cm4gcnB2IC0gcnY7Cn0=