Create n-dimensional vector with given sizes

问题:

So, what I want is to create multidimensional vector of given type where the first dimension will have size of the first argument of a function call, etc, for example if I do

std::size_t n = 5;
auto x = make_vector<int>(n + 1, n * 2, n * 3);

x should be 6x10x15 3d array (consisting of zeroes, because I want to default construct right now)

I have tried this:

template <typename T>
std::vector<T> make_vector(std::size_t size) {
    return std::vector<T>(size);
}

template <typename T, typename... Args>
auto make_vector(std::size_t first, Args... sizes) -> std::vector<decltype(make_vector<T>(sizes...))> {
    auto inner = make_vector<T>(sizes...);
    return std::vector<decltype(inner)>(first, inner);
}

It seems to work for 1 or 2 arguments, but fails for 3 arguments with following error(clang++)

In file included from /Users/riad/ClionProjects/for-jhelper/output/run.cpp:1:
/Users/riad/ClionProjects/for-jhelper/tasks/TaskC.cpp:12:12: error: no matching function for call to 'make_vector'
                auto x = make_vector<int>(n + 1, n * 2, n * 3);
                         ^~~~~~~~~~~~~~~~
/Users/riad/ClionProjects/for-jhelper/tasks/../spcppl/make_vector.hpp:9:6: note: candidate template ignored: substitution failure [with T = int, Args = <unsigned long, unsigned long>]: call to function 'make_vector' that is neither visible in the template definition nor found by argument-dependent lookup
auto make_vector(std::size_t first, Args... sizes) -> std::vector<decltype(make_vector<T>(sizes...))> {
     ^                                                                     ~~~~~~~~~~~
/Users/riad/ClionProjects/for-jhelper/tasks/../spcppl/make_vector.hpp:4:16: note: candidate function template not viable: requires single argument 'size', but 3 arguments were provided
std::vector<T> make_vector(std::size_t size) {

If I understand correctly problem is that when compiler tries to calculate return value of make_vector it have to know the return value of vector with less number of arguments and fails to do so. How do I fix that?

回答1:

Create a namespace to put some helpers in it, called details.

In details create a type struct adl_helper{};

Create an implementation of make_vector, except its first parameter is always a template parameter called Adl. This template parameter is never named, and instances of it are passed to recursions.

Implement make_vector( blah ) by calling details::make_vector<T>( details::adl_helper{}, blah ).

namespace details {
  struct adl_helper { };

  template <class T, class Adl>
  std::vector<T> make_vector(Adl, size_t size) {
    return std::vector<T>(size);
  }

  template <class T, class Adl, class... Args,
    class R_T=decltype(
      make_vector<T>(Adl{}, std::declval<Args>()...)
    ),
    class R=std::vector<R_T>
  >
  R make_vector(Adl, size_t first, Args... sizes) 
  {
    auto inner = make_vector<T>(Adl{}, std::forward<Args>(sizes)...);
    return R(first, inner);
  }
}


template <class T, class... Args,
  class R=decltype(
    details::make_vector<T>(details::adl_helper{}, std::declval<Args>()...)
  )
>
R make_vector(Args... args)
{
  return details::make_vector<T>(details::adl_helper{}, std::forward<Args>(args)...);
}

What is going on here is that a seemingly recursive call in the signature of a template function is evaluated in two contexts.

First, it is evaluated where it is declared. In particular, it is evaluated before itself has been defined. So it doesn't "catch" itself.

Second, an ADL (argument dependent lookup) based pass is done at the point where it is instantiated based only off template types passed to the function.

The template<class Adl> and adl_helper types means that this argument dependent lookup can see the details::make_vector function itself when it is instantiated. And when it looks up the return type, it can also see details::make_vector. Etc.

live example.

The use of class R= aliases and the like is just there to cleanup the code and reduce some needless duplication.

In this particular case, the effort required to build the return type is easier than all this gymnastics.

I think this solution is cleaner:

template<class T>struct tag{using type=T;};
template<class Tag>using type=typename Tag::type;

template<class T, size_t n>
struct n_dim_vec:tag< std::vector< type< n_dim_vec<T, n-1> > > > {};
template<class T>
struct n_dim_vec<T, 0>:tag<T>{};
template<class T, size_t n>
using n_dim_vec_t = type<n_dim_vec<T,n>>;

回答2:

Interesting question! The problem you're running into is that unqualified name lookup will look in the scopes of where it is used (in increasing order of generality). But, from [basic.scope.pdecl]:

The point of declaration for a name is immediately after its complete declarator (Clause 8) and before its initializer (if any)

and in this function:

template <typename T, typename... Args>
auto make_vector(std::size_t first, Args... sizes) 
-> std::vector<decltype(make_vector<T>(sizes...))> {
    ...
}

The "complete declarator" includes the trailing-return-type. So the function template make_vector<T, Args...> will not be in scope yet until the {. That's why this won't compile for 3+ arguments.

The simplest fix would be if you had access to C++14, you simply wouldn't need the trailing return type;

template <typename T, typename... Args>
auto make_vector(std::size_t first, Args... sizes)
{ /* exactly as before */ }

Within the body of the name function, you can make the recursive call with no issues.

Without C++14, you could forward it to a class template whose name will be in the scope of all the recursive calls:

template <typename T, size_t N>
struct MakeVector
{
    template <typename... Args>
    static auto make_vector(std::size_t first, Args... sizes)
    -> std::vector<decltype(MakeVector<T, N-1>::make_vector(sizes...))>
    {
        auto inner = MakeVector<T, N-1>::make_vector(sizes...);
        return std::vector<decltype(inner)>(first, inner);        
    }
};

template <typename T>
struct MakeVector<T, 1>
{
    static std::vector<T> make_vector(std::size_t size) {
        return std::vector<T>(size);
    }
};

template <typename T, typename... Args>
auto make_vector(Args... args)
-> decltype(MakeVector<T, sizeof...(Args)>::make_vector(args...))
{
    return MakeVector<T, sizeof...(Args)>::make_vector(args...);
}

回答3:

I manage to do this by calculating the type separately but that seems unnecessary hard despite it's quite short.

template <typename T, int n>
struct NDVector {
    typedef std::vector<typename NDVector<T, n - 1>::type> type;
};

template <typename T>
struct NDVector<T, 0> {
    typedef T type;
};

template <typename T>
std::vector<T> make_vector(std::size_t size) {
    return std::vector<T>(size);
}


template <typename T, typename... Args>
typename NDVector<T, sizeof...(Args) + 1>::type make_vector(std::size_t first, Args... sizes) {
    typedef typename NDVector<T, sizeof...(Args) + 1>::type Result;
    return Result(first, make_vector<T>(sizes...));
}

Will really appreciate more elegant solution

回答4:

I was unaware about the other answers when I posted this. Not deleting it in case it could be useful to someone. Ofcourse the solution is quite trivial with C++14 enabled.

With [below code](Demo@ideone you can achieve:

  size_t n = 5;
  auto x = make_vector<int>(n+1, n*2, n*3);

Here is the code with minimal comments:

// Creating a multidimensional container (e.g. `vector`, `map`)
template<template<typename...> class Container,
         typename T,  
         size_t DIMENSION>
struct MultiDimensional
{
  using internal = MultiDimensional<Container, T, DIMENSION-1>;
  using type = Container<typename internal::type>;

  template<typename... Args>
  static
  type Generate (const size_t size, Args... sizes)
  {
    return type(size, internal::Generate(sizes...));
  }
};

// Last dimension overload
template<template<typename...> class Container,
         typename T>
struct MultiDimensional<Container, T, 1>  
{
  using internal = T;
  using type = Container<T>;

  static
  type Generate (const size_t size)
  {
    return type(size);
  }
};

// Wrapper for the specific requirement of creating a multidimensional `std::vector`
template<typename T,
         typename... Args>
auto make_vector(Args... sizes)
 -> typename MultiDimensional<std::vector, T, sizeof...(sizes)>::type
{
  return MultiDimensional<std::vector, T, sizeof...(sizes)>::Generate(sizes...);
}

回答5:

The easiest solution to this is to drop back to C:

void foo(size_t n) {
    int (*threeDArray)[2*n][3*n] = malloc((n + 1)*sizeof(*threeDArray));

    //Do with your array whatever you like.
    //Here I just initialize it to zeros:
    for(size_t i = 0; i < n + 1; i++) {
        for(size_t j = 0; j < 2*n; j++) {
            for(size_t k = 0; k < 3*n; k++) {
                threeDArray[i][j][k] = 0;
            }
        }
    }

    free(threeDArray);
}

As I said, this is not possible in C++: the C++ standard requires all array sizes to be compile time constants. C is much more flexible in this regard, allowing run time array sizes everywhere since C99, even within typedefs.

So, when I have some code that has to do serious work with multidimensional arrays, I seriously ask myself whether it is worth to move this code into a pure .c file and just link it together with the rest of my project.