dot product of vector < vector < int > > over the first dimension

Question

I have

vector < vector < int > > data_mat ( 3, vector < int > (4) );
vector          < int >   data_vec ( 3                     ); 

where data_mat can be thought of as a matrix and data_vec as a column vector, and I'm looking for a way to compute the inner product of every column of data_mat with data_vec, and store it in another vector < int > data_out (4).

The example http://liveworkspace.org/code/2bW3X5%241 using for_each and transform, can be used to compute column sums of a matrix:

sum=vector<int> (data_mat[0].size());
for_each(data_mat.begin(), data_mat.end(),
         [&](const std::vector<int>& c) {
            std::transform(c.begin(), c.end(), sum.begin(), sum.begin(),
                           [](int d1, double d2) 
                             { return d1 + d2; }
                          );
            }
        );

Is it possible, in a similar way (or in a slightly different way that uses STL functions), to compute column dot products of matrix columns with a vector?

The problem is that the 'd2 = d1 + d2' trick does not work here in the column inner product case -- if there is a way to include a d3 as well that would solve it ( d3 = d3 + d1 * d2 ) but ternary functions do not seem to exist in transform.

Answer 1

In fact you can use your existing column sum approach nearly one to one. You don't need a ternary std::transform as inner loop because the factor you scale the matrix rows with before summing them up is constant for each row, since it is the row value from the column vector and that iterates together with the matrix rows and thus the outer std::for_each.

So what we need to do is iterate over the rows of the matrix and multiply each complete row by the corresponding value in the column vector and add that scaled row to the sum vector. But unfortunately for this we would need a std::for_each function that simultaneously iterates over two ranges, the rows of the matrix and the rows of the column vector. To achieve this, we could use the usual unary std::for_each and just do the iteration over the column vector manually, using an additional iterator:

std::vector<int> sum(data_mat[0].size());
auto vec_iter = data_vec.begin();
std::for_each(data_mat.begin(), data_mat.end(), 
              [&](const std::vector<int>& row) {
                 int vec_value = *vec_iter++;    //manually advance vector row
                 std::transform(row.begin(), row.end(), sum.begin(), sum.begin(),
                                [=](int a, int b) { return a*vec_value + b; });
              });

The additional manual iteration inside the std::for_each isn't really that idiomatic use of the standard library algorithms, but unfortunately there is no binary std::for_each we could use.

---

Another option would be to use std::transform as outer loop (which can iterate over two ranges), but we don't really compute a single value in each outer iteration to return, so we would have to just return some dummy value from the outer lambda and throw it away by using some kind of dummy output iterator. That wouldn't be the cleanest solution either:

//output iterator that just discards any output
struct discard_iterator : std::iterator<std::output_iterator_tag,
                                        void, void, void, void>
{
    discard_iterator& operator*() { return *this; }
    discard_iterator& operator++() { return *this; }
    discard_iterator& operator++(int) { return *this; }
    template<typename T> discard_iterator& operator=(T&&) { return *this; }
};

//iterate over rows of matrix and vector, misusing transform as binary for_each
std::vector<int> sum(data_mat[0].size());
std::transform(data_mat.begin(), data_mat.end(), 
               data_vec.begin(), discard_iterator(), 
               [&](const std::vector<int>& row, int vec_value) {
                   return std::transform(row.begin(), row.end(), 
                                         sum.begin(), sum.begin(),
                                         [=](int a, int b) { 
                                             return a*vec_value + b;
                                         });
               });

---

EDIT: Although this has already been discussed in comments and I understand (and appreciate) the theoretic nature of the question, I will still include the suggestion that in practice a dynamic array of dynamic arrays is an awfull way to represent such a structurally well-defined 2D array like a matrix. A proper matrix data structure (which stores its contents contigously) with the appropriate operators is nearly always a better choice. But nevertheless due to their genericity you can still use the standard library algorithms for working with such a custom datastructure (maybe even by letting the matrix type provide its own iterators).