Flatten a multidimensional vector in c++

Question

I want to write a generic function in c++ to flatten any multidimensional vector provided. The signature of the method is as follows:

template <class U, class T>
void flatten(U* out, T& inp, int* dims, int n){
  // out is the flattened output
  // inp is some multidimensional vector<vector...<U>>
  // dims is an array of the dimensions of inp
  // n is the number of dimensions of inp
  int ticker[n];
  int prodLimit = 1;
  int prod = 0;
  
  // calculate prodLimit as product of elements in dims and initialize ticker
  for (int i=0; i<n; i++){
    ticker[i] = 0;
    prodLimit *= dims[i];
  }
  
  while (prod < prodLimit){
    
    // access the current element in inp
    {...}

    // update ticker
    for (int i=n-1; i>0; i++){
      if (ticker[i] == dims[i]){
        ticker[i] == 0;
        ticker[i-1] += 1;
      }
    }
    prod += 1;
    out[prod] = correctElementIn_inp;
  }
}

Most of the operations are straight forward except accessing the specific component of multi-dimensional vector inp. As the dimensions are unknown a-priori I create an array of size n in a while loop to handle the counter for each dimension and update it properly. Now the only problem remaining is using the ticker to access the correct element in the vector.

As an example lets say the following holds:

#include <vector>

typedef std::vector<std::vector<double>> vec2;
typedef std::vector<std::vector<std::vector<double>>> vec3;

int main(){
  vec2 inp1 = {...};
  vec3 inp2 = {...};
  
  int s1[2] = {2,3};
  int s2[3] = {2,3,4};
  ...

}

Now this method should be able to handle both of inp1 and inp2. Is there a way of recursively accessing the vector elements without explicitly using the vector element access operator for each case.

`int ticker[n];` is not standard C++. [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) — 463035818_is_not_an_ai, Mar 30 '22 at 12:17
I can use new or a vector there but that is not my issue. But thanks for the guidance you provided. — D. ACAR, Mar 30 '22 at 12:22

463035818_is_not_an_ai · Accepted Answer · 2022-03-30T13:53:50.100

Your code is unecessarily complicated due to manually managing the memory and manually passing sizes around. Both is obsolete when you use std::vector. Even if you do want a raw C-array as result you can nevertheless use a std::vector and later copy its contents to properly allocated C-array. I would use a recursive approach:

#include <vector>
#include <iostream>

template <typename E,typename X>
void unroll(const std::vector<E>& v,std::vector<X>& out){
    std::cout << "unroll vector\n";
    out.insert(out.end(), v.begin(), v.end());
}


template <typename V,typename X>
void unroll(const std::vector<std::vector<V>>& v,std::vector<X>& out) {
    std::cout << "unroll vector of vectors\n";
    for (const auto& e : v) unroll(e,out);
}


int main() {
    std::vector<std::vector<std::vector<int>>> x;
    std::vector<int> y;
    x.push_back({{1,2,3},{4,5,6}});
    x.push_back({{7,8,9}});
    unroll(x,y);
    for (const auto& e : y) std::cout << e << " ";
}

Output:

unroll vector of vectors
unroll vector of vectors
unroll vector
unroll vector
unroll vector of vectors
unroll vector
1 2 3 4 5 6 7 8 9

Is there a way of recursively accessing the vector elements without explicitly using the vector element access operator for each case.

A vectors elements are stored in contiguous memory, hence you can use pointer arithmetics via its data(). However, a std::vector<std::vector<int>> does not store the ints in contiguous memory. Only the inner vectors elements are stored contiguously while each inner vector allocates the elements on the heap "somewhere". There is no short cut to access x[0][0][0] without accessing x[0][0]. Actually I would suggest to reconsider if you want to use nested vectors in the first place.

PS: I was cheating a little ;). I would expect it to be more performant to first calculate the total size of out before pushing elements to it as you are doing in your code. For brevity it was left out from the above. It can be done with similar recursion as the above code. Instead of pusing to out you would accumulate some size until you reach the first non-vector element type. Then reserve enough space for out upfront and only then run the actual recursion that populates out.

(1) The inputs I had were as a result of circumstance (Its due to binding python to cpp and cpp code's c wrapper to modelica language). Of course its possible to convert everything to vector and be done with it or just flatten everything in python side. What I wondered was if its possible to do these operations without manually coding every case. For instance what if the input was 5 dimensional like a batch of videos. — D. ACAR, Mar 31 '22 at 07:01
@D.ACAR sorry, I dont understand. Is this answer not answering your quesiton? `unroll` does work for every case, no? — 463035818_is_not_an_ai, Mar 31 '22 at 07:07

score 3 · Answer 2 · answered Mar 30 '22 at 16:25

If you have access to a C++20 compiler, I would use std::ranges::views::join recursively, to make a fully flattened view. You can then iterate this flat view without having to copy anything.

using namespace std::ranges;

template<typename R>
concept nested_range = input_range<R> && range<range_reference_t<R>>;

struct flatten_t
{
    template<nested_range R>
    auto operator()(R && r) const
    {
        return std::forward<R>(r) | views::transform(*this) | views::join;
    }
    
    template<typename T>
    auto operator()(T && t) const
    {
        return std::forward<T>(t);
    }
};

template<typename T>
auto operator |(T && t, flatten_t f)
{
    return f(std::forward<T>(t));
}

constexpr flatten_t flatten;

int main() {
    std::vector<std::vector<std::vector<int>>> x;
    x.push_back({{1,2,3},{4,5,6}});
    x.push_back({{7,8,9}});
    for (const auto& e : x | flatten) std::cout << e << " ";
}

Flatten a multidimensional vector in c++

2 Answers2