c++ - 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 编译并运行它时，启用了所有优化，我得到了输出:

Done in: 8 msec!

当我用 g++ 编译和运行它时，使用标志

g++ main.cpp -pedantic -O2

我得到输出

Done in: 7349 msec!

大约慢了 1000 倍。这是为什么？根据“cppreference”，在列表上调用删除应该只用完常数时间。

代码是在同一台机器上编译和执行的。

Answer 1

可能是 GCC 提供的实现不存储大小，而 MSVC 提供的实现。在这种情况下，内部循环对于 GCC 是 O(n^2)，对于 MSVC 是 O(n)。

无论如何，C++11 要求 list::size 是常数时间，您可能希望将其报告为错误。