How to pivot a vector of vectors

I am looking for an elegant way to pivot a vector of vector prefarably using STL algorithms or boost Sample data looks like this

vector<vector<int> > vm;
vector<int> v;
v.push_back(1);
v.push_back(2);
vm.push_back(v);
v.clear()开发者_JAVA技巧;
v.push_back(3);
v.push_back(4);
vm.push_back(v);
v.clear();
v.push_back(5);
v.push_back(6);
vm.push_back(v);

1   2
3   4
5   6

I want to get a vector of vectors of ints like this

1   3   5
2   4   6

I guess the simplest solution is just to write a simple transpose function with two loops in it:

std::vector<std::vector<int> > transpose(const std::vector<std::vector<int> > data) {
    // this assumes that all inner vectors have the same size and
    // allocates space for the complete result in advance
    std::vector<std::vector<int> > result(data[0].size(),
                                          std::vector<int>(data.size()));
    for (std::vector<int>::size_type i = 0; i < data[0].size(); i++) 
        for (std::vector<int>::size_type j = 0; j < data.size(); j++) {
            result[i][j] = data[j][i];
        }
    return result;
}

The return-by-value should be optimized away easily enough. I don't think it will get any simpler or more efficient by using any standard function, but I could be wrong.

An alternative approach would be to store all the data in one flat vector and then calculate the position of element i, j using i*row_length + j or something like that. This way, transposing involves no copying of data, but simply changing the calculation of the indices.

Look at Boost MultiArray. You can create sub-views of your data. There's also the vnl_matrix which has a transpose method.

I would introduce a wrapper that converts row -> col and col -> row. This will prevent you having to copy all the data.

#include <iostream>
#include <vector>

template<typename T>
class TwoDPivotWrapper
{
    public:
        // These two typedef's were done with std::vector
        // in mind. But with a small amount of effort I am
        // sure they can be generalized. They are solely to define
        // value_type (the data stored in the 2-D array).
        typedef typename T::value_type          OneDType;
        typedef typename OneDType::value_type   value_type;

        // A constructor that wraps a 2-D structure.
        TwoDPivotWrapper(T& o)
            : object(o)
        {}

        // A helper class used to store the row after the first array accesses.
        class Row
        {
            friend class TwoDPivotWrapper;
            Row(TwoDPivotWrapper& w, size_t r)
                : wrapper(w)
                , row(r)
            {}

            TwoDPivotWrapper&    wrapper;  
            size_t               row;

            public:
                value_type operator[](size_t col)
                {                    
                    return wrapper.get(row,col);
                }
        };

        // The operator [] returns a Row object that overloads
        // the operator[] for the next dimension.
        Row operator[](size_t row)              {return Row(*this, row);}

        // Generic get function used to access elements.
        // Notice we swap the row/col around when accessing
        // the underlying object.
        value_type get(size_t row, size_t col)  {return object[col][row];}

    private:
        T&  object;
};

Typical usage would be:

int main()
{
    typedef std::vector<std::vector<int> >      TwoDVector;

    TwoDVector  data(3,std::vector<int>(2,0));

    data[0][0]  = 1; data[0][1]  = 2;
    data[1][0]  = 3; data[1][1]  = 4;
    data[2][0]  = 5; data[2][1]  = 6;

    TwoDPivotWrapper<TwoDVector>               wrapper(data);
    std::cout << wrapper[0][0] << wrapper[0][1] << wrapper[0][2] << "\n";
    std::cout << wrapper[1][0] << wrapper[1][1] << wrapper[1][2] << "\n";
}

If you're going to be doing lots of linear algebra in C++, you should check out Boost.uBlas.

#include <boost/numeric/ublas/matrix.hpp>

template <class M>
void printMatrix(const M& m)
{
    for (size_t i=0; i<m.size1(); ++i)
    {
        for (size_t j=0; j<m.size2(); ++j)
            std::cout << m(i,j) << " ";
        std::cout << std::endl;
    }
}

int main()
{
    namespace ublas = boost::numeric::ublas;
    typedef ublas::matrix<double> Matrix;
    Matrix A(3, 2);

    // Fill matrix A with incrementing values
    double counter = 0.0;
    for (size_t i=0; i<A.size1(); ++i)
        for (size_t j=0; j<A.size2(); ++j)
            A(i,j) = ++counter;

    printMatrix(A);
    std::cout << std::endl;

    // Transpose A and store it in B
    Matrix B = ublas::trans(A);
    printMatrix(B);

    return 0;
}

Does it absolutely have to be a vector of vectors?

If not, then you could probably implement a wrapper over a regular vector of rows*columns elements.

Something like:

class Vector
{
public:
    int operator[]( int index )
    {
        return 1;
    }
    friend class Wrapper;
private:
    Vector( std::vector<int> & vector, int index, int numElements );

    std::vector<int> v_;
    int index_;
    int numElements_;
};

class Wrapper
{
public:
    Vector operator[](int index)
    {
        return Vector( v_, index, numColumns_ );
    }

    Wrapper( int numRows, int numColumns);
    void setNumRows( int numRows );
    void setNumColumns( int numColumns );
private:
    std::vector<int> v_;
    int numRows_;
    int numColumns_;
};

and in main:

Wrapper w;

int i = w[1][1];

EDIT:

The Vector class will represent the row or column data. It needs, as parameters, the linearized matrix, the matrix geometry(number of rows and columns) and what row/column it represents.

Try this with pencil and paper: 1. write the elements of a 3x4 matrix in matrix form

11 12 13 14 21 22 23 24 31 32 33 34

1. write them in a linearized fashion:

11 12 13 14 21 22 23 24 31 32 33 34

There is a simple relation between an element's indices from the matrix form and its index in the linearized form which depends on the matrix geometry.

1. if you want a Vector to "contain" elements 21 22 23 24 (or 12 22 32) then you need to implement some logic in your operator [] (int index) that will determine the index in the underlying vector of the element from Vector[index].

Say your Vector needs to reference the second column from the matrix (i.e. 12 22 32). Then: - the first item in the vector (i.e. Vector[1]) is the second element in the linearized matrix - the second item in the vector, 22, is the 6th element from the underlying vector - the third item in the vector, 32, is the 10th element of v_

Now, with pencil and paper do the same for the third column of the matrix( elements 13 23 33). See if you spot any similarity between the indexes in the underlying vector for the second column (which were 2, 6 and 10) and the indexes you find for the third column.