push_front

push_front だけくらいなら実験できるので、 vector に insert(v.begin(), i) とかするのと list に push_front する速度を比較してみた。

http://shinh.skr.jp/tmp/push_front.png

答え: int 40要素くらいなら vector もいいセン行く。

#include <stdio.h>
#include <time.h>
#include <vector>
#include <list>

using namespace std;

int main(int argc, char* argv[]) {
    vector<int> v;
    list<int> l;
    static const int TOT = 10000000;
    const int n = atoi(argv[1]);
    {
        clock_t cl = clock();
        for (int t = 0; t < TOT / n; t++) {
            for (int i = 0; i < n; i++) {
                v.insert(v.begin(), i);
            }
            v.clear();
        }
        printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC);
    }
    {
        clock_t cl = clock();
        for (int t = 0; t < TOT / n; t++) {
            for (int i = 0; i < n; i++) {
                l.push_front(i);
            }
            l.clear();
        }
        printf("%.3f\n", ((double)clock() - cl) / CLOCKS_PER_SEC);
    }
}