How does c++17 std::variant determine which type to use?

I am curious how std::variant works.

From what i understand it is “basically” a union with an additional index variable. I am, however, confused how does it determine which type to forward the construction/assignment to efficiently. I have looked at it via godbolt.org and it does seem to be pretty efficient, even when copying from another variant.

I have thought of how i would approach an implementation of a variant-like type, but the only way i thought of is to have some sort of helper functions that would forward constructor/assignemnt/destructor calls to the appropriate type based on an index argument. However that would be pretty inefficient with recurcive calls, wouldnt it?

Another way would be to have a union with fixed types and whenever it would need to use a constructor/destructor etc. a big switch would decide which union member to use depending on the index variable, but that would require a lot of code bloat and would only work for fixed types.

From what i can see on godbolt.org, gcc implementation of variant makes a call to std::__detail::__variant::__gen_vtable_impl, but i have not found any information on what it does.

Also, how does it, for example, determine which variant type to use during construction if both of them are “convertible” from the passed argument type? cppreference says that the type must be convertible, but what if there are several possible variant types that are convertible?

I have tried looking at gcc’s stdlib implementation source but it is quite confusing, so i would appreciate if somebody explained it.

Answer

Another way would be to have a union with fixed types and whenever it would need to use a constructor/destructor etc. a big switch would decide which union member to use depending on the index variable, but that would require a lot of code bloat and would only work for fixed types.

But this (morally) works fine for an arbitrary list of types. A switch with contiguous nonoverlapping cases is logically just indexing into your program’s code. Therefore you can intuitively replace a switch with an array lookup: Extract the cases you’ll switch into as functions, and then switching on the cases means indexing the array and calling into the result.

switch(tag) { // effectively "go to line here + tag", so conceptually a lot like indexing
case 0: ret = ...; break;
case 1: ret = ...; break;
...
}
// <=>
ret_t case0(args_t args) { return ...; }
ret_t case1(args_t args) { return ...; }
...
ret_t (*cases[])(args_t) = {case0, case1, ...};
ret = cases[tag](args); // and now it's literally indexing

But generating a bunch of functions and constructing expressions according to patterns is just what templates do.

template<std::size_t I, typename F, typename... Ts>
decltype(auto) visit_case(F &f, std::variant<Ts...> &v) {
    return f(std::get<I>(v));
}
// visit_case<0, F, T1, T2, ...>(f, v) assumes v is a T1 t1 and calls f(t1);
// visit_case<1, F, T1, T2, ...>(f, v) assumes v is a T2 t2 and calls f(t2);
// etc., so this template is capable of generating all the cases of a function on a variant as separate functions
template<typename F, typename... Ts, std::size_t... Is>
constexpr auto visit_cases_impl(std::index_sequence<Is...>) {
    return std::array{visit_case<Is, F, Ts...>...};
}
template<typename F, typename... Ts>
constexpr inline auto visit_cases =
    visit_cases_impl<F, Ts...>(std::index_sequence_for<Ts...>{});
// visit_cases<F, T1, T2, T3> =
// std::array{visit_case<0, F, T1, T2, T3>, visit_case<1, F, T1, T2, T3>, visit_case<2, F, T1, T2, T3>}

The “vtable” you were coming across was referring to the array of function pointers representing what to do with the possible alternatives. This table is all you need for a rudimentary std::visit:

template<typename F, typename... Ts>
decltype(auto) visit(F f, std::variant<Ts...> &v) {
    return visit_cases<F, Ts...>[v.index()](f, v);
    // <=>
    // switch(v.index()) {
    // case 0: return f(std::get<0>(v));
    // case 1: return f(std::get<1>(v));
    // ...
    // }
}

Now, for implementing std::variant, I think it’s needed to have some super_visit that passes also the variant index as a template parameter to f, but otherwise it should be relatively straightforward. The copy/move constructors/assignments and destructor can all be written as such indexed visits. A complete example.