g ++比使用列表的visual studio慢1000倍？

Question

请考虑以下代码段:

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
using namespace std;

#define NUM_ITER 100000

int main() {
    clock_t t = clock();
    std::list< int > my_list;
    std::vector< std::list< int >::iterator > list_ptr;

    list_ptr.reserve(NUM_ITER);

    for(int i = 0; i < NUM_ITER; ++i) {
        my_list.push_back(0);
        list_ptr.push_back(--(my_list.end()));
    }

    while(my_list.size() > 0) {
        my_list.erase(list_ptr[list_ptr.size()-1]);
        list_ptr.pop_back();
    }

    cout << "Done in: " << 1000*(clock()-t)/CLOCKS_PER_SEC << " msec!" << endl;
}

当我使用visual studio编译并运行它时,启用了所有优化,我得到输出:

完成:8毫秒!

当我用g ++编译并运行它时,使用标志

g ++ main.cpp -pedantic -O2

我得到了输出

完成:7349毫秒!

这比粗鲁慢1000倍.这是为什么？根据"cppreference"调用列表上的擦除应该只用掉恒定时间.

代码在同一台机器上编译和执行.

Answer 1

可能是由GCC发布的实现不存储大小,而MSVC发布的实现.在这种情况下,内环是O(n ^ 2),GCC,O(n),用于MSVC.

无论如何,C++ 11强制要求list :: size是常量时间,你可能想把它报告为bug.