随机插入/删除的综合向量与链表基准

I guess if I were going to test something like this, I'd probably start with code something on this order:

#include <list>
#include <vector>
#include <algorithm>
#include <deque>
#include <time.h>
#include <iostream>
#include <iterator>

static const int size = 30000;

template <class T>
double insert(T &container) {
    srand(1234);
    clock_t start = clock();
    for (int i=0; i<size; ++i) {
        int value = rand();
        T::iterator pos = std::lower_bound(container.begin(), container.end(), value);
        container.insert(pos, value);
    }
// uncomment the following to verify correct insertion (in a small container).
//  std::copy(container.begin(), container.end(), std::ostream_iterator<int>(std::cout, "	"));
    return double(clock()-start)/CLOCKS_PER_SEC;
}


template <class T>
double del(T &container) {
    srand(1234);
    clock_t start = clock();
    for (int i=0; i<size/2; ++i) {
        int value = rand();
        T::iterator pos = std::lower_bound(container.begin(), container.end(), value);
        container.erase(pos);
    }
    return double(clock()-start)/CLOCKS_PER_SEC;
}       

int main() { 
    std::list<int> l;
    std::vector<int> v;
    std::deque<int> d;

    std::cout << "Insertion time for list: " << insert(l) << "
";
    std::cout << "Insertion time for vector: " << insert(v) << "
";
    std::cout << "Insertion time for deque: " << insert(d) << "

";

    std::cout << "Deletion time for list: " << del(l) << '
';
    std::cout << "Deletion time for vector: " << del(v) << '
';
    std::cout << "Deletion time for deque: " << del(d) << '
';

    return 0;
}

因为它使用clock，这应该给处理器时间而不是挂墙时间(尽管一些编译器，如MS VC++ 弄错了).它不会尝试测量插入时间，不包括找到插入点的时间，因为 1) 这需要更多的工作 2) 我仍然无法弄清楚它会完成什么.它当然不是 100% 严格，但考虑到我从中看到的差异，如果看到更仔细的测试有显着差异，我会有点惊讶.例如，使用 MS VC++，我得到:

Insertion time for list: 6.598
Insertion time for vector: 1.377
Insertion time for deque: 1.484

Deletion time for list: 6.348
Deletion time for vector: 0.114
Deletion time for deque: 0.82

Insertion time for list: 5.272
Insertion time for vector: 0.125
Insertion time for deque: 0.125

Deletion time for list: 4.259
Deletion time for vector: 0.109
Deletion time for deque: 0.109