4 ms·

This is solved by iterators in C++. The idea of an iterators is to generalize the concept of a pointer —- something which refers to a location in your data stru

This is solved by iterators in C++. The idea of an iterators is to generalize the concept of a pointer —- something which refers to a location in your data structure. For example the most basic operations of a pointer are to advance and dereference. std::map is actually implemented as a tree. To iterator its members you can do for (cost auto &pair : map) The only requirement for your custom data structure to work is to implement begin() and end() which return iterators - “pointer like” objects.

rerdavies 1y ago
I'm surprised nobody's brought up C++ generators yet (which avoid potential problems with recursion stack depth). for (const auto&node: await depth_first_tree(node)) And generators have the added advantage that walking trees is just a special case of the more general case of traversing a directed graph of elements, which is equally easy. Are generators not a thing in other languages?
- trealira 1y ago
  I didn't even know C++ had generators, but you're right, generators make functions that walking trees much more obviously correct and convenient to write. The site cppreference has an example of walking trees in C++ using them. https://en.cppreference.com/w/cpp/coroutine/generator https://en.cppreference.com/w/cpp/coroutine/generator But I have a question: why is it that in your example, you write `await` before the generator function, but it's not in the example given on cppreference? Also, did you mean `co_await`?
  - rerdavies 1y ago
    To answer your question: I have used them, but I was too lazy to look up the correct syntax. Yes. It should be co_await. The library I used was layered on top of the C++20 co-routine implementation, not c++23, and used co_await there (but probably should not have). Do NOT use the c++20 co-routine APIs (a half-implemented nightmare of an API, although what is there does miraculously work, contrary to expectations). Probably better to wait for c++23 generators, which are so far available as an experimental feature on GCC 14.0 (which makes the feature unusable in any of my projects). All of which, I guess, answers my question about why nobody has brought up c++ generators yet. C# has nice generators. Sorry I brought it up. :-(
- monkeyelite 1y ago
  > (which avoid potential problems with recursion stack depth). Iterators for trees are not implemented with call stack recursion. > I'm surprised nobody's brought up C++ generators yet You cannot modify, insert, or use standard algorithms with a generator.

rerdavies 1y ago

I'm surprised nobody's brought up C++ generators yet (which avoid potential problems with recursion stack depth). for (const auto&node: await depth_first_tree(node)) And generators have the added advantage that walking trees is just a special case of the more general case of traversing a directed graph of elements, which is equally easy. Are generators not a thing in other languages?

trealira 1y ago
I didn't even know C++ had generators, but you're right, generators make functions that walking trees much more obviously correct and convenient to write. The site cppreference has an example of walking trees in C++ using them. https://en.cppreference.com/w/cpp/coroutine/generator https://en.cppreference.com/w/cpp/coroutine/generator But I have a question: why is it that in your example, you write `await` before the generator function, but it's not in the example given on cppreference? Also, did you mean `co_await`?
- rerdavies 1y ago
  To answer your question: I have used them, but I was too lazy to look up the correct syntax. Yes. It should be co_await. The library I used was layered on top of the C++20 co-routine implementation, not c++23, and used co_await there (but probably should not have). Do NOT use the c++20 co-routine APIs (a half-implemented nightmare of an API, although what is there does miraculously work, contrary to expectations). Probably better to wait for c++23 generators, which are so far available as an experimental feature on GCC 14.0 (which makes the feature unusable in any of my projects). All of which, I guess, answers my question about why nobody has brought up c++ generators yet. C# has nice generators. Sorry I brought it up. :-(
monkeyelite 1y ago
> (which avoid potential problems with recursion stack depth). Iterators for trees are not implemented with call stack recursion. > I'm surprised nobody's brought up C++ generators yet You cannot modify, insert, or use standard algorithms with a generator.