CODEWITHSUNDEEP
c++
chromy
chromy

Reputation: 162

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

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:

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?

Upvotes: 0

Views: 125

Answers (1)

SoronelHaetir
SoronelHaetir

Reputation: 15162

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.

Upvotes: 1

Related Questions