Comment puis-je obtenir la profondeur d'un vecteur std :: multidimensionnel au moment de la compilation?

45

J'ai une fonction qui prend une dimension multidimensionnelle std::vectoret nécessite que la profondeur (ou le nombre de dimensions) soit transmise en tant que paramètre de modèle. Au lieu de coder en dur cette valeur, je voudrais écrire une constexprfonction qui prendra std::vectoret retournera la profondeur comme unsigned integervaleur.

Par exemple:

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

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

Cela doit être fait au moment de la compilation, car cette profondeur sera transmise à la fonction de modèle en tant que paramètre de modèle:

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

Y a-t-il un moyen de faire ça?

tjwrona1992
la source
4
La taille d'un std::vectorest une chose au moment de l'exécution, pas à la compilation. Si vous voulez un conteneur de taille au moment de la compilation, recherchez std::array. Aussi; rappelez-vous que cela constexprsignifie seulement " peut être évalué au moment de la compilation" - il n'y a aucune promesse que ce sera le cas. Il peut être évalué au moment de l'exécution.
Jesper Juhl
5
@JesperJuhl, je ne cherche pas la taille, je cherche la profondeur. Deux choses très différentes. Je veux savoir combien de std::vectors sont imbriqués les uns dans les autres. Par exemple avec std::vector<std::vector<int>> v;, GetDepth(v);renverrait 2 car il s'agit d'un vecteur bidimensionnel. La taille n'a pas d'importance.
tjwrona1992
4
Semi-liés: imbriqués vectorn'est pas toujours la meilleure façon de faire les choses. L'indexation manuelle 2D ou 3D d'un seul vecteur plat peut être plus efficace, selon le cas d'utilisation. (Juste des mathématiques entières au lieu de chasser des pointeurs des niveaux extérieurs.)
Peter Cordes
1
@PeterCordes Une meilleure efficacité n'est qu'une facette. Un autre est qu'un type plat représente mieux la nature contiguë du tableau. Une structure imbriquée (de longueurs individuelles potentiellement différentes) est fondamentalement une incompatibilité de type pour représenter un hyperrectangle contigu à n dimensions.
Konrad Rudolph
4
Sur le plan de la nomenclature, la bibliothèque standard utilise rankpour cette requête sur les types de tableaux (en accord avec la nomenclature mathématique des tenseurs). Peut-être que c'est un meilleur mot ici que «profondeur».
dmckee --- chaton ex-modérateur

Réponses:

48

Un problème de modèle classique. Voici une solution simple comme la bibliothèque standard C ++. L'idée de base est d'avoir un modèle récursif qui comptera une par une chaque dimension, avec un cas de base de 0 pour tout type qui n'est pas un vecteur.

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

Vous pouvez donc l'utiliser comme ceci:

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

Éditer:

Ok, j'ai terminé l'implémentation générale pour tout type de conteneur. Notez que j'ai défini un type de conteneur comme tout ce qui a un type d'itérateur bien formé selon l'expression begin(t)std::beginest importé pour la recherche ADL et test une valeur de type T.

Voici mon code avec des commentaires pour expliquer pourquoi les choses fonctionnent et les cas de test que j'ai utilisés. Notez que cela nécessite C ++ 17 pour être compilé.

#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
la source
Et si je veux que cela fonctionne pour tous les conteneurs imbriqués et pas seulement pour les vecteurs? Existe-t-il un moyen facile de réaliser cela?
tjwrona1992
@ tjwrona1992 Ya, vous pouvez littéralement copier et coller la std::vector<T>spécialisation et la changer en un autre type de conteneur. La seule chose dont vous avez besoin est le cas de base 0 pour tout type pour lequel vous n'êtes pas spécialisé
Cruz Jean
Je voulais dire sans copier / coller haha, Comme le modèle du modèle
tjwrona1992
@ tjwrona1992 Oh, pour cela, vous devez utiliser les fonctions constexpr de SFINAE. Je prototyperai quelque chose pour cela et je l'ajouterai en tant que montage.
Cruz Jean
@ tjwrona1992, quelle est votre définition d'un conteneur?
Evg
15

Si l'on suppose qu'un conteneur est un type qui a value_typeet iteratortypes de membres (conteneurs bibliothèque standard satisfont à cette exigence) ou un tableau de style C, on peut facilement généraliser Cruz Jean solution de:

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
}

Les types de conteneurs peuvent être davantage restreints si nécessaire.

Evg
la source
Cela ne fonctionne pas pour les tableaux de style C
Cruz Jean
1
@CruzJean, bien sûr. C'est pourquoi j'ai demandé ce qu'est un conteneur. Quoi qu'il en soit, il peut facilement être corrigé avec une spécialisation supplémentaire, voir la réponse mise à jour.
Evg
2
@Evg merci. Aujourd'hui, j'ai découvert std :: void_t! Brillant!
marco6
2

Vous pouvez définir le modèle de classe suivant vector_depth<>qui correspond à n'importe quel type:

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

Ce modèle principal correspond au cas de base qui termine la récursivité. Définissez ensuite sa spécialisation correspondante pour std::vector<T>:

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

Cette spécialisation correspond à un std::vector<T>et correspond au cas récursif.

Enfin, définissez le modèle de fonction GetDepth(), qui utilise le modèle de classe ci-dessus:

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

Exemple:

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

Le résultat de ce programme est:

0 1 2 3
眠 り ネ ロ ク
la source
1
cela fonctionne pour std::vector, mais par exemple GetDepth(v)vest intne sera pas compilé. Ce serait mieux d'avoir GetDepth(const volatile T&)et de revenir vector_depth<T>::value. volatilelaisse juste couvrir plus de choses, étant qualifié de cv maximum
Cruz Jean
@CruzJean Merci pour la suggestion. J'ai édité la réponse.
眠 り ネ ロ ク