Is it optimized when erasing the n last items in std::vector

Question

As I know, if the order of the vector is not important, it is faster to use the swap-pop_back idiom for removing an single item from std::vector. For example:

auto it = std::find(my_vec.begin(),my_vec.end(),SOME_VALUE); std::swap(*it,my_vector.back()); my_vector.pop_back();

The previous example avoids copying many elements.

From the same perspective, if I want to call std::vector::erase on a range which is represent the last n items of a std::vector, would it be optimised and behaves like multi pop_back?

Example:

auto it = std::find(my_vec.begin(),my_vec.end(),SOME_VALUE); my_vec.erase(it,my_vec.end()); // Erase everything from 'it' and beyond

Why do you think it would be "optimal" for it to behave as "multi pop_back"? That sounds quite sub-optimal to me. — juanchopanza
– juanchopanza, Commented Mar 8, 2016 at 9:28
You mean: why do I think that multi pop_back is a good thing at all ? — Humam Helfawi
– Humam Helfawi, Commented Mar 8, 2016 at 9:29
I mean why is it particularly good for removing the last n elements. — juanchopanza
– juanchopanza, Commented Mar 8, 2016 at 9:30
As far as I know, Swap-pop idiom avoid reallocation which results in more speed. I need the same here for range rather than 1 item — Humam Helfawi
– Humam Helfawi, Commented Mar 8, 2016 at 9:30
good question. With respect ot the swap/pop-back idea, here is one answer supporting it. I'm sure I've also saw timing result on SO, but I can't find them now. — davidhigh
– davidhigh, Commented Mar 8, 2016 at 10:20

legends2k · Accepted Answer · 2016-03-08 10:32:45Z

if I call std::vector::erase on a range which is represent the last n items of a std::vector, would it be optimised and behaves like multi pop_back?

If I understand you right, think the worry here is there shouldn't be any reseating operation like an erase in the middle. If this is the case, the standard guarantees that (emphasis mine):

Complexity

Linear in the distance between first and last, plus linear in the distance between last and end of the container.

The emphasised part is for the reseating. However, since this is zero, there will be no cost incurred when removing elements from the back.

A worthwhile thing to do is to disassemble the optimized output of some such code and see if this is just not a pointer assign/decrement operation in your toolchain.

Richard Hodges · Accepted Answer · 2016-03-08 09:33:23Z

As I know, if the order of the vector is not important, it is faster to use the swap-pop_back idiom for removing from std::vector.

Not sure what you mean by this. Anything involving multiple calls to pop-back is unlikely to be optimal.

From the same perspective, if I call std::vector::erase on a range which is represent the last n items of a std::vector, would it be optimised

It depends on the library implementation, but almost certainly.

and behaves like multi pop_back?

No

As I know, if the order of the vector is not important, it is faster to use the swap-pop_back idiom for removing from std::vector. means: if the order in the vector is not important, and you want to delete one element in the middle of the vector, instead of simply eraseing it from the middle, it is more efficient to swap this element with the last element in the vector and pop_back. Because the first alternative has to replace all elements after the erased one, whereas the second doesn't.

Collectives™ on Stack Overflow

Is it optimized when erasing the n last items in std::vector

2 Answers 2

Complexity

Comments

1 Comment

Linked

Hot Network Questions