Solution or alternative for recursive view

Question

We want to implement a tree of items:

       +----------------------+
       |   Item (interface)   |
       +----------------------+
       | + getName(): string  |-----------+
       +----------------------+           |
                    ^                     |
                    |                     |
             +------+------+              |
             |             |              |
   +-------------+      +------------+    |
   | SimpleItem  |      |   Group    |<>--+
   +-------------+      +------------+
                        | +add(Item) |
                        | +all()     |
                        +------------+

The Group::all() function shall return a flattened recursive view of all items including self, as pairs of: {recursion level, item}.

An implementation using ranges::views fails, as the return type of all, depends on the level (a view of a view of items is not the same type as a view of items).

So this code doesn't compile:

auto all(size_t level = 0) const {
    return views::concat(
        views::single(std::pair<size_t, std::shared_ptr<const Item>>(level, shared_from_this())), 
        views::join(items | 
            views::transform([level](const auto& item) {
                auto group = std::dynamic_pointer_cast<Group>(item);
                if (group == nullptr) {
                    return views::single(std::pair{level + 1, item});
                }
                else {
                    return group->all(level + 1);
                }
            })
        )
    );
}

Code: https://compiler-explorer.com/z/fdc8rsWae

Any idea how to make the all function work and return the desired flattened view of all recursive items?

_{* Note: the code uses ranges-v3, as we use concat, which is added to std::ranges only in C++26. Solutions may rely either on std::ranges or on ranges-v3.}

How is the collection of child items implemented in Group? (I know I could look at your source code.) I mean, what prevents you from going to the basics and simply iterating this collection recursively? The second question is: how does the object graph of all the Item instances look? It does not have to be a tree. In the case of the general graph, you will have to avoid infinite loops. To do so, you can, for example, create a temporary hash set of the already visited Item nodes. Basically, that's all. Any problem with this? — Sergey A Kryukov
– Sergey A Kryukov, Commented Feb 27 at 0:14
Question why do you use std::shared_ptr<const Item> in your view and not Item&? You're going to build up a view so why pay for the ownership overhead of shared_ptr? — Pepijn Kramer
– Pepijn Kramer, Commented Feb 27 at 4:24
Unrelated: all should be a virtual function in Item. Alternatively, use a std::variant instead of an hierarchy. — n. m. could be an AI
– n. m. could be an AI, Commented Feb 27 at 4:52

Ahmed AEK · Accepted Answer · 2025-02-27 01:20:11Z

4

A function needs to have a single return type, and every time concat is called recursively the type changes, you need to type-erase the result at some point, like the return of the lambda.

one way to type-erase ranges is ranges::any_view.

using erased_view = ranges::any_view<std::pair<size_t, std::shared_ptr<const Item>>,ranges::category::input>;
auto all(size_t level = 0) const {
    return views::concat(
        views::single(std::pair<size_t, std::shared_ptr<const Item>>(level, shared_from_this())), 
        views::join(items | 
            views::transform([level](const auto& item)->erased_view {
                auto group = std::dynamic_pointer_cast<Group>(item);
                if (group == nullptr) {
                    return views::single(std::pair{level + 1, item});
                }
                else {
                    return group->all(level + 1);
                }
            })
        )
    );
}

godbolt demo

edited Feb 27 at 1:20

answered Feb 27 at 0:59

Ahmed AEK

23.2k3 gold badges19 silver badges50 bronze badges

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

1 Comment

Amir Kirsh Feb 27 at 14:55

Shukran Ahmed, that is exactly what I was looking for! Links that might be relevant (documenting it for myself, as well as for anyone who finds this useful): SO discussion on any_view, another relevant SO post on using any_view, a proposal to add any_view to std which does not seem to be progressing for some reason.

康桓瑋 · Accepted Answer · 2025-02-27 02:58:05Z

3

In C++23, you can do this simply via std::generator (instead of depending on concat_view):

using Ret = std::pair<size_t, std::shared_ptr<const Item>>;
auto all(size_t level = 0) const -> std::generator<Ret> {
    co_yield Ret(level, shared_from_this());
    for (auto&& item : items) {
      auto group = std::dynamic_pointer_cast<Group>(item);
      if (group == nullptr)
        co_yield Ret(level + 1, item);
      else
        co_yield std::ranges::elements_of(group->all(level + 1));
    }
}

Demo

answered Feb 27 at 2:58

康桓瑋

46.8k5 gold badges69 silver badges135 bronze badges

3 Comments

Amir Kirsh Feb 27 at 14:57

This is a valid solution which I had in mind, however I was looking for a solution based on views. Got my upvote though ;)

康桓瑋 Feb 27 at 15:20

@AmirKirsh std::generator is a view.

Amir Kirsh Feb 27 at 15:31

Didn't phrase my comment right. Was looking for a solution which is not using coroutines :) It is BTW interesting to benchmark the two solutions.

Collectives™ on Stack Overflow

Solution or alternative for recursive view

2 Answers 2

1 Comment

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related