Can a C++ intrusive linked list work with std::queue?

Question

Recently I was trying to make an intrusive list (like boost's or elt's) work with std::queue.

std:queue<T> has two options for push which end up calling though to push_back on the underlying list impl:

void push( const value_type& value );
void push( value_type&& value );

Neither of these make much sense for intrusive lists of T. We have to modify T too insert it so the const would be a lie and we definitely don't want to move it into list since the whole point of an intrusive list is that it doesn't own the elements. Reasonably then the intrusive lists I've seen only implement void push_back(value_type& value);.

I realise std::queue doesn't buy me anything I couldn't do with manual application of push_back/pop_front ...but at this point I'm morbidly curious if it's possible. Is there some C++ magic I'm missing?

Somehow related: stackoverflow.com/questions/10455550/queuestring-errors — Bob__
– Bob__, Commented Dec 22, 2021 at 22:57

SoronelHaetir · Accepted Answer · 2021-12-22 23:12:15Z

1

It would not be possible to do this if you want the original list object to remain valid after being added to the queue but if you dispense with that requirement then the move version of push() becomes usable with an intrusive list.

It would require creating a new intrusive list object (this would be managed by std::queue), assigning the current list's head and tail to the new list's head and tail and also fixing up the head's tail and tail's head to point to the new list and then clearing the old list's head and tail (these operations would all be handled by the list's move constructor, maybe move-assign).

The thing to keep in mind is that C++ standard containers always take copies of whatever is added. Copying an intrusive container likely never makes sense but moving one can.

answered Dec 22, 2021 at 23:12

SoronelHaetir

15.6k1 gold badge18 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Can a C++ intrusive linked list work with std::queue?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related