C++ Logo

std-proposals

Advanced search

Re: [std-proposals] An input iterator for std::stack

From: Ell <ell_se_at_[hidden]>
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/

Received on 2025-02-22 18:25:04