How can I get the depth of a multidimensional std::vector at compile time?

Question

I have a function that takes a multidimensional std::vector and requires the depth (or the number of dimensions) to be passed in as a template parameter. Instead of hardcoding this value I would like to write a constexpr function that will take the std::vector and return the depth as an unsigned integer value.

For example:

std::vector<std::vector<std::vector<int>>> v =
{
    { { 0, 1}, { 2, 3 } },
    { { 4, 5}, { 6, 7 } },
};

// Returns 3
size_t depth = GetDepth(v);

This needs to be done at compile time though because this depth will be passed to the template function as a template parameter:

// Same as calling foo<3>(v);
foo<GetDepth(v)>(v);

Is there any way to do this?

Jeffreys

The size of a std::vector is a run-time thing, not a compile-time one. If you want a compile-time size container, look to std::array. Also; remember that constexpr only means "may be evaluated at compile time" - there's no promise that it will be. It may be evaluated at run-time. – Howdoyoudo

@JesperJuhl, I'm not looking for size, I'm looking for depth. Two very different things. I want to know how many std::vectors are nested within each other. For example with std::vector<std::vector<int>> v;, GetDepth(v); would return 2 since it is a 2 dimensional vector. The size is irrelevant. – Jeffreys

Semi-related: nested vector isn't always the best way to do things. Manual 2d or 3d indexing of a single flat vector can be more efficient, depending on the use-case. (Just integer math instead of pointer-chasing from the outer levels.) – Snowmobile

@PeterCordes Better efficiency is just one facet. Another one is that a flat type better represents the contiguous nature of the array. A nested structure (of potentially differing individual lengths) is fundamentally a type mismatch for representing a contiguous, n-dimensional hyperrectangle. – Torrance

@KonradRudolph: agreed; there are use-cases for nested std::vector, but an always-rectangular array isn't one of them. (Especially if it doesn't need to be resizable in any dimension, but even then it's not great.) Use-cases do include a sparse or ragged array. – Snowmobile

Nomenclature-wise the standard library uses rank for this query on array types (in agreement with the mathematical nomenclature for tensors). Perhaps that is a better word here than "depth". – Gnaw

Also @JesperJuhl, if you use a constexpr as part of a template argument then by definition it MUST be evaluated at compile time otherwise the template as a whole will fail to compile. Whether a constexpr will be evaluated at compile time or runtime is not as unpredictable as your comment makes it seem. – Jeffreys

Answer 1

A classic templating problem. Here's a simple solution like how the C++ standard library does. The basic idea is to have a recursive template that will count one by one each dimension, with a base case of 0 for any type that is not a vector.

#include <vector>
#include <type_traits>

template<typename T>
struct dimensions : std::integral_constant<std::size_t, 0> {};

template<typename T>
struct dimensions<std::vector<T>> : std::integral_constant<std::size_t, 1 + dimensions<T>::value> {};

template<typename T>
inline constexpr std::size_t dimensions_v = dimensions<T>::value; // (C++17)

So then you could use it like so:

dimensions<vector<vector<vector<int>>>>::value; // 3
// OR
dimensions_v<vector<vector<vector<int>>>>; // also 3 (C++17)

Edit:

Ok, I've finished the general implementation for any container type. Note that I defined a container type as anything that has a well-formed iterator type as per the expression begin(t) where std::begin is imported for ADL lookup and t is an lvalue of type T.

Here's my code along with comments to explain why stuff works and the test cases I used. Note, this requires C++17 to compile.

#include <iostream>
#include <vector>
#include <array>
#include <type_traits>

using std::begin; // import std::begin for handling C-style array with the same ADL idiom as the other types

// decide whether T is a container type - i define this as anything that has a well formed begin iterator type.
// we return true/false to determing if T is a container type.
// we use the type conversion ability of nullptr to std::nullptr_t or void* (prefers std::nullptr_t overload if it exists).
// use SFINAE to conditionally enable the std::nullptr_t overload.
// these types might not have a default constructor, so return a pointer to it.
// base case returns void* which we decay to void to represent not a container.
template<typename T>
void *_iter_elem(void*) { return nullptr; }
template<typename T>
typename std::iterator_traits<decltype(begin(*(T*)nullptr))>::value_type *_iter_elem(std::nullptr_t) { return nullptr; }

// this is just a convenience wrapper to make the above user friendly
template<typename T>
struct container_stuff
{
    typedef std::remove_pointer_t<decltype(_iter_elem<T>(nullptr))> elem_t;    // the element type if T is a container, otherwise void
    static inline constexpr bool is_container = !std::is_same_v<elem_t, void>; // true iff T is a container
};

// and our old dimension counting logic (now uses std:nullptr_t SFINAE logic)
template<typename T>
constexpr std::size_t _dimensions(void*) { return 0; }

template<typename T, std::enable_if_t<container_stuff<T>::is_container, int> = 0>
constexpr std::size_t _dimensions(std::nullptr_t) { return 1 + _dimensions<typename container_stuff<T>::elem_t>(nullptr); }

// and our nice little alias
template<typename T>
inline constexpr std::size_t dimensions_v = _dimensions<T>(nullptr);

int main()
{
    std::cout << container_stuff<int>::is_container << '\n';                 // false
    std::cout << container_stuff<int[6]>::is_container<< '\n';               // true
    std::cout << container_stuff<std::vector<int>>::is_container << '\n';    // true
    std::cout << container_stuff<std::array<int, 3>>::is_container << '\n';  // true
    std::cout << dimensions_v<std::vector<std::array<std::vector<int>, 2>>>; // 3
}

Brandenbrandenburg

What if I want this to work for all nested containers and not just vectors? Is there an easy way to make that happen? – Jeffreys

@tjwrona1992 Ya, you could literally just copy and paste the std::vector<T> specialization and change it to some other container type. The only thing you need is the 0 base case for any type you don't specialize for – Brandenbrandenburg

I meant without copy/paste haha, Like templating the template – Jeffreys

@tjwrona1992 Oh, for that you would need to use SFINAE constexpr functions. I'll prototype a thing for that and add it as an edit. – Brandenbrandenburg

@tjwrona1992, what is your definition of a container? – Stoltzfus

@Stoltzfus I would define "container" as any class that has the same behavior/interface as the standard STL container classes. – Jeffreys

@tjwrona1992 Tis' added. Is that more what you were looking for? – Brandenbrandenburg

Yeah, all I need for my specific use case is vector, but having a generic solution readily available is always a plus. :) – Jeffreys

It will match std::string as a container too. It happend to me couple of times with templates – Conceal

Is there a way to use above defined dimensions with a named variable rather than with type of variable as the OP originally asked? – Gorges

@Gorges I think you're looking for decltype – Forehanded

@Gorges In addition to using decltype you could write a constexpr template function that simply returns dimensions_v of the type of the argument to get the exact syntax the OP desired. (I'm not sure that would be good practice though; it's sort of likely confuse people, since it's a function that doesn't actually look at its argument) – Camfort

Answer 2

Assuming that a container is any type that has value_type and iterator member types (standard library containers satisfy this requirement) or a C-style array, we can easily generalize Cruz Jean's solution:

template<class T, typename = void>
struct rank : std::integral_constant<std::size_t, 0> {};

// C-style arrays
template<class T>
struct rank<T[], void> 
    : std::integral_constant<std::size_t, 1 + rank<T>::value> {};

template<class T, std::size_t n>
struct rank<T[n], void> 
    : std::integral_constant<std::size_t, 1 + rank<T>::value> {};

// Standard containers
template<class T>
struct rank<T, std::void_t<typename T::iterator, typename T::value_type>> 
    : std::integral_constant<std::size_t, 1 + rank<typename T::value_type>::value> {};

int main() {
    using T1 = std::list<std::set<std::array<std::vector<int>, 4>>>;
    using T2 = std::list<std::set<std::vector<int>[4]>>;

    std::cout << rank<T1>();  // Output : 4
    std::cout << rank<T2>();  // Output : 4
}

Container types can be further restricted if needed.

Stoltzfus

@CruzJean, sure. That's why I asked what a container is. Anyway, it can easily be fixed with an additional specialization, see the updated answer. – Stoltzfus

@Stoltzfus thank you. Today I learned about std::void_t! Brilliant! – Mahout

Answer 3

You can define the following class template vector_depth<> which matches any type:

template<typename T>
struct vector_depth {
   static constexpr size_t value = 0;
};

This primary template corresponds to the base case that ends the recursion. Then, define its corresponding specialization for std::vector<T>:

template<typename T>
struct vector_depth<std::vector<T>> {
   static constexpr size_t value = 1 + vector_depth<T>::value;
};

This specialization matches an std::vector<T> and corresponds to the recursive case.

Finally, define the function template, GetDepth(), that resorts to the class template above:

template<typename T>
constexpr auto GetDepth(T&&) {
   return vector_depth<std::remove_cv_t<std::remove_reference_t<T>>>::value;
}

Example:

auto main() -> int {
   int a{}; // zero depth
   std::vector<int> b;
   std::vector<std::vector<int>> c;
   std::vector<std::vector<std::vector<int>>> d;

   // constexpr - dimension determinted at compile time
   constexpr auto depth_a = GetDepth(a);
   constexpr auto depth_b = GetDepth(b);
   constexpr auto depth_c = GetDepth(c);
   constexpr auto depth_d = GetDepth(d);

   std::cout << depth_a << ' ' << depth_b << ' ' << depth_c << ' ' << depth_d;
}

The output of this program is:

0 1 2 3

Illampu

this works for std::vector, but e.g. GetDepth(v) where v is int won't compile. Would be better to have GetDepth(const volatile T&) and just return vector_depth<T>::value. volatile just lets it cover more stuff, being maximum cv qualified – Brandenbrandenburg

@CruzJean Thanks for the suggestion. I've edited the answer. – Bermuda