Date: Sat, 22 Feb 2025 20:24:56 +0200
This could be occasionally nice to have, especially if it worked with
other adaptors as well. Some random examples:
Finding the area of the largest rectangle under a histogram [1] can be
solved with a monotonic stack. Before pushing a new element, the
discarded elements could be processed as a range:
template <stdr::input_range R>
auto max_rect_area (R&& r) {
using idx_t = stdr::range_difference_t<R>;
using height_t = stdr::range_value_t<R>;
using area_t = decltype (idx_t () * height_t ());
struct bar {
idx_t idx;
height_t height;
};
std::stack<bar> stk;
area_t result {};
for (auto [idx, height] : stdv::concat (r, stdv::single (0)) |
stdv::enumerate)
{
std::tie (idx, result) = stdr::fold_left (
pop_off (stk) | // <-- popping adaptor
stdv::take_while ([=] (bar b) {
return b.height >= height;
}),
std::pair (idx, result),
[=] (auto p, bar b) {
return std::pair (
b.idx,
std::max (p.second, (idx - b.idx) * b.height)
);
}
);
stk.emplace (idx, height);
}
return result;
}
Finding minimal paths in a graph using BFS:
std::queue<...> q;
q.push (seed);
for (std::size_t path_length = 0; ! q.empty (); ++path_length) {
/* all current elements in the queue are path_length away
* from seed
*/
for (auto& node : pop_off (q) | stdv::take (q.size ())) {
// process node, possibly pushing new elements
}
}
Using priority_queue as a lazily-sorted range:
template <stdr::input_range R1, stdr::input_range R2>
bool is_permutation (R1&& r1, R2&& r2) {
return stdr::equal (
pop_off (
stdr::to<std::priority_queue> (std::forward<R1> (r1))
),
pop_off (
stdr::to<std::priority_queue> (std::forward<R2> (r2))
)
);
}
[1] https://leetcode.com/problems/largest-rectangle-in-histogram/
other adaptors as well. Some random examples:
Finding the area of the largest rectangle under a histogram [1] can be
solved with a monotonic stack. Before pushing a new element, the
discarded elements could be processed as a range:
template <stdr::input_range R>
auto max_rect_area (R&& r) {
using idx_t = stdr::range_difference_t<R>;
using height_t = stdr::range_value_t<R>;
using area_t = decltype (idx_t () * height_t ());
struct bar {
idx_t idx;
height_t height;
};
std::stack<bar> stk;
area_t result {};
for (auto [idx, height] : stdv::concat (r, stdv::single (0)) |
stdv::enumerate)
{
std::tie (idx, result) = stdr::fold_left (
pop_off (stk) | // <-- popping adaptor
stdv::take_while ([=] (bar b) {
return b.height >= height;
}),
std::pair (idx, result),
[=] (auto p, bar b) {
return std::pair (
b.idx,
std::max (p.second, (idx - b.idx) * b.height)
);
}
);
stk.emplace (idx, height);
}
return result;
}
Finding minimal paths in a graph using BFS:
std::queue<...> q;
q.push (seed);
for (std::size_t path_length = 0; ! q.empty (); ++path_length) {
/* all current elements in the queue are path_length away
* from seed
*/
for (auto& node : pop_off (q) | stdv::take (q.size ())) {
// process node, possibly pushing new elements
}
}
Using priority_queue as a lazily-sorted range:
template <stdr::input_range R1, stdr::input_range R2>
bool is_permutation (R1&& r1, R2&& r2) {
return stdr::equal (
pop_off (
stdr::to<std::priority_queue> (std::forward<R1> (r1))
),
pop_off (
stdr::to<std::priority_queue> (std::forward<R2> (r2))
)
);
}
[1] https://leetcode.com/problems/largest-rectangle-in-histogram/
Received on 2025-02-22 18:25:04