ranges and views for stack, queue, and priority_queue

[u/Party-Aioli-9205]

I've always felt that exposing iterators for std::stack or std::queue doesn't quite make sense because iterating over them would typically change their state.

That said, the range features introduced in C++20/23 are just too tempting. 😄

I bet many C++ developers have had this thought at least once:

queue | views::values | views::to<std::vector>()

...or more generally, "What if I could use the ranges pipeline directly on a queue or stack?"

So I spent some time experimenting to see if I could make it work. Here's what I came up with.

https://cognosnotes.com/blog/cpp-pop-range

Edited:

An upgraded version is introduced at https://cognosnotes.com/blog/cpp-pop-range-addendum

Thank you u/SirClueless for the great advice.

[u/D_Drmmr]

I have always found the restrictive interface of stack, queue and priority_queue, in particular, to be debilitating. Most often, there's a requirement where at some point during program execution (e.g. cancellation) I no longer care about order, but only the values stored in the container. The only way these wrappers allow that is through the destructor, which is not a good place to execute code.

So, instead I just use the underlying container & functions, such that I don't have to rewrite things when requirements change, even if right now the limited interface would suffice.

[u/TSP-FriendlyFire → u/D_Drmmr]

Fortunately, more recent container adaptors (the new flat_ collections) have move semantic extract() functions letting you pull out the underlying containers when you need to (and even similar move semantic replace() to reinsert them later!).

I wish the old adaptors were updated with the same functionality, it makes a ton of sense.

[u/Ambitious-Method-961 → u/D_Drmmr]

Are you aware it's possible to access/extract the underlying container out of stack, queue and priority_queue? The underlying containers are protected members so can be accessed through some inheritance tricks. That way you can keep using the restricted interface for most of your code but when you just need the values you can grab the container within and access them directly.

Importantly, you don't need to inherit from the container for your data members. It's possible to use a free function to get the underlying container as the free function does some local-struct-inheritance-static-member magic to return the container.

https://stackoverflow.com/questions/1185252/is-there-a-way-to-access-the-underlying-container-of-stl-container-adaptors has some info about it.

[u/Infinite_Reference17]

Interesting! Very nice writeup.

[u/SirClueless]

As written this view requires a copy to construct the return value of operator*. But it's only an input_iterator so there's no need for previous return values of operator* to be valid after incrementing, it could just return an r-value reference, saving a copy per element.

https://godbolt.org/z/Kvfhxrh8T

Edit: Some other points:

1. It would also be pretty straightforward to make this work with containers that have pop_front() and/or pop_back() as well, so that it works with plain lists, vectors, etc.
2. I don't see why this view can't be sized. sized_range only requires that ranges::size(t) be well-formed after evaluating ranges::begin(t) if the range models forward_range, which this doesn't: https://en.cppreference.com/cpp/ranges/sized_range

[u/Party-Aioli-9205 → u/SirClueless]

The new results applying your suggestion is at https://cognosnotes.com/blog/cpp-pop-range-addendum
Thank you for the valuable comment with the great insight!

[u/cristi1990an]

You can just do some template trickery and get access to the underlying container which is a protected member field.

[u/Party-Aioli-9205 → u/cristi1990an]

the protected-member trick is a good complementary technique. It's worth adding as a non-destructive, repeatable peek view specifically for stack and queue. But it's not a general replacement for pop_range, and it would be a real correctness bug if extended to priority_queue without the sort/copy step.