Mathematical '+' operation on nested vector std::vector<std::vector<double>>

Question

Say I defined second order tensors A and B as nested vectors as:

std::vector<std::vector<double>> A, B;

Now I want to calculate the elementwise addition, meaning:

// Elementwise addition of two tensors
//         |A11+B11  A12+B12  ... |
// A + B = | ...     A22+B22  ... |
//         | ...       ...    ... |

For a std::vector this can be achieved by creating a template for the '+' operator:

#include <cassert>
#include <vector>
#include <algorithm>

template <typename T>
std::vector<T> operator+(const std::vector<T>& a, const std::vector<T>& b)
{
    assert(a.size() == b.size());

    std::vector<T> result;
    result.reserve(a.size());

    std::transform(a.begin(), a.end(), b.begin(), 
                  std::back_inserter(result), std::plus<T>());
    return result;
}

int main(){
    std::vector<double> a {0.0, 1.0, 2.0};
    std::vector<double> b {2.0, 2.0, 2.0};

    std::vector<double> c = a + b  // yields {2.0, 3.0, 4.0}

    return 0;
}

I have tried to solve the problem using the std::for_each function, but I am getting a false result:

#include <vector>
#include <algorithm>

template <typename T>
std::vector<std::vector<T>> operator+=(std::vector<std::vector<T>>& A,
                                      const std::vector<std::vector<T>>& B)
{
    // Ommitt compatibility checks
    std::for_each( A.begin(), A.end(),[&B](std::vector<T>& a){
        std::for_each( B.begin(), B.end(),[&a](const std::vector<T>& b){
            std::transform( a.begin(), a.end(),b.begin(), a.begin(), std::plus<T>());
        });
    });

    return A;
}

template <typename T>
std::vector<std::vector<T>> operator+(std::vector<std::vector<T>> A,
                                     const std::vector<std::vector<T>>& B)
{ 
    return A += B;
}

int main(){
    std::vector<std::vector<double>> A {{0.0,1.0}, {2.0,3.0}};
    std::vector<std::vector<double>> B = {{10.0,100.0}, {1000.0,10000.0}};

    auto C = A + B; 
    // yields C =  {{1010, 10101}, {1012, 10103}
    // should yield C = {{10, 101}, {1002, 10003}}

    return 0;
}

Obviously my code does not yield the correct result. Any recommendations/solution to get a working (efficient) implementation of this?

Answer 1

For a vector, element lookup is O(1), so a simple counting loop would do. Be careful how you do it. Your current incorrect solution is O(n²) for the two outer loops alone. Do you see what happened?

for   (std::size_t x = 0;  x < A   .size();  x += 1)
  for (std::size_t y = 0;  y < A[0].size();  y += 1)
    A[x][y] += B[x][y];

This is again an O(n) pass over the two matrices.