CODEWITHSUNDEEP
c++algorithmvector
2147483647
2147483647

Reputation: 1197

Are vectors in c++ so slow?

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.

Upvotes: 6

Views: 3024

Answers (7)

soulcheck
soulcheck

Reputation: 36777

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.

Upvotes: 7

IVlad
IVlad

Reputation: 43517

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.

Upvotes: 10

shuttle87
shuttle87

Reputation: 15964

If you know that the vector has a certain number of elements in it in advance you can reserve enough space to contain everything to save yourself reallocations of space within the vector:

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

However that's not the issue here, I'm sure if you profiled your code you would see a large overhead from the .erase() usage. Removing elements from the middle of a vector is slow because of how a vector is implemented it will need to move all the elements part the one that is removed. Consider using a different data structure instead such as std::array instead.

Upvotes: 1

mathematician1975
mathematician1975

Reputation: 21351

Unless you have called reserve to size your vector to the number of elements you have, calls to push_back will reallocate memory every time the new size will exceed the vector capacity. Consider using reserve to allocate memory sufficient for your elements and you should see a performance speed up, particularly if the vector is large. Also take heed of the other answers regarding use of erase.

Upvotes: 3

john
john

Reputation: 8027

Removing elements from the middle of a vector (with vector::erase) is slow. This is because all the higher elements of the vector must be moved down to fill the gap left by the element you've removed.

So this is not a case of vectors being slow, but you algorithm being slow because you've chosen an inappropriate data structure.

Upvotes: 2

Tobias Langner
Tobias Langner

Reputation: 10828

your problem is the call to "erase". If you check the documentation here, you'll note that:

Because vectors keep an array format, erasing on positions other than the vector end also moves all the elements after the segment erased to their new positions, which may not be a method as efficient as erasing in other kinds of sequence containers (deque, list).

either run the loop from the end or erase after the loop.

Upvotes: 2

Aamir
Aamir

Reputation: 5440

Do you really need a vector to achieve what you are doing?

You have to keep in mind how vectors work: They're essentially dynamic arrays that resize as you add more items in them. Resizing a vector is an O(n) operation (where n is the number of items in your vector) as it allocates new memory and copies the items over to the new vector.

You can read about what vectors are good at here.

I would recommend using a standard array instead -- which seems completely plausible since you already know how many total elements there are (which is total_books)

Upvotes: 0

Related Questions