c ++中的向量是如此之慢吗？

Question

我正在制作一个解决这个问题的程序:http://opc.iarcs.org.in/index.php/problems/BOOKLIST

我使用矢量的唯一地方是:

for(int i =0;i < total_books; i++){
    int temp;
    cin >> temp;
    books_order.push_back(temp);
}

和

for(int i = 0;i < total_entries; i++){
    int index;
    cin >> index;
    index--;
    cout << books_order[index] << endl;
    books_order.erase(books_order.begin()+index);
}

(这是我的完整代码:http://cpaste.org/1377/)

我从向量中使用的唯一函数是vector :: erase,vector :: push_back和vector :: begin.对于大输入,我的代码花费的时间超过3秒(这是该问题的时间限制),但是当我删除向量函数时,它运行得更快(但是给出了错误的答案)

我明白在这个问题中使用向量是错误的,我的算法很慢,但我不明白为什么它很慢.

如果您知道为什么我使用的功能很慢,请向我解释.谢谢.

Answer 1

我从向量中使用的唯一函数是vector :: erase,vector :: push_back和vector :: begin

我会说这是你的问题.vector::erase是的O(n),其他的是不变的时间,不应该导致在线判断问题的效率问题.避免擦除方法.

但是,一般来说,如果你事先知道数组的大小,我会使用一个简单的数组.如果可以提供帮助,请不要添加任何不必要的开销.

要解决您链接的问题,请考虑使用集合:其擦除方法O(log n)和插入方法一样.如果您需要随机删除,那么您通常应该使用这种方法.

编辑:我忘记了C++也有优先队列,所以也要考虑一下.既然你只关心这里的最大值,它可能比一个集合更快,虽然它们都具有相同的理论复杂性(一个堆可以检索最小/最大值O(1),但删除它,你必须为这个问题做,O(log n))在这种情况下,任何一个应该工作得很好.

Answer 2

IMO的罪魁祸首是vector::erase它将移除所有元素之后移动所有元素.因此,除非你总是删除最后一个元素,否则它可能会很慢.