How can I move an element from a C++11 container to the back of the container?

Question

I'm specifically using a list but could use a vector if needed (or probably any container; would be good to get general container solutions).

I have a list of elements. I have a value. I pass this value to each element; one of them will respond. The first one that responds I want to move to the back of the container.

My existing code looks like this:

std::list<elements> m_elements ... bool handle(event e) { for(auto &element : m_elements) { if(element->handle()) return true; } return false; }

But what I now want to do is move the element that handle()s the event to the end of m_elements. For a bit of context, I'm working on a GUI system of windows. So whichever window happens to capture the mouse needs to jump to the top when being drawn; windows in m_elements are being drawn one by one (so the last element is on top).

It might be worth noting that elements are std::shared_ptrs.

EDIT

In case anyone comes across this question and answer for a similar situation.

I actually needed to iterate backwards through my container to process input because the last element is drawn last, i.e. it is on top, so it should be the first element that should try to intercept input.

This was simple to do. However, splicing a reverse iterator to the end of your container is a bit trickier. std::reverse_iterator.base() returns you the NEXT iterator if the iterator was a forward iterator, so you need to std::advance the iterator by -1 in order to successfully move the actual element that "intercepted".

for(auto itr = m_elements.rbegin(); itr != m_elements.rend(); ++itr) { if((*itr)->handle(e)) { auto itr2 = itr.base(); std::advance(itr2,-1); m_elements.splice(m_elements.end(), m_elements, itr2); return true; } }

Hope this helps the next poor soul.

Because partition and swap are not order-preserving for the other elements — kdog
– kdog, Commented Nov 12, 2014 at 11:57

cdhowie · Accepted Answer · 2014-11-12 10:38:54Z

If you want to remove the element and add it to the end (effectively shifting everything else down) then you can do this by using the std::list::splice method, which will relink the node at a new location without requiring any nodes to be created or destroyed. All it will do is tweak the node pointers on existing nodes to reflect the change you want.

for (auto i = m_elements.begin(); i != m_elements.end(); ++i) { if ((*i)->handle()) { // Move this node to the back. m_elements.splice(m_elements.end(), m_elements, i); return true; } } return false;

There are more general solutions that will apply to any container (including std::list) but they may be sub-optimal compared to a technique for that particular container.

Wouldn't it invalidate the collection, and make for-loop to fail?
@Ajay After m_elements.erase(i) the i iterator is indeed invalid, but it doesn't matter because we return immediately afterwards. If we needed to continue iterating through the array then we would have to use the i = m_elements.erase(i) idiom and move ++i into an else block, but since we are not there is no concern.
@Ajay And note my edit -- std::list::splice exists for exactly this reason, and saves a node construction, std::shared_ptr move-construction, and node destruction by adjusting some internal pointers.

Collectives™ on Stack Overflow

How can I move an element from a C++11 container to the back of the container?

EDIT

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

EDIT

1 Answer 1

3 Comments

Related