Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

MinhTri's blog

Why does C++ erase take so long?
By MinhTri, 10 years ago, In English

Can someone help me?

I just solved problem 439C - Devu and Partitioning of the Array. But I was stuck a very long time. First I used the erase method to delete vector element. But I got TLE. The code's here: 6865570. After a long time I changed to use back and pop_back method. The code's here: 6865483. And I got AC! I don't know why erase method takes my time so much. Do you guys have any ideas?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

vector::erase() method takes O(n) time, especially for odd.erase(odd.begin());

→ Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Actually vector erase takes exactly distance(it, x.end());

But you can use deque, that erase in min(distance(it, x.begin()), distance(it, x.end()));

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

the problem is with the line odd.erase(odd.begin());. this takes time because it erases the first element of the vector.

in ur AC code, try replacing odd.pop_back(); by odd.erase(odd.end()-1);. (u should get AC again.)
yes i know the two do exactly the same thing, but i'm telling this just to show u that vector::erase() doesn't always "take so long". ;)

→ Reply