How can I deduce the inner type of a nested std::vector at compile time?

Question

The other day I asked a very similar question about nested vectors, but I've come across another problem that has me stumped. I need to get the innermost type of a nested vector at compile time so I can use it to pass as a template argument.

For example if I have this nested vector:

std::vector<std::vector<std::vector<int>>> v;

I need a way to extract int so I can call a function that takes a nested vector and works on the elements like this:

foo<int>(v);

Except the catch is this function should be able to work on nested vectors of any depth that hold any type. And when I call foo I want the inner type to be automatically deduced for me.

So maybe the call would look something like this:

foo<inner_type_t<v>>(v);

Where inner_type_t is some form of recursive template that resolves to int when given v.

I assume the solution will be similar to that of the other question but I haven't been able to work it out... I'm still a bit of a novice when it comes to recursive templates.

Edit:

Here is what I have so far...

template <typename T>
struct inner_type
{
    using type = T;
};

template <typename T>
struct inner_type<std::vector<T>>
{
    using type = inner_type<T>;
};

int main()
{
    std::vector<std::vector<int>> v  = {
        { 1, 2}, {3, 4}
    };

    std::cout << typeid(inner_type<decltype(v)>::type).name();
}

output:

struct inner_type<class std::vector<int,class std::allocator<int> > >

Crosscheck

What have you tried so far? Most whatever_t types are created by making a struct whatever with a member type, and then template <typename T> using whatever_t = typename whatever<T>::type;. – Eec

I added to the question with my attempt at the problem. – Crosscheck

Another option would be to follow vector's value_type, and stopping if there is no value_type. – Jinni

Answer 1

@tjwrona1992's solution is ok, but doesn't allow for vectors with different allocators. Also, let's make this C++14-friendly with an _t version of the trait.

This should do the trick:

template <typename T> struct inner_type { using type = T; };

template<class T, class Alloc>
struct inner_type<std::vector<T, Alloc>> { using type = typename inner_type<T>::type; };

template<class T>
using inner_type_t = typename inner_type<T>::type;

Also, for the type name, you should using the type_name() function implemented here for C++14 or here for C++17.

See it working live...

Rauch

Answer 2

Wow I was really close haha, got it to work!

I just had to change the template specialization slightly to properly get the type recursively.

template <typename T>
struct inner_type
{
    using type = T;
};

template <typename T>
struct inner_type<std::vector<T>>
{
    // Had to change this line
    using type = typename inner_type<T>::type;
};

int main()
{
    std::vector<std::vector<int>> v  = {
        { 1, 2}, {3, 4}
    };

    std::cout << typeid(inner_type<decltype(v)>::type).name();
}

Output:

int

Crosscheck

Answer 3

A solution that follows the Bulletmagnet's suggestion to use value_type member type:

template<class T, typename = void>
struct inner_type {
    using type = T;
};

template<class T>
struct inner_type<T, std::void_t<typename T::value_type>>
    : inner_type<typename T::value_type> {};

template<class T>
using inner_type_t = typename inner_type<T>::type;

using VV = std::vector<std::vector<int>>;
static_assert(std::is_same_v<inner_type_t<VV>, int>);

A very good explanation of how std::void_t works, can be found in this question. It is used here to silently reject the specialization if typename T::value_type is ill-formed.

Solemnity

Can you explain how the std::void_t piece works? I can follow it except for that lol – Crosscheck

@tjwrona1992, see this question for a very good explanation. std::void_t<typename T::value_type> makes the specialization ill-formed. It is then silently rejected thanks to SFINAE. – Solemnity

Answer 4

You can define the following primary class template, inner_type:

template<typename T>
struct inner_type {
   using type = T;
};

which is used as the base case, i.e., for stopping the recursion – when the template argument doesn't match std::vector<T> (see below).

Then, the following convenience alias template just for writing C++14-like trailing _t instead of ::type:

template<typename T>
using inner_type_t = typename inner_type<T>::type;

Finally, the specialization for std::vector<T> – the recursive case:

template<typename T>
struct inner_type<std::vector<T>> {
   using type = inner_type_t<T>;
};

This specialization is matched when passing an std::vector<T> as the template argument. Otherwise, the first one (see above) will be matched.

---

To check it. You can declare the following class template:

template<typename> struct type_shower;

Then:

auto main() -> int {
   using type = inner_type_t<std::vector<std::vector<int>>>;
   type_shower<type> _;
}

It should display an error saying that implicit instantiation of undefined template type_shower<int>. This implies that type is int.

Resume

That looks like an interesting trick, but when I tried it I get a different error instead of revealing the type :( error C2079: '_' uses undefined struct 'type_shower<type>'. Could be because I'm using a different compiler. – Crosscheck

@tjwrona1992 I see. What if you write std::vector<std::vector<int>> directly as a template argument of type_shower<> ??? – Resume

Yeah that spits out a type but it's ugly lol error C2079: '_' uses undefined struct 'type_shower<std::vector<std::vector<int,std::allocator<_Ty>>,std::allocator<std::vector<_Ty,std::allocator<_Ty>>>>>' – Crosscheck

Answer 5

With Boost.Mp11, this is a short one-liner (as always)

template <typename T>
using inner_value_t = mp_last<mp_iterate<T, mp_identity_t, mp_first>>;

Demo.

This is relying on the fact that you only care about vector, and the value type of vector<T, A> is just T. Which is actually true for all the sequence containers (this will work for list, deque, forward_list, etc, just fine. Although for vector<map<int, double>> it'll give you int).

If we had vector<vector<char>>, mp_iterate would first produce the sequence mp_list<vector<vector<char>>, vector<char>, char> (applying mp_first until we cannot anymore, and passing the result into mp_identity_t which is just a no-op). And then mp_last returns the last type in that list. Which is the type we want: char.

---

If you want to broaden to support arbitrary ranges, you can instead use std::ranges::range_value_t (C++20) instead of mp_first, which is the most generic solution.

Or, if you just care about the nested value_type alias:

template <typename T> using value_type_t = typename T::value_type;

template <typename T>
using inner_value_t = mp_last<mp_iterate<T, mp_identity_t, value_type_t>>;

Segno

Answer 6

Here's a more general solution. It works for list and forward_list too, not just vector.

#include <vector>
#include <list>
#include <forward_list>
#include <type_traits>

//using nested = std::vector<std::vector<std::vector<int>>>;
using nested = std::list<std::vector<std::forward_list<double>>>;

// primary template handles types that have no nested value_type member:
template< class, class = std::void_t<> >
struct has_vt : std::false_type { };

// specialization recognizes types that do have a nested value_type member:
template< class T >
struct has_vt<T, std::void_t<typename T::value_type>> : std::true_type { };

template <typename T, typename Enable = void> struct inner;

template <typename T> struct inner<T, typename std::enable_if<!has_vt<T>::value>::type> {
    using vt = T;
};

template <typename T> struct inner<T, typename std::enable_if<has_vt<T>::value>::type> {
    using vt = typename inner<typename T::value_type>::vt;
};

template<typename> struct type_shower;

int main() {
    using deeep = inner<nested>::vt;
    type_shower<deeep> _;
    return 0;
}

Jinni