Get the first column of a matrix represented by a vector of vectors

Question

Suppose I'm representing a matrix foo of values using std::vector:

int rows = 5;
int cols = 10;    
auto foo = vector<vector<double>>(rows, vector<double>(cols));

Is there a cleverly simple way for me to get a vector<int> of size rows that contains the first "column" of foo:

{foo[0][0], foo[0][1], foo[0][2], foo[0][3], foo[0][4] }

Put another way, can I "transpose" foo so that the following three things are true:

foo_transpose.size() == cols
foo_transpose[0].size() == rows
foo_transpose[0] == {foo[0][0], foo[0][1], foo[0][2], foo[0][3], foo[0][4] }

Clarifying Note

There are a few good suggestions for alternative ways to represent a "matrix". When I use the term "matrix" I simply mean that each of the second level vector's will be the same size. I don't mean to suggest that I will be using this data structure for linear algebra type operation. I actually DO need a vector of vectors, or a data structure from which you can "pull out" 1D vectors, because I have functions that operate on vectors like:

double sum(vector<double> const & v);

That I call by:

sum(foo[0]);

It's just in a special case I came up to a situation that need to do:

sum({foo[0][0], foo[0][1], foo[0][2], foo[0][3], foo[0][4] };

For Loop Solution

There is an obvious for loop solution, but I was looking for something more robust and efficient.

Single

I highly advise against representing a matrix in this way. Cache locality will be terrible, and trivial operations like slicing, reshaping or transposing a matrix become a total pain in the arse. – Panatella

Do you have to roll your own matrix? If not, I'd suggest using Boost.MultiArray. – Tautologism

Do you require the returned column vector to be modifiable-direct to the source matrix (i.e. change a value in the column, it changes in he matrix)? It makes a considerable difference in the complexity of the possible solutions. I'm with paddy, on this, by the way. The only reason to use vector-of-vector is to benefit from variable row widths, which by definition a true matrix will not have. – Tallou

If your matrix sizes are known, it might be better to use an array: array<array<double, cols>, rows>> matrix; This will put the data in one consecutive memory area, improving cache efficiency. – Compelling

Lex, are you adding stuff to the vectors all the time, or does the matrix stay the same size once built? Do you expect to have rows of differing length? If your structure really is like a matrix, I can recommend a simple alternative that will give you what you want. – Panatella

@paddy, all rows are same length, and the size doesn't change. Please add your suggestion as an answer. – Single

@Lex There you go... =) – Panatella

why would you be getting a vector<int> of size rows? wouldn't it be a vector<double>? – Deltoro

Answer 1

As I mentioned in the comments, it's not practical to represent matrices using vector-of-vector for a few reasons:

1. It is fiddly to set up;
2. It is difficult to change;
3. Cache locality is bad.

Here is a very simple class I have created that will hold a 2D matrix in a single vector. This is pretty much how software like MATLAB does it... albeit a huge simplification.

template <class T>
class SimpleMatrix
{
public:
    SimpleMatrix( int rows, int cols, const T& initVal = T() );

    // Size and structure
    int NumRows() const                       { return m_rows; }
    int NumColumns() const                    { return m_cols; }
    int NumElements() const                   { return m_data.size(); }

    // Direct vector access and indexing
    operator const vector<T>& () const        { return m_data; }
    int Index( int row, int col ) const       { return row * m_cols + col; }

    // Get a single value
          T & Value( int row, int col )       { return m_data[Index(row,col)]; }
    const T & Value( int row, int col ) const { return m_data[Index(row,col)]; }
          T & operator[]( size_t idx )        { return m_data[idx]; }
    const T & operator[]( size_t idx ) const  { return m_data[idx]; }

    // Simple row or column slices
    vector<T> Row( int row, int colBegin = 0, int colEnd = -1 ) const;
    vector<T> Column( int col, int rowBegin = 0, int rowEnd = -1 ) const;

private:
    vector<T> StridedSlice( int start, int length, int stride ) const;

    int m_rows;
    int m_cols;

    vector<T> m_data;
};

This class is basically sugar-coating around a single function -- StridedSlice. The implementation of that is:

template <class T>
vector<T> SimpleMatrix<T>::StridedSlice( int start, int length, int stride ) const
{
    vector<T> result;
    result.reserve( length );
    const T *pos = &m_data[start];
    for( int i = 0; i < length; i++ ) {
        result.push_back(*pos);
        pos += stride;
    }
    return result;
}

And the rest is pretty straight-forward:

template <class T>
SimpleMatrix<T>::SimpleMatrix( int rows, int cols, const T& initVal )
    : m_data( rows * cols, initVal )
    , m_rows( rows )
    , m_cols( cols )
{    
}

template <class T>
vector<T> SimpleMatrix<T>::Row( int row, int colBegin, int colEnd ) const
{
    if( colEnd < 0 ) colEnd = m_cols-1;
    if( colBegin <= colEnd )
        return StridedSlice( Index(row,colBegin), colEnd-colBegin+1, 1 );
    else
        return StridedSlice( Index(row,colBegin), colBegin-colEnd+1, -1 );
}
    
template <class T>
vector<T> SimpleMatrix<T>::Column( int col, int rowBegin, int rowEnd ) const
{
    if( rowEnd < 0 ) rowEnd = m_rows-1;
    if( rowBegin <= rowEnd )
        return StridedSlice( Index(rowBegin,col), rowEnd-rowBegin+1, m_cols );
    else
        return StridedSlice( Index(rowBegin,col), rowBegin-rowEnd+1, -m_cols );
}

Note that the Row and Column functions are set up in such a way that you can easily request an entire row or column, but are a little more powerful because you can slice a range by passing one or two more parameters. And yes, you can return the row/column in reverse by making your start value larger than your end value.

There is no bounds-checking built into these functions, but you can easily add that.

You could also add something to return an area slice as another SimpleMatrix<T>.

Have fun.

Panatella

I should have explicitly stated that this is a row-major representation. I vaguely compared it to MATLAB, which I should mention is column-major. Use the representation that best suits your access needs. – Panatella

this is a great answer. one thing that would make it better -- especially for newbies like myself -- would be some example use cases: i.e., initiating a matrix, taking slices of it, setting values, . . . – Deltoro

here's a particular example i'm struggling with: how would you assign values to, say, the first column of a SimpleMatrix instance. with auto V = SimpleMatrix<double>(N, n_t, 0);, V.Column(0) = . . . isn't working for me. – Deltoro

on further consideration, it appears to me that additional methods are needed to support assignment of values to the matrix. question: why do you have duplicates of each method, one prepended with const and the other not? – Deltoro

Yes it would be tricky to set up a transparent method to return a slice as a reference. Perhaps this could be implemented somehow with valarray. As for the const and non-const methods, that's there to allow assignment to a specific value, but also maintain const-correctness if you are only reading values from a const version of the container. – Panatella