Jump to content
  • Advertisement
Sign in to follow this  
hkBattousai

How does this "pop_front()" implementation work?

This topic is 1054 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was looking for how to erase the front element of an std::vector object, and I found the following code here.

template<typename T>
void pop_front(std::vector<T>& vec)
{
    assert(!vec.empty());
    vec.front() = std::move(vec.back());
    vec.pop_back();
}

As far as I understand, it moves the object at the back (assuming that the contained object is movable) to the front. The object at the back is now empty, and the object at the front is lost since it is overwritten. Then, it detaches the back element, leaving the front one overwritten with the lost back one.

 

But appearently, it doesn't happen like I said. The documentations says that the front() and back() objects return references. If they did return pointers or iterators and we swapped them, or we swapped the back and front objects with std::swap(), I could understand it. But in this code, it just looks like we overwrite the front element.

 

Can you please explain me how it works?

Share this post


Link to post
Share on other sites
Advertisement
If the front/back returned pointers or iterators it would not work at all because you would swap the pointers/iterators without touching what these instances pointed to. In hypothetical scenario where front and back returned pointers/iterators and you wanted to use swap you would have to say:
using std::swap; swap(*myVector.front(), *myVector.back());
Everything else would not have the intended effect.

In most cases "vec.front() = std::move(vec.back());" will in fact be identical to "swap(vec.front(), vec.back());" because a very easy way to implement a copy and move assignment operator in one go is by doing something like this

T& operator (T other)
{
    using std::swap;
    swap(*this, other);
    return *this;
}
Obviously this relies on you already having sensible move/copy constructors and a specialized swap.

Share this post


Link to post
Share on other sites

The move assignment in C++ is basically like the copy assignment, the key difference being that the moved object is left in an "will not be used again" state. So when back is 'moved' to front, front has become the back object. The back object is still there, but it'll no longer be the owner of any allocated memory. So yeah the front element is overwritten with the back element, and the back element is popped. This is very efficient because you don't have to move a bunch of objects in memory now.

 

There is however one caveat, and I'm thinking this is the part you are struggling with: the order of elements in the vector was changed in the process. So while this is an efficient way of getting rid of the first, or any other element for that matter, it doesn't preserve order. So this is actually not a pop_front, but a swap and pop function.

Share this post


Link to post
Share on other sites

The move assignment in C++ is basically like the copy assignment, the key difference being that the moved object is left in an "will not be used again" state.


That is not true in this context. Standard library constructs guarantee (unless explicitly stated otherwise and I still can't say any class that does) that they are in 'unspecified but valid' state. You are explicitly allowed to do any operations on them which do not have preconditions. The standard also requires that any objects you put into its container stick to the same rule.

Edit: maybe some examples are useful:
std::vector<MyData> data = { ... };
somethingElse = std::move(data);
// data is now in an unspecified but valid state
std::cout << data.size() << "\n"; // <-- this is never a problem although we don't know what will be printed
std::cout << data.front() << "\n"; // <-- this is an ERROR. data can be empty in which case we violate the precondition of front()
data.clear(); // from here on we know data is empty
data.push_back(...); // now we know there is one element in there
std::cout << data.front() << "\n"; // this is no problem now
Edited by BitMaster

Share this post


Link to post
Share on other sites

There is however one caveat, and I'm thinking this is the part you are struggling with: the order of elements in the vector was changed in the process.

 

I think there is a bigger problem than the order of elements being changed. The front element is being destroyed unless I understand this code wrongly.
Are we assuming, as in BitMaster's answer, that the object's move constructor will swap the data instead of moving it, or do we reserve this front position as the sanctuary of emigrants whose hometowns will be destroyed?

Share this post


Link to post
Share on other sites


I think there is a bigger problem than the order of elements being changed. The front element is being destroyed unless I understand this code wrongly.

 

The whole point of a pop_front is to destroy the front element. The only difference here is that you don't want to copy all elements after that front element to i-1 by instead putting the last element at fronts position. Am I missing something about your comment here?

Share this post


Link to post
Share on other sites

Are we assuming, as in BitMaster's answer, that the object's move constructor


No, I did not say that. I said a convenient way to implement the move assignment operator is using the method above (which combines move and copy assignment). You still need to have a sensible copy constructor and a sensible move constructor. It is possible (but by now means always desired) to implement move-construction using swap but then you need a specialized swap, otherwise you define one by using the other which will crash by exhausting the stack and never getting anything done.

or do we reserve this front position as the sanctuary of emigrants whose hometowns will be destroyed?

I have no real clue what you are saying here. The purpose of the code you posted above is to remove the first element. Unlike a traditional pop_front (which requires O(n) copy/move operations) that version only requires a single move operation. On the downside it does not preserve the sequence of the input array.

Share this post


Link to post
Share on other sites


That is not true in this context. Standard library constructs guarantee (unless explicitly stated otherwise and I still can't say any class that does) that they are in 'unspecified but valid' state. You are explicitly allowed to do any operations on them which do not have preconditions. The standard also requires that any objects you put into its container stick to the same rule.

Correct, the "will not be used again" was an attempt to make it clear the back object could be popped without consequences (assuming correct implementation).

 


The front element is being destroyed unless I understand this code wrongly.

Like Juliean said, that's kind of the point. Did you mean the front element not being properly destroyed because of the move assignment? If so, it's the move assignment's responsibility to make sure that things are handled properly. So if the front element owns memory, it should delete the memory in the move assignment before it takes over ownership from the back element.

Share this post


Link to post
Share on other sites

 

The whole point of a pop_front is to destroy the front element.

 

Of course! Stupid me. I was confused there. We shouldn't worry about the overwritten front element, because it is our purpose to delete it in the first place. I get it now. Thanks a lot. Sorry for the confusion.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!