Anyone have a better way to flatten a vector?

[jamesjones]

Hello. This is my first time posting. I have written a recursive template function to "flatten" a vector. I've just started reading up on recursive templates, and was wondering if anyone had some advice on a better way to do this (more efficient / easier to follow). When I say "flatten", I mean that I want to reduce a multidimensional vector to one-dimension, such as the following:

[[[1.0, 2.0], [3.0, 4.0]], [[5.0, 6.0], [7.0, 8.0]]] -> [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0]

If you respond, could you please explain what your code does, because I'm essentially just a beginner at C++. Here's a working version of what I have come up with:

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

template<typename T> vector<double> flatten(const vector<T>& vec);
template<typename T> vector<T> flatten(const T& value);

template<typename T>
vector<double> flatten(const vector<T>& vec) {

    assert(!vec.empty());

    vector<double> flatVec;
    vector<double> tempVec;

    for (unsigned int i = 0; i < vec.size(); ++i) {
        tempVec = flatten(vec[i]);
        flatVec.insert(flatVec.end(), tempVec.begin(), tempVec.end());	
    }

    return flatVec;
}

template<typename T>
vector<T> flatten(const T& value) {

    return vector<T>(1, value);
}

int main() {

   typedef vector<double> V1;
   typedef vector<vector<double> > V2;
   typedef vector<vector<vector<double> > > V3;

   V3 vec3D(1, V2(2, V1(3, 0.0)));  // Create a 3-D vector
   V1 vec1D = flatten(vec3D); // Flatten the vector to 1-D
   
   for (unsigned int i = 0; i != vec1D.size(); ++i) {
       cout << vec1D[i] << endl;
   }  

   return 0; 
}

[Lindley]

If you simply make a multidimensional interface to a 1D vector to begin with, then "flattening" is a noop. boost::multi_array does this. (Note that resizing arrays designed this way may be extra slow.)

[Peter_APIIT]

I was looking for that approach too but in case if you have 1d array, you can used the swap tricks to reduce the memory usage.

[treuss]

If you respond, could you please explain what your code does, because I'm essentially just a beginner at C++. Here's a working version of what I have come up with:

Your version looks fine, but passing around and copying the return values is not very elegant, thus a better (less code, more efficient) solution would be to pass an "inserter" object to the flatten function:

#include <iostream>
#include <vector>

using namespace std;

template<typename T, typename I>
void flatten(const vector<T>& vec, I inserter) {
  for (typename vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    flatten(*it, inserter);
  }
}

template<typename T, typename I> 
void flatten(const T& value, I inserter) {
  *inserter = value;
}

int main() {

   typedef vector<double> V1;
   typedef vector<vector<double> > V2;
   typedef vector<vector<vector<double> > > V3;

   V3 vec3D(1, V2(2, V1(3, 0.0)));  // Create a 3-D vector
   V1 vec1D;
   flatten(vec3D, back_inserter(vec1D)); // Flatten the vector to 1-D

   for (V1::const_iterator it = vec1D.begin(); it != vec1D.end(); ++it)
     std::cout << *it << endl;
}