Recursively generate tuple of all distinct types referenced by a struct

user_626796 0
Viewed 94

I'm specifying a graph of types at compile time with usings and std::tuples like this:

#include<tuple>

struct C;

struct A
{
    using ReferencedTypes = std::tuple<>;
};

struct B
{
    using ReferencedTypes = std::tuple<C>;
};

struct C
{
    using ReferencedTypes = std::tuple<B, A>;
};

struct D
{
    using ReferencedTypes = std::tuple<A, B, C>;
};

struct E
{
    using ReferencedTypes = std::tuple<C, B>;
};

What I would like is a way to recursively get a tuple of all the distinct types referenced by any one of these types (Including the top-level type). The order of the elements of the tuple doesn't matter. Something like:

// DistinctTypes is a std::tuple<E, C, B, A>;
using DistinctTypes = all_types_referenced_in_graph<E>::value;
c++17 tuples metaprogramming c++
1 Answers

My template metaprogramming skills are rusty, but I have something working that will correctly ignore the cycles.

For example, I'm sure a better answer will not force the use of std::tuple_cat and SFINAE.

For the sake of readability, I used requires instead of SFINAE dark arts.

First, let's write a metafunction that will search linearly in a tuple to find if an element is there. If it's there, return true. Otherwise, return false:

// Base case
template<typename Elem, typename Tuple>
struct tuple_contains : std::false_type {};

// Iteration. We extend the type until result. Looks like recursion.
// We drop the first element of the tuple for the next iteration, until none.
template<typename T, typename First, typename... Rest>
struct tuple_contains<T, std::tuple<First, Rest...>> : tuple_contains<T, std::tuple<Rest...>> {};

// Success! T is the same as the first element of the tuple!
template<typename T, typename... Rest>
struct tuple_contains<T, std::tuple<T, Rest...>> : std::true_type {};

Using that, we can make a class that will recursively go into tuples, and append a type into a list only if that element is not in the list:

// We will only use specializations
template<typename TupIn, typename TupOut = std::tuple<>>
struct recursive_append_unique;

// End case. No more types to process.
template<typename... TsOut>
struct recursive_append_unique<std::tuple<>, std::tuple<TsOut...>> {
    using type = std::tuple<TsOut...>;
};

// Here we receive std::tuple<T, TsIn...> where T is already in TsOut.
// In that case, we skip it since it's already processed
template<typename T, typename... TsIn, typename... TsOut>
requires (tuple_contains<T, std::tuple<TsOut...>>::value)
struct recursive_append_unique<std::tuple<T, TsIn...>, std::tuple<Ts...>> {
    using type = recursive_append_unique<std::tuple<TsIn...>, std::tuple<TsOut...>>::type;
};

// Here we have a T that is not in TsOut.
// Here's the core of the algorithm: We add T into TsOut,
// But we also add all types on T::ReferencedTypes into TsIn.
// The next iteration will take care of the first type we added into TsIn.
template<typename T, typename... TsIn, typename... TsOut>
struct recursive_append_unique<std::tuple<T, TsIn...>, std::tuple<TsOut...>> {
    using type = recursive_append_unique<decltype(std::tuple_cat(std::declval<typename T::ReferencedTypes>(), std::declval<std::tuple<TsIn...>>())), std::tuple<TsOut..., T>>::type;
};

Here's a usage of it with your code:

int main() {
    static_assert(std::same_as<recursive_append_unique<std::tuple<E>>::type, std::tuple<E, C, B, A>>);
}

I'm sure this can be done way simpler, but it's been quite a while since I've done anything with template metaprograms.

Live example

The requires clause can be replaced by a dummy third template parameter defaulted to void, combined with std::enable_if_t.

user_21046970
Related