Anyone have a better way to flatten a vector?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Anyone have a better way to flatten a vector?

  1. #1
    Join Date
    Jun 2009
    Posts
    1

    Question 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 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:

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

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,885

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

  3. #3
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    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.

  4. #4
    Join Date
    Jan 2004
    Location
    Düsseldorf, Germany
    Posts
    2,401

    Re: Anyone have a better way to flatten a vector?

    Quote Originally Posted by jamesjones View Post
    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 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;
    }
    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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center