Are vectors in c++ so slow?

Question

I am making a program that solves this problem here: http://opc.iarcs.org.in/index.php/problems/BOOKLIST

and the only places i am using vectors are:

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

and

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);
}

(here is my full code: http://cpaste.org/1377/)

The only functions i am using from vectors are vector::erase, vector::push_back and vector::begin. For large inputs my code take more time than 3 seconds(which is the time limit for that problem), but when i remove the vector function, it runs much faster(but gives a wrong answer ofcourse)

I understood that it is wrong using vectors in this problem and that my algorithm is very slow, but i did not understand why it is slow.

If you know why the functions i am using are slow please explain them to me. Thank you.

Answer 1

The only functions i am using from vectors are vector::erase, vector::push_back and vector::begin

I would say this is your problem. vector::erase is O(n), the others are constant time and should not cause efficiency issues in online judge problems. Avoid the erase method.

However, in general, if you know the size of your array in advance, I would just use a simple array. Don't add any unnecessary overhead if you can help it.

To solve the problem you linked to though, consider using a set: its erase method is O(log n), as are its insertion methods. That is what you should use generally if you need random removals.

Edit: I forgot that C++ had priority queues too, so look into those as well. Since you only care about the max here, it might be faster than a set, although they both have the same theoretical complexities (a heap can retrieve the min/max in O(1), but removing it, which you must do for this problem, is O(log n)) in this case, and either one should work just fine.

Answer 2

IMO the culprit is vector::erase as it will shift all the elements after the one removed. So unless you're removing always the last element it can be quite slow.