3

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
Humam Helfawi
  • 19,566
  • 15
  • 85
  • 160
  • 1
    Why do you think it would be "optimal" for it to behave as "multi `pop_back`"? That sounds quite sub-optimal to me. – juanchopanza Mar 08 '16 at 09:28
  • You mean: why do I think that multi pop_back is a good thing at all ? – Humam Helfawi Mar 08 '16 at 09:29
  • I mean why is it particularly good for removing the last n elements. – juanchopanza Mar 08 '16 at 09: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 Mar 08 '16 at 09:30
  • I'm not sure I understand the question. Are you asking if `std::vector::erase()` is the best way to removes the last elements of a vector? – YSC Mar 08 '16 at 09:31
  • @YSC yes a kind of.. – Humam Helfawi Mar 08 '16 at 09:32
  • Yes, it's as optimized as can be – Viktor Sehr Mar 08 '16 at 09:35
  • 1
    good question. With respect ot the `swap/pop-back` idea, [here](http://stackoverflow.com/a/4442529/2412846) is one answer supporting it. I'm sure I've also saw timing result on SO, but I can't find them now. – davidhigh Mar 08 '16 at 10:20
  • The swap-pop idiom does not avoid reallocation. vector::erase is guaranteed to do no reallocation of memory at all. All the swap-pop idiom achieves is the minimisation of the number of elements copied, that is all – SJHowe Mar 08 '16 at 12:20
  • @davidhigh: Keep in mind that you're refering to an answer which predates C++11. Today, it can be even cheaper to move the element out (certainly for POD's that is a LOT cheaper). – MSalters Mar 08 '16 at 12:23
  • @SJHowe sorry I meant that and wrote reallocation by mistake. Thanks for notifying – Humam Helfawi Mar 08 '16 at 12:25

2 Answers2

5

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.

legends2k
  • 31,634
  • 25
  • 118
  • 222
1

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

Richard Hodges
  • 68,278
  • 7
  • 90
  • 142
  • *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 `erase`ing 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. – davidhigh Mar 08 '16 at 10:13