Как я могу получить глубину многомерного std :: vector во время компиляции?

45

У меня есть функция, которая принимает многомерный std::vectorи требует, чтобы глубина (или количество измерений) передавалась как параметр шаблона. Вместо жесткого кодирования этого значения я хотел бы написать constexprфункцию, которая будет принимать std::vectorи возвращать глубину как unsigned integerзначение.

Например:

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

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

Это необходимо сделать во время компиляции, потому что эта глубина будет передана функции шаблона в качестве параметра шаблона:

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

Есть какой-либо способ сделать это?

tjwrona1992
источник
4
Размер std::vector- это время выполнения, а не время компиляции. Если вы хотите контейнер размера во время компиляции, посмотрите std::array. Также; помните, что это constexprозначает только то, что « может быть оценено во время компиляции» - нет никаких обещаний, что так и будет . Это может быть оценено во время выполнения.
Джеспер Юль
5
@JesperJuhl, я не ищу размер, я ищу глубину. Две очень разные вещи. Я хочу знать, сколько std::vectors вложено друг в друга. Например, с std::vector<std::vector<int>> v;, GetDepth(v);вернет 2, так как это 2-мерный вектор. Размер не имеет значения.
tjwrona1992
4
Полусвязанный: вложенный vectorне всегда лучший способ сделать что-то. Ручная двумерная или трехмерная индексация одного плоского вектора может быть более эффективной в зависимости от варианта использования. (Просто целочисленная математика вместо погони за указателями с внешних уровней.)
Питер Кордес
1
@PeterCordes Повышение эффективности - это только один аспект. Другой - плоский тип лучше отражает смежный характер массива. Вложенная структура (потенциально различной индивидуальной длины) является принципиально несоответствием типов для представления смежного n-мерного гиперреугольника.
Конрад Рудольф
4
С точки зрения номенклатуры стандартная библиотека использует rankдля этого запроса типы массивов (в соответствии с математической номенклатурой для тензоров). Возможно, это лучшее слово здесь, чем "глубина".
dmckee --- котенок экс-модератора

Ответы:

48

Классическая шаблонная проблема. Вот простое решение, например, как работает стандартная библиотека C ++. Основная идея состоит в том, чтобы иметь рекурсивный шаблон, который будет подсчитывать одно за другим каждое измерение, с базовым регистром 0 для любого типа, который не является вектором.

#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)

Тогда вы можете использовать это так:

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

Редактировать:

Хорошо, я закончил общую реализацию для любого типа контейнера. Обратите внимание, что я определил тип контейнера как что-либо, что имеет правильно сформированный тип итератора согласно выражению, begin(t)где std::beginимпортируется для поиска ADL и tявляется lvalue типа T.

Вот мой код вместе с комментариями, чтобы объяснить, почему все работает, и тестовые примеры, которые я использовал. Обратите внимание, это требует C ++ 17 для компиляции.

#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
}
Круз Жан
источник
Что если я хочу, чтобы это работало для всех вложенных контейнеров, а не только для векторов? Есть ли простой способ сделать это?
tjwrona1992
@ tjwrona1992 Да, вы можете буквально скопировать и вставить std::vector<T>специализацию и изменить ее на другой тип контейнера. Единственное, что вам нужно, это базовый вариант 0 для любого типа, для которого вы не специализируете
Cruz Jean
Я имел в виду без копирования / вставки, ха-ха, Как шаблонов
tjwrona1992
@ tjwrona1992 О, для этого вам нужно использовать функции SFINAE constexpr. Я прототипирую что-то для этого и добавлю как редактирование.
Круз Жан
@ tjwrona1992, как вы определяете контейнер?
Evg
15

Предполагая, что контейнером является любой тип, который имеет value_typeи iteratorтипы элементов (стандартные библиотечные контейнеры удовлетворяют этому требованию) или массив в стиле C, мы можем легко обобщить решение Cruz Jean :

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
}

Типы контейнеров могут быть дополнительно ограничены при необходимости.

Evg
источник
Это не работает для массивов в стиле C
Cruz Jean
1
@CruzJean, конечно. Вот почему я спросил, что такое контейнер. В любом случае, это легко исправить с помощью дополнительной специализации, смотрите обновленный ответ.
Evg
2
@ Evg спасибо. Сегодня я узнал о std :: void_t! Brilliant!
Marco6
2

Вы можете определить следующий шаблон класса, vector_depth<>который соответствует любому типу:

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

Этот основной шаблон соответствует базовому случаю, который завершает рекурсию. Затем определите его соответствующую специализацию для std::vector<T>:

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

Эта специализация соответствует std::vector<T>и соответствует рекурсивному случаю.

Наконец, определите шаблон функции GetDepth(), который обращается к шаблону класса выше:

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

Пример:

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;
}

Выход этой программы:

0 1 2 3
眠 り ネ ロ ク
источник
1
это работает std::vector, но, например, GetDepth(v)где vне intбудет компилироваться. Было бы лучше иметь GetDepth(const volatile T&)и просто вернуться vector_depth<T>::value. volatileпросто позволяет охватить больше вещей, будучи максимально квалифицированным cv
Cruz Jean
@CruzJean Спасибо за предложение. Я отредактировал ответ.
眠 り ネ ロ ク