
June 8th, 2009, 11:33 PM
#1
Anyone have a better way to flatten a vector?
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 onedimension, 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:
Code:
#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 3D vector
V1 vec1D = flatten(vec3D); // Flatten the vector to 1D
for (unsigned int i = 0; i != vec1D.size(); ++i) {
cout << vec1D[i] << endl;
}
return 0;
}

June 8th, 2009, 11:38 PM
#2
Re: Anyone have a better way to flatten a vector?
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.)

June 9th, 2009, 03:00 AM
#3
Re: Anyone have a better way to flatten a vector?
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.
Thanks for your help.

June 9th, 2009, 08:28 AM
#4
Re: Anyone have a better way to flatten a vector?
Originally Posted by jamesjones
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:
Code:
#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 3D vector
V1 vec1D;
flatten(vec3D, back_inserter(vec1D)); // Flatten the vector to 1D
for (V1::const_iterator it = vec1D.begin(); it != vec1D.end(); ++it)
std::cout << *it << endl;
}
More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason  including blind stupidity. W.A.Wulf
Premature optimization is the root of all evil Donald E. Knuth
Please read Information on posting before posting, especially the info on using [code] tags.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
