Determine dimensionality structure of a vector of vectors of ...

[dariodem]

Hello People,

I want to write a template which I can pass to an undetermined
-in advance- nested structure vector, that is:
vecto<vector<vector<...>>>

I need the template to compute the dimensionality structure
of such a "multidimensional" vector.

That is: this vector has -for example- three vectors of four vectors of
six vectors of two double elements each.
Summarizing: the template has to end up with arrayDimensionality = {3,4,6,2}.

I tried to code it in recursive way, but I think I have some important conceptual problems because I cannot make it compile.

Here is the code

#include <iostream>
#include <vector>
#include <algorithm>

// determines the dimensionality structure of a vector of vectors of ...
template <typename T>
void	determine_array_dimensionality( std::vector<int>& arrayDimensionality, const std::vector<T>& matrix )
{
	if ( std::is_scalar<T>::value ) {
		arrayDimensionality.push_back(matrix.size());
		arrayDimensionality.shrink_to_fit();
	}
	else {
		arrayDimensionality.push_back(matrix.size());
		determine_array_dimensionality(arrayDimensionality, matrix[0]);
		std::vector<int>	sizes;
		for (auto i : matrix)
			sizes.push_back(i.size());

		if ( !(std::adjacent_find( sizes.begin(), sizes.end(), std::not_equal_to<int>() ) == sizes.end()) ) {
			std::cout << "determine_array_dimensionality template inconsistence.\n";
			std::cout << "Not all vectors in \"matrix\" argument have the same dimensionality.\n";
			exit( EXIT_FAILURE );
		}
	}
} // end template determine_array_dimensionality



int main() {
    std::vector<std::vector<int>>    v;
    std::vector<int>    dimensions;
    
    v.resize(3);
    v[0] = {0,1,2,3,4,5,6,7,8,9};
    v[1] = {0,1,2,3,4,5,6,7,8,9};
    v[2] = {0,1,2,3,4,5,6,7,8,9};
    
    determine_array_dimensionality(dimensions, v);
}

What am I doing wrong here?
Thanks!

[helios]

What if it's a jagged matrix? E.g.

    v[0] = {0,1,2,3,4,5,6,7,8,9};
    v[1] = {0,1,2,3,4,5,6,7};
    v[2] = {0,1,2,3,4,5,6,7,8,9,10};

[dariodem]

I have coded the template in a way that it detects that situation as an error (lines 16 to 24)

[helios]

There's several problems with your code.
1. std::is_scalar is the wrong check, since it returns false for any object type, which is a problem if, for example, T = std::string. You would need an is_vector.
2. You can't perform that check in an if anyway, because later on in the code you try to call T::size(). Even if you had an is_vector, the compiler need to compile both branches of the if and there can't be any type errors such as this. You need to branch using function overloading or template specialization.
3. Your jaggedness test misses several cases. Consider a 10x10x10 vector, where subvector [5][5] is resized to 5. Your check is unable to catch this.

[JLBorges]

template < typename T > bool is_rectangular( const T&  ) { return true ; }

template < typename T > bool is_rectangular( const std::vector< std::vector<T> >& matrix )
{
    static const auto neq_size = []( const auto& a, const auto& b ) { return a.size() != b.size() ; } ;
    if( std::adjacent_find( std::begin(matrix), std::end(matrix), neq_size ) != std::end(matrix) ) return false ;

    for( const auto& v : matrix ) if( !is_rectangular(v) ) return false ;
    return true ;
}

template < typename T > std::vector<std::size_t> dimensionality( const T& ) { return {} ; }

template < typename T > std::vector<std::size_t> dimensionality( const std::vector<T>& vec )
{
   if( !is_rectangular(vec) ) throw std::domain_error( "not rectangular" ) ;

   std::vector<std::size_t> dims { vec.size() } ;

   const auto inner_dims = dimensionality( vec.empty() ? typename std::vector<T>::value_type{} : vec.front() ) ;
   dims.insert( dims.end(), inner_dims.begin(), inner_dims.end() ) ;

   return dims ;
}

http://coliru.stacked-crooked.com/a/b0973ddf76c6693f

[dariodem]

Thank you very much helios, you are right.

Thanks JLBorges!
You are like a Jorge Luis Borges of c++!!! What a level.
Just one more question, and please excuse me if I am missing something obvious in your code.

Isn't it inefficient to call is_rectangular inside dimensionality?
I think, since is_rectangular is already recursive, it is enough to call it just one time.
Yet, it will be called every time in the recursion of dimensionality.
Wouldn't it be like a recursion of recursion, when it is not really necessary?

[JLBorges]

> Isn't it inefficient to call is_rectangular inside dimensionality?
> I think, since is_rectangular is already recursive, it is enough to call it just one time.
> Wouldn't it be like a recursion of recursion, when it is not really necessary?

Yes.

The refinement is quite straightforward.

template < typename T > std::vector<std::size_t> dimensionality( const T&, bool ) { return {} ; }

template < typename T > std::vector<std::size_t>
dimensionality( const std::vector<T>& vec, bool guaranteed_to_be_rectangualar = false )
{
    if( !guaranteed_to_be_rectangualar && !is_rectangular(vec) ) throw std::domain_error( "not rectangular" ) ;

    std::vector<std::size_t> dims { vec.size() } ;

    const auto inner_dims = dimensionality( vec.empty() ? typename std::vector<T>::value_type{} : vec.front(), true ) ;
    dims.insert( dims.end(), inner_dims.begin(), inner_dims.end() ) ;

    return dims ;
}

http://coliru.stacked-crooked.com/a/0c4a2357ddc9c681

[dariodem]

I suppose the code check conditions from left to right in the run in
if( !guaranteed_to_be_rectangualar && !is_rectangular(vec) )
In such case, once the the first check is false it does not bother checking the second one.
Then is_rectangular is called just one time in the first call to dimensionality.

Thanks a lot!