A constexpr function that calculates how deep a std::vector is nested

Question

Is there a way to write a constexpr function that returns how deep a std::vector is nested?

Example:

get_vector_nested_layer_count<std::vector<std::vector<int>>>() // 2
get_vector_nested_layer_count<std::vector<std::vector<std::vector<float>>>>() // 3

康桓瑋 · Accepted Answer · 2022-06-21T13:04:46.053

11

The easy way is to use recursion

#include <vector>

template<class T>
constexpr bool is_stl_vector = false;
template<class T, class Alloc>
constexpr bool is_stl_vector<std::vector<T, Alloc>> = true;

template<class T>
constexpr std::size_t get_vector_nested_layer_count() {
  if constexpr (is_stl_vector<T>)
    return 1 + get_vector_nested_layer_count<typename T::value_type>();
  else
    return 0;
};

Demo

edited Jun 21 '22 at 13:04

answered Jun 21 '22 at 12:58

康桓瑋

33,481
5
40
90

5

Minor quibble: please call it `is_std_vector`, not `is_stl_vector`. After all, its name is `std::vector`. +1. – Pete Becker Jun 21 '22 at 13:12
Why does it still work if I instead write `template constexpr bool is_stl_vector> = true;`? I omitted the `Alloc` template parameter. – palapapa Jun 21 '22 at 13:26
1

@palapapa Try something like [`std::pmr::vector`](https://godbolt.org/z/neTfqWrj1). – 康桓瑋 Jun 21 '22 at 13:33
1

@palapapa Because `std::vector` will supply a default value for its `Alloc` parameter. But in addition to, say, `std::vector`, there could also `std::vector` if we want to have some alternate strategy for how the storage space is used. This is an `std::vector`, but if we don't include `Alloc` as a template parameter for `is_stl_vector` then it will falsely think that it isn't one. – Nathan Pierson Jun 21 '22 at 13:34
@NathanPierson But it still works? How does the compiler know `T` is a `vector` if I don't include `Alloc` in `is_stl_vector`? I thought if I omit `Alloc` then `is_stl_vector` will always be false because there is no `vector` with just one template argument. Is it because the `T` can match against anything? – palapapa Jun 21 '22 at 13:39
1

It supplies the default value `Alloc = std::allocator`. If you just have `std::vector`, that automatically gets expanded to `std::vector>`. – Nathan Pierson Jun 21 '22 at 13:40
@NathanPierson You seemed to have misunderstood me. I was asking why even though there is no `Alloc` template parameter in `is_stl_vector`, when I write `is_stl_vector>` it still returns true? Yes it would get expanded into `is_stl_vector>>`, but why does the compiler think that `std::vector>` is `vector`. What would `T` be? There are two types. – palapapa Jun 21 '22 at 13:49
3

Why would the compiler be unable to figure out that `T` is `int`? – Nathan Pierson Jun 21 '22 at 13:50

dfrib · Answer 2 · 2022-06-22T09:48:52.733

Pre-C++17 (pre constexpr if) you can implement the underlying logic using a trait and specialization

#include <cstddef>
#include <vector>

template <typename> struct vector_nested_layer_count {
  static constexpr std::size_t value{0};
};

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

Or, using std::integral_constant:

#include <cstddef>
#include <type_traits>
#include <vector>

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

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

Apply either of these approaches and add a helper variable template:

template <typename T>
constexpr std::size_t vector_nested_layer_count_v{
    vector_nested_layer_count<T>::value};

static_assert(vector_nested_layer_count_v<int> == 0);
static_assert(vector_nested_layer_count_v<std::vector<std::vector<int>>> == 2);
static_assert(
    vector_nested_layer_count_v<std::vector<std::vector<std::vector<float>>>> ==
    3);

If you're not happy with the idiomatic _v helper variable template (as opposed to a function) you can implement the function as:

template <typename T> constexpr int get_vector_nested_layer_count() {
  return vector_nested_layer_count_v<T>;
}

static_assert(get_vector_nested_layer_count<std::vector<std::vector<int>>>() ==
              2);
static_assert(get_vector_nested_layer_count<
                  std::vector<std::vector<std::vector<float>>>>() == 3);

If you're at C++17 or beyond the constexpr if approach of the other answer is arguably neater, if you really want a function API for this kind of query trait (somewhat atypical in classic meta-programming).

score 4 · Answer 3 · answered Jun 21 '22 at 13:46

you can also directly recurse on the count variable.

template<typename T>
constexpr auto count_nest_vector = 0;

template<typename T>
constexpr auto count_nest_vector<std::vector<T>> = 1+count_nest_vector<T>;

// not really need, but if you want a function.
template<typename T>
constexpr auto get_vector_nested_layer_count() {
    return count_nest_vector<T>;
};

A constexpr function that calculates how deep a std::vector is nested

3 Answers3