Create n-dimensional vector with given sizes

Question

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?

Are you seriously even considering `vector>`? If you need multidimensional arrays, use a one-dimensional one and wrap it. — Columbo, May 01 '15 at 23:27
Oh, I don't know, a substantial performance increase? Less unnecessary indirection? Technically enforced bounds consistence? — Columbo, May 01 '15 at 23:28
vector> is more a list of lists than a multidimensional array. — Columbo, May 01 '15 at 23:29
@Columbo, Well, I do understand that elements are not stored continuously, but it still allows main thing I need: O(1) access to an element. And also allows to work with subarrays as with vectors (for example sometimes I want to swap or reassign particular subarrays) which is not the case for hand-written one (well something could be done but you need to write code for everything) — RiaD, May 01 '15 at 23:38
@Columbo `vector>` is good. Your advice is bad because it doesn't involve measuring if the contiguous array is actually necessary (i.e. an improvement). Worse: In some cases, a contiguous array with index calculation it's even harmful (e.g. for adding more columns). So please don't cry about `vector>`: measure. — stefan, May 04 '15 at 03:34
@stefan The question says he wants to create a multidimensional array. Adding columns after creation of that array implies that you wanted a list of arrays instead, or a list of lists, which is what `vector>` is. But a multidimensional array doesn't suddenly change the column count. — Columbo, May 04 '15 at 09:14
@Columbo: A manually written multidimensional array is still wrong: `std::array, N2>` is the way to go in case of fixed boundaries. — stefan, May 04 '15 at 10:14
@stefan Yeah... if you need to copy or assign the array. Anyway, lets end this discussion, this isn't leading anywhere. :) — Columbo, May 04 '15 at 10:19

score 7 · Answer 1 · answered May 02 '15 at 13:12

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

score 4 · Answer 2 · answered May 01 '15 at 22:02

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

The implementation of the non-specialized `make_vector` could simply be `return {first, make_vector(sizes...)}`. — Lingxi, May 06 '15 at 03:29

Yakk - Adam Nevraumont · Accepted Answer · 2015-05-03T01:35:06.047

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

@barrey you mean describe what ADL is? Or how it changes template function lookup rules? Oh, I made a mistake, sec. Ok, fixed I think. I should test & add an example, but helping run a a bday party for a 2 yo. ;) — Yakk - Adam Nevraumont, May 02 '15 at 13:34
How it changes the lookup rules so that the function template `bob` can be found in the trailing-return-type. I implemented this and it works, I just don't understand how. — Barry, May 02 '15 at 13:37
I could just edit in the [code](http://coliru.stacked-crooked.com/a/500d18515aae1524) if you want. — Barry, May 02 '15 at 13:38
@barry `struct alice{};` should not be a template. In `bob`, add `class Alice` to `template<>` args, possibly remove `T` if now unused (sorry on phone, using memory). Change arg to `Alice` instead of `alice`. Call with just `alice{}`. It works by having a template parameter dependent adl lookup (on `alice`) which is deferred to the point of instantiation instead of where the template is declared (which cannot find itself). Which is why `alice` and `bob` need be in the same namespace: recursive `bob` is found via ADL on `alice`. — Yakk - Adam Nevraumont, May 02 '15 at 15:46
@Yakk just edit it in when you have the time. I don't really understand what you're describing (or why my interpretation of it even compiles) — Barry, May 02 '15 at 16:58
@Barry edited with what I meant. gcc sadly exploded part way through, but end version works in clang and gcc. — Yakk - Adam Nevraumont, May 03 '15 at 01:35
Finally I decided to use this trick with ADL because it works better with my IDE parser (which shows unexistsing errors when I use other options) — RiaD, Jun 03 '15 at 13:34
@RiaD that's me, posting practical code on stack overflow, *cough* *cough* — Yakk - Adam Nevraumont, Jun 03 '15 at 14:45

iammilind · Answer 4 · 2015-05-05T09:35:14.333

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

score -2 · Answer 5 · answered May 05 '15 at 06:21

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.

@Barry No, you can't. Afaik, even the VLA-proposal for C++17 will only allow for arrays declared as local variables *with the outer dimension flexible, only*. There will still be no way to deal with variable sizes in types, as for example in `threeDArray = (int (*)[2*n][3*n])malloc(...);`. If your compiler has more VLA support, then it's because its a compiler extension, not because it's C++. — cmaster - reinstate monica, May 05 '15 at 14:42

Create n-dimensional vector with given sizes

5 Answers5

Linked

Related