How to define a variant<x,y,z> extracting subtypes of a template parameter

Question

I am building a state-machine where state transitions are described as a variant, i.e.:

using table = std::variant<
/*             state        event               followup-state    */
    transition<start,       success<sock>,      connecting>,
    transition<start,       exception,          failed>,
    transition<connecting,  success<>,          connected>,
    transition<connecting,  exception,          failed>,
    transition<connected,   exception,          failed>
    >;

and transition being a simple type:

template <typename ENTRY_STATE, typename EVENT, typename NEXT_STATE>
struct transition {
    using entry_state = ENTRY_STATE;
    using event = EVENT;
    using next_state = NEXT_STATE;
};

The state classes are non-polymorphic (and shall not be). My question now is how to define another variant that is able to store all possible states found in the table type (best without duplicates). The type is needed to store the actual state in a type-safe and non-polymorphic way.

From the above table, we have a unique set of entry states:

entry_states = <start,connecting,connected>

and a set of follow-up states:

followup_states = <connecting, connected, failed>

so the resulting variant definition shall be a:

using states = std::variant<entry_states JOINT followup_states>;

=>  using states = std::variant<start,connecting,connected, failed>

I know how to extract type information from the table and access type information of a particular transition, but have no idea how to transfer possible states into a variant definition (without duplicate types).

Any idea is appreciated. However, polymorphism is not a valid solution. Also saving the current state inside a lambda is not an option.

Thanks and best!

PS: the state-machine signature looks like that (I am not posting the full code since it is not meaningful for the question, imo):

template <typename TransitionTable, typename Context>
class state_machine {
public:
    template <typename State, typename Event>
    auto push(State & state, Event & event) {
    ...
    }
protected:
    *using states = std::variant<???>;*
    states current_state;
};

Answer 1

There are two separate tasks:

1. Extracting the states from the transition-table. This is easily done with pattern-matching.
2. Removing duplicates. This can be done with O(log n) depth, the complexity comes from std::tuple_cat which uses std::index_sequence, and additionally directly from the latter.

Code for merging type-lists thrown in as a bonus:

#include <tuple>
#include <utility>
#include <type_traits>

namespace detail {
    template <template <class...> class TT, template <class...> class UU, class... Us>
    auto pack(UU<Us...>)
    -> std::tuple<TT<Us>...>;

    template <template <class...> class TT, class... Ts>
    auto unpack(std::tuple<TT<Ts>...>)
    -> TT<Ts...>;

    template <std::size_t N, class T>
    using TET = std::tuple_element_t<N, T>;

    template <std::size_t N, class T, std::size_t... Is>
    auto remove_duplicates_pack_first(T, std::index_sequence<Is...>)
    -> std::conditional_t<(... || (N > Is && std::is_same_v<TET<N, T>, TET<Is, T>>)), std::tuple<>, std::tuple<TET<N, T>>>;

    template <template <class...> class TT, class... Ts, std::size_t... Is>
    auto remove_duplicates(std::tuple<TT<Ts>...> t, std::index_sequence<Is...> is)
    -> decltype(std::tuple_cat(remove_duplicates_pack_first<Is>(t, is)...));

    template <template <class...> class TT, class... Ts>
    auto remove_duplicates(TT<Ts...> t)
    -> decltype(unpack<TT>(remove_duplicates<TT>(pack<TT>(t), std::make_index_sequence<sizeof...(Ts)>())));
}

template <template <class...> class TT, class... Ts>
using merge_t = decltype(detail::unpack<TT>(std::tuple_cat(detail::pack<TT>(std::declval<Ts>())...)));

template <class T>
using remove_duplicates_t = decltype(detail::remove_duplicates(std::declval<T>()));

Applying it to your transitions-table:

template <template <class...> class TT, class ... Ts>
auto extract_states(TT<Ts...>)
-> TT<typename Ts::entry_state..., typename Ts::next_state...>;

using extracted = decltype(extract_states(std::declval<table>()));
using states = remove_duplicates_t<extracted>;

See it live on coliru.