Блог пользователя MinhTri

Why does C++ erase take so long?
Автор MinhTri, 12 лет назад, По-английски

Can someone help me?

I just solved problem 439C - Деву и разбиение массива. 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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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". ;)

→ Ответить