Filtering nested dynamic tuple (dynamic tuple of tuples)

Question

I have a sort of dynamic tuple structure:

template <typename... Elems> //Should only be tuples
class DynamicTuple {
    vector<byte> data; //All data is stored contiguously
    vector<tuple<size_t,size_t>> element_table; //First element is offset into the data vector; second is which index of the parameter pack holds the stored type.
    /* ... */ 
}

Now I want to be able to filter out all tuples that contain a list of types.

template <typename... Ts>
vector<tuple<Ts&...>> filter() {
    vector<tuple<Ts&...>> result;
    for (auto it : element_table) {
        auto [offset, type] = it;
        // ???
    }
}

Here I need to be able to check if the type in the Nth index of the "Elems" parameter pack is a tuple that contains all the types in the "Ts" parameter pack. If it does, I want to push back a tuple containing those values.

Intuitively I want to use the "type" value to get the type from the "Elems" parameter pack, and use a has_type structure like the one from this answer: https://stackoverflow.com/a/41171291/11463887 Something like:

((has_type<Ts, tuple_element<type, tuple<Elems...>>::type>&& ...))

However this doesn't work, since "type" is not a compile-time constant expression. Is there a way to get around this?

@walnut That would stop it from being dynamic. I understand this is why my way, using tuple_element can't work―what I'm asking for is a way to do this at runtime. — meatandmahjong, Dec 16 '19 at 08:14
@walnut I mean dynamic in the same way an std::vector is dynamic while an std::array isn't. I store various types at runtime in the data vector and need the element_table to look up the types stored in it. If I push back a float in the data vector, I need to also push back { data.end(0), Index::value } (taken from https://stackoverflow.com/a/26169248/11463887), so the element_table stores has one element per tuple the DynamicTuple is holding. — meatandmahjong, Dec 16 '19 at 08:37

walnut · Accepted Answer · 2019-12-16T11:40:38.467

With the has_type that you already have, you can in the same manner define a type_subset testing whether all types are contained in the tuple:

template <typename Ts, typename Tuple>
struct type_subset;

template <typename... Ts, typename... Us>
struct type_subset<std::tuple<Ts...>, std::tuple<Us...>>
    : std::conjunction<has_type<Ts, std::tuple<Us...>>...> {};

and then you probably want to find the correct type matching your type index by iterating over the parameter pack and the corresponding indices:

size_t i = 0;
bool match = ((type == i++ && type_subset<std::tuple<Ts...>, Elems>::value) || ...);

Make sure to reset i to 0 before each execution of the fold expression. You might want to put the whole thing in a lambda or function to separate the i and to reuse this with other conditions.

Maybe better performing is to save the possible results to an array at compile-time, and then index into it at runtime:

constexpr static std::array matches{type_subset<std::tuple<Ts...>, Elems>::value...};
bool match = matches[type];

In either case you need to make sure that type < sizeof...(Elems). In the second variant especially you will have undefined behavior otherwise (if you don't use .at instead of []).

This is perfectly what I wanted, but now that I'm trying to implement it, specifically using the constexpr version, I'm having difficulty getting it to work. Matches' length is always 1. Maybe this is because I wrapped `type_subset, Elems>::value, ...` in parenthesis, but otherwise it wouldn't compile. — meatandmahjong, Dec 16 '19 at 10:47
@meatandmahjong Sorry, I used wrong syntax. The comma shouldn't have been there and a semicolon was missing, see updated question. If you enclose it in parentheses it will have a different meaning (fold-expression with the comma operator). — walnut, Dec 16 '19 at 11:42

darune · Answer 2 · 2019-12-16T08:58:57.340

1

However this doesn't work, since "type" is not a compile-time constant expression. Is there a way to get around this?

It's not possible to return a different type based on a runtime value.

You either have to resort to something that can be evaluated at runtime (eg. use a vector) OR have the input be compile time constant.

A runtime solution could use type_id or similiar.

edited Dec 16 '19 at 08:58

answered Dec 16 '19 at 08:35

darune

10,480
2
24
62

"type" is the size_t value from the element_table. I don't neccessarily have to return a different type based on the value. I could for instance make it so it returns a vector> and return a nullptr when a tuple doesn't contain the type. The main issue though, is how to figure out how the each tuple from the Elems parameter pack contains each type from the Ts parameter pack – meatandmahjong Dec 16 '19 at 08:59

Filtering nested dynamic tuple (dynamic tuple of tuples)

2 Answers2