Como posso obter a profundidade de um std :: vector multidimensional em tempo de compilação?

45

Eu tenho uma função que tem uma std::vectordimensão multidimensional e requer que a profundidade (ou o número de dimensões) seja passada como um parâmetro de modelo. Em vez de codificar esse valor, eu gostaria de escrever uma constexprfunção que aceite std::vectore retorne a profundidade como um unsigned integervalor.

Por exemplo:

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

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

Isso precisa ser feito em tempo de compilação, porque essa profundidade será passada para a função de modelo como um parâmetro de modelo:

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

Há alguma maneira de fazer isso?

tjwrona1992
fonte
4
O tamanho de a std::vectoré uma coisa em tempo de execução, não em tempo de compilação. Se você deseja um contêiner de tamanho em tempo de compilação, consulte std::array. Além disso; lembre-se de que constexprapenas significa " pode ser avaliado em tempo de compilação" - não há promessa de que será . Pode ser avaliado em tempo de execução.
Jesper Juhl
5
@JesperJuhl, não estou procurando por tamanho, estou procurando por profundidade. Duas coisas muito diferentes. Quero saber quantos std::vectors estão aninhados um no outro. Por exemplo std::vector<std::vector<int>> v;, GetDepth(v);retornaria 2, pois é um vetor bidimensional. O tamanho é irrelevante.
tjwrona1992
4
Semi-relacionado: aninhado vectornem sempre é a melhor maneira de fazer as coisas. A indexação manual 2d ou 3d de um único vetor plano pode ser mais eficiente, dependendo do caso de uso. (Apenas matemática inteiro em vez de ponteiro-perseguição dos níveis exteriores.)
Pedro Cordes
11
@PeterCordes Melhor eficiência é apenas uma faceta. Outra é que um tipo simples representa melhor a natureza contígua da matriz. Uma estrutura aninhada (de comprimentos individuais potencialmente diferentes) é fundamentalmente uma incompatibilidade de tipo para representar um hiper-retângulo n-dimensional contíguo.
Konrad Rudolph
4
Em termos de nomenclatura, a biblioteca padrão usa rankpara esta consulta em tipos de matriz (de acordo com a nomenclatura matemática para tensores). Talvez essa seja uma palavra melhor aqui do que "profundidade".
dmckee --- ex-moderador gatinho

Respostas:

48

Um problema clássico de modelagem. Aqui está uma solução simples, como a biblioteca padrão C ++. A idéia básica é ter um modelo recursivo que contará um por um cada dimensão, com um caso base de 0 para qualquer tipo que não seja um vetor.

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

Então você poderia usá-lo da seguinte maneira:

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

Editar:

Ok, eu terminei a implementação geral para qualquer tipo de contêiner. Note-se que I definido um tipo de recipiente como qualquer coisa que tenha um tipo de iteração bem formada de acordo com a express begin(t)onde std::beginé importado para pesquisa de ADL e té um Ivalue de tipo T.

Aqui está o meu código, juntamente com os comentários para explicar por que as coisas funcionam e os casos de teste que eu usei. Observe que isso requer C ++ 17 para compilar.

#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
fonte
E se eu quiser que isso funcione para todos os contêineres aninhados e não apenas para vetores? Existe uma maneira fácil de fazer isso acontecer?
tjwrona1992
@ tjwrona1992 Sim, você pode literalmente copiar e colar a std::vector<T>especialização e alterá-la para outro tipo de contêiner. A única coisa que você precisa é o caso 0 base para qualquer tipo que você não se especializam para
Cruz Jean
Eu quis dizer, sem copiar / colar haha, como templates do modelo
tjwrona1992
@ tjwrona1992 Ah, para isso você precisaria usar as funções consinapr SFINAE. Vou criar um protótipo para isso e adicioná-lo como uma edição.
Cruz Jean
@ tjwrona1992, qual é a sua definição de contêiner?
Evg
15

Supondo que um contêiner seja de qualquer tipo value_typee iteratortipo de membro (os contêineres de biblioteca padrão atendem a esse requisito) ou uma matriz de estilo C, podemos generalizar facilmente a solução de 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
}

Os tipos de contêiner podem ser ainda mais restritos, se necessário.

Evg
fonte
Isso não funciona para matrizes de estilo C
Cruz Jean
11
@CruzJean, com certeza. Por isso perguntei o que é um contêiner. De qualquer forma, ele pode ser facilmente corrigido com uma especialização adicional, consulte a resposta atualizada.
Evg
2
@Evg obrigado. Hoje eu aprendi sobre std :: void_t! Brilhante!
marco6
2

Você pode definir o seguinte modelo de classe vector_depth<>que corresponde a qualquer tipo:

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

Esse modelo primário corresponde ao caso base que encerra a recursão. Em seguida, defina sua especialização correspondente para std::vector<T>:

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

Essa especialização corresponde a std::vector<T>e corresponde ao caso recursivo.

Por fim, defina o modelo de função,, GetDepth()que recorre ao modelo de classe acima:

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

Exemplo:

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

A saída deste programa é:

0 1 2 3
眠 り ネ ロ
fonte
11
isso funciona std::vector, mas por exemplo, GetDepth(v)onde vestá intnão será compilado. Seria melhor ter GetDepth(const volatile T&)e apenas voltar vector_depth<T>::value. volatileapenas permite que ele cubra mais coisas, sendo qualificado como cv máximo
Cruz Jean
@CruzJean Obrigado pela sugestão. Eu editei a resposta.
眠りネロク