#include <iostream>
#include <vector>
#include <list>
#include <ctime>
using namespace std;
int testVector(int count) {
vector<int> v;
for (int i=0; i<count; i++) v.push_back(count-i);
return v.size();
}
int testVector2(int count) {
vector<int> v;
for (int i=0; i<count; i++) v.insert(v.begin(), 1, i);
return v.size();
}
int testList(int count) {
list<int> v;
for (int i=0; i<count; i++) v.push_back(count-i);
return v.size();
}
int testList2(int count) {
list<int> v;
for (int i=0; i<count; i++) v.push_front(count-i);
return v.size();
}
int main() {
const int loopcnt = 1000000;
const int loopcnt2 = 100000;
clock_t sw;
sw = clock();
int c = testVector(loopcnt);
sw = clock() - sw;
cout << "vector back : " << c << " : " << sw / (double) CLOCKS_PER_SEC << endl;
sw = clock();
c = testVector2(loopcnt2);
sw = clock() - sw;
cout << "vector front : " << c << " : " << sw / (double) CLOCKS_PER_SEC << endl;
sw = clock();
c = testList(loopcnt);
sw = clock() - sw;
cout << "list back : " << c << " : " << sw / (double) CLOCKS_PER_SEC << endl;
sw = clock();
c = testList2(loopcnt);
sw = clock() - sw;
cout << "list front : " << c << " : " << sw / (double) CLOCKS_PER_SEC << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPGN0aW1lPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCB0ZXN0VmVjdG9yKGludCBjb3VudCkgewogIHZlY3RvcjxpbnQ+IHY7CiAgZm9yIChpbnQgaT0wOyBpPGNvdW50OyBpKyspIHYucHVzaF9iYWNrKGNvdW50LWkpOwogIHJldHVybiB2LnNpemUoKTsKfQoKaW50IHRlc3RWZWN0b3IyKGludCBjb3VudCkgewogIHZlY3RvcjxpbnQ+IHY7CiAgZm9yIChpbnQgaT0wOyBpPGNvdW50OyBpKyspIHYuaW5zZXJ0KHYuYmVnaW4oKSwgMSwgaSk7CiAgcmV0dXJuIHYuc2l6ZSgpOwp9CgppbnQgdGVzdExpc3QoaW50IGNvdW50KSB7CiAgbGlzdDxpbnQ+IHY7CiAgZm9yIChpbnQgaT0wOyBpPGNvdW50OyBpKyspIHYucHVzaF9iYWNrKGNvdW50LWkpOwogIHJldHVybiB2LnNpemUoKTsKfQoKaW50IHRlc3RMaXN0MihpbnQgY291bnQpIHsKICBsaXN0PGludD4gdjsKICBmb3IgKGludCBpPTA7IGk8Y291bnQ7IGkrKykgdi5wdXNoX2Zyb250KGNvdW50LWkpOwogIHJldHVybiB2LnNpemUoKTsKfQoKaW50IG1haW4oKSB7CiAgY29uc3QgaW50IGxvb3BjbnQgPSAxMDAwMDAwOwogIGNvbnN0IGludCBsb29wY250MiA9IDEwMDAwMDsKICBjbG9ja190IHN3OwogIHN3ID0gY2xvY2soKTsKICBpbnQgYyA9IHRlc3RWZWN0b3IobG9vcGNudCk7CiAgc3cgPSBjbG9jaygpIC0gc3c7CiAgY291dCA8PCAidmVjdG9yIGJhY2sgOiAiIDw8IGMgPDwgIiA6ICIgPDwgc3cgLyAoZG91YmxlKSBDTE9DS1NfUEVSX1NFQyA8PCBlbmRsOwogIHN3ID0gY2xvY2soKTsKICBjID0gdGVzdFZlY3RvcjIobG9vcGNudDIpOwogIHN3ID0gY2xvY2soKSAtIHN3OwogIGNvdXQgPDwgInZlY3RvciBmcm9udCA6ICIgPDwgYyA8PCAiIDogIiA8PCBzdyAvIChkb3VibGUpIENMT0NLU19QRVJfU0VDIDw8IGVuZGw7CiAgc3cgPSBjbG9jaygpOwogIGMgPSB0ZXN0TGlzdChsb29wY250KTsKICBzdyA9IGNsb2NrKCkgLSBzdzsKICBjb3V0IDw8ICJsaXN0IGJhY2sgOiAiIDw8IGMgPDwgIiA6ICIgPDwgc3cgLyAoZG91YmxlKSBDTE9DS1NfUEVSX1NFQyA8PCBlbmRsOwogIHN3ID0gY2xvY2soKTsKICBjID0gdGVzdExpc3QyKGxvb3BjbnQpOwogIHN3ID0gY2xvY2soKSAtIHN3OwogIGNvdXQgPDwgImxpc3QgZnJvbnQgOiAiIDw8IGMgPDwgIiA6ICIgPDwgc3cgLyAoZG91YmxlKSBDTE9DS1NfUEVSX1NFQyA8PCBlbmRsOwogIHJldHVybiAwOwp9Cg==