Jak uzyskać głębokość wielowymiarowego std :: vector w czasie kompilacji?

45

Mam funkcję, która przyjmuje wielowymiarowość std::vectori wymaga podania głębokości (lub liczby wymiarów) jako parametru szablonu. Zamiast na stałe wpisywać tę wartość, chciałbym napisać constexprfunkcję, która pobierze std::vectori zwróci głębokość jako unsigned integerwartość.

Na przykład:

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

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

Należy to zrobić w czasie kompilacji, ponieważ ta głębokość zostanie przekazana do funkcji szablonu jako parametr szablonu:

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

Czy jest na to sposób?

tjwrona1992
źródło
4
Rozmiar a std::vectorjest kwestią czasu wykonywania, a nie kompilacji. Jeśli potrzebujesz kontenera w czasie kompilacji, spójrz na std::array. Również; pamiętaj, że constexproznacza to tylko „ można ocenić w czasie kompilacji” - nie ma obietnicy, że tak będzie . Można to ocenić w czasie wykonywania.
Jesper Juhl,
5
@JesperJuhl, nie szukam rozmiaru, szukam głębi. Dwie bardzo różne rzeczy. Chcę wiedzieć, ile std::vectors są w sobie zagnieżdżone. Na przykład std::vector<std::vector<int>> v;, GetDepth(v);zwróci 2, ponieważ jest to wektor dwuwymiarowy. Rozmiar nie ma znaczenia.
tjwrona1992
4
Częściowo powiązane: zagnieżdżanie vectornie zawsze jest najlepszym sposobem na robienie rzeczy. Ręczne indeksowanie 2d lub 3d pojedynczego płaskiego wektora może być bardziej wydajne, w zależności od przypadku użycia. (Tylko matematyka całkowita zamiast gonić za wskazówkami z zewnętrznych poziomów.)
Peter Cordes
1
@PeterCordes Lepsza wydajność to tylko jeden aspekt. Innym jest to, że typ płaski lepiej reprezentuje przylegający charakter tablicy. Struktura zagnieżdżona (o potencjalnie różnych długościach indywidualnych) jest zasadniczo niedopasowaniem typu do reprezentowania ciągłego, n-wymiarowego hiperprostokąta.
Konrad Rudolph
4
Pod względem nomenklatury biblioteka standardowa używa ranktego zapytania do typów tablic (zgodnie z nomenklaturą matematyczną dla tensorów). Być może jest to lepsze słowo niż „głębia”.
dmckee --- były moderator kociak

Odpowiedzi:

48

Klasyczny problem szablonów. Oto proste rozwiązanie, takie jak standardowa biblioteka C ++. Podstawową ideą jest posiadanie szablonu rekurencyjnego, który będzie zliczał jeden po drugim dla każdego wymiaru, z podstawowym przypadkiem 0 dla każdego typu, który nie jest wektorem.

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

Więc możesz użyć go w następujący sposób:

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

Edytować:

Ok, zakończyłem ogólną implementację dowolnego typu kontenera. Zauważ, że zdefiniowałem typ kontenera jako dowolny element, który ma dobrze uformowany typ iteratora zgodnie z wyrażeniem, w begin(t)którym std::beginjest importowany do wyszukiwania ADL i tjest wartością typu T.

Oto mój kod wraz z komentarzami wyjaśniającymi, dlaczego działają rzeczy i przypadki testowe, których użyłem. Uwaga, wymaga to kompilacji 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
}
Cruz Jean
źródło
Co jeśli chcę, aby działało to dla wszystkich zagnieżdżonych kontenerów, a nie tylko wektorów? Czy jest na to łatwy sposób?
tjwrona1992
@ tjwrona1992 Tak, możesz dosłownie po prostu skopiować i wkleić std::vector<T>specjalizację i zmienić ją na inny typ kontenera. Jedyne, czego potrzebujesz, to skrzynka podstawowa 0 dla każdego typu, dla którego się nie specjalizujesz
Cruz Jean
Miałem na myśli bez kopiowania / wklejania haha, Like templating the template
tjwrona1992
@ tjwrona1992 Och, do tego musisz użyć funkcji SFINAE constexpr. Zrobię to prototypem i dodam jako edycję.
Cruz Jean
@ tjwrona1992, jaka jest twoja definicja kontenera?
Evg
15

Zakładając, że kontener jest dowolnego typu value_typei ma iteratortypy elementów (standardowe kontenery biblioteczne spełniają to wymaganie) lub tablicę w stylu C, możemy łatwo uogólnić rozwiązanie 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
}

W razie potrzeby typy kontenerów można dodatkowo ograniczyć.

Evg
źródło
Nie działa to w przypadku tablic w stylu C
Cruz Jean
1
@CruzJean, jasne. Dlatego zapytałem, co to jest pojemnik. W każdym razie można to łatwo naprawić za pomocą dodatkowej specjalizacji, zobacz zaktualizowaną odpowiedź.
Evg
2
@ Evg dziękuję. Dzisiaj dowiedziałem się o std :: void_t! Znakomity!
marco6,
2

Możesz zdefiniować następujący szablon klasy, vector_depth<>który pasuje do dowolnego typu:

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

Ten podstawowy szablon odpowiada przypadkowi bazowemu, który kończy rekurencję. Następnie zdefiniuj odpowiednią specjalizację dlastd::vector<T> :

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

Ta specjalizacja pasuje do std::vector<T> i odpowiada przypadkowi rekurencyjnemu.

Na koniec zdefiniuj szablon funkcji GetDepth(), który odwołuje się do szablonu klasy powyżej:

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

Przykład:

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

Dane wyjściowe tego programu to:

0 1 2 3
眠 り ネ ロ ク
źródło
1
Działa to std::vector, ale na przykład GetDepth(v), gdzie vjest intnie skompiluje. Lepiej byłoby mieć GetDepth(const volatile T&)i po prostu wrócić vector_depth<T>::value. volatilepo prostu pozwala na pokrycie większej liczby rzeczy, mając maksymalną kwalifikację cv
Cruz Jean
@CruzJean Dzięki za sugestię. Zredagowałem odpowiedź.
眠 り ネ ロ ク