STL matrix chain multiplication

Question

Please provide positive and not-so-positive feedback on style, clarity, or any other additional feedback you would like to provide.

#ifndef MATRIX_H_
#define MATRIX_H_

#include <string>

struct Matrix_error
{
    Matrix_error(std::string error)
    {
        m_error = error;
    }
    std::string m_error;
};

class Matrix
{
public:
    Matrix(std::string name, std::pair<int, int> dim, int mult);

    Matrix operator* (Matrix &m) throw (Matrix_error)
    {
        if (m_dim.second != m.m_dim.first) {
            throw Matrix_error(std::string("ERROR:" 
                "Matrix Multiplication Dimension Error")
                + m_name + m.m_name + std::string("\n"));
        }
        Matrix M(std::string("("+m_name + m.m_name+")"), 
            std::pair<int, int>(m_dim.first, m.m_dim.second), 
            m.m_mult + m_mult + m_dim.first*m_dim.second*m.m_dim.second);
        return M;
    }
    int getMultiplications() const {return m_mult;}
    std::string getName() const {return m_name;}
    std::pair<int,int> getDimensions() const {return m_dim;}
private:
    std::string m_name;
    std::pair<int,int> m_dim;
    int m_mult;

    friend std::ostream& operator<< (std::ostream &out, Matrix &m)
    {
        return out << m.m_name << "(" << m.m_dim.first
                   << ", " << m.m_dim.second << ")";
    }
};

#endif /* MATRIX_H_ */

#include <iostream>
#include <string>
#include "matrix.h"

Matrix::Matrix(std::string name, std::pair<int, int> dim, int mult = 0)
{
    m_name = name;
    m_dim = dim;
    m_mult = mult;
}

#include <iostream>
#include <list>
#include <iterator>
#include <cstdlib>
#include "matrix.h"

/*
 * Declare typedefs up front. Keep them to a minimal
 * to help readability and reduce amount of scrolling
 */
typedef std::list<Matrix>::iterator matrix_it;
typedef std::list<Matrix> matrix_chain;

/*
 * This function prints out the final results of 
 * the computations.
 */
void print_matrix_chain(matrix_it left, matrix_it right)
{
    while (left != right) {
        std::cout << (*left) << " = " << (*left).getMultiplications()  
                  << std::endl;
        left++;
    }
}

/*
 * This function finds the optimal way to multiply
 * N matrices together when provided a list of N
 * matrices
 */
matrix_chain optimal_matrix_chain_multiplication(matrix_chain &chain) 
{
    matrix_chain ret;
    if (chain.size() == 1) {
        ret.push_back(chain.front());
        chain.pop_front();
    } else if (chain.size() == 2) {
        Matrix A = chain.front();
        chain.pop_front();
        Matrix B = chain.front();
        chain.pop_front();
        Matrix C = (A*B);
        ret.push_back(A*B);
    } else {
        matrix_it pos = chain.begin();
        pos++;                                      //Start pos 1 from the left
        matrix_it end = chain.end();

        for (; pos != end; pos++) {
            matrix_chain left;
            matrix_chain right;
            copy(chain.begin(), pos, back_inserter(left));
            copy(pos, chain.end(), back_inserter(right));

            left = optimal_matrix_chain_multiplication(left);
            right = optimal_matrix_chain_multiplication(right);

            matrix_it lbegin = left.begin();
            matrix_it rbegin = right.begin();
            matrix_it lend = left.end();
            matrix_it rend = right.end();
            for (; lbegin != lend; lbegin++) {
                for(; rbegin != rend; rbegin++) {
                    try {
                        ret.push_back((*lbegin)*(*rbegin));
                    } catch (Matrix_error e) {
                        std::cout << e.m_error;
                    }
                }
            }
        }
    }
    return ret;   
}

int main(int argc, char *argv[])
{
    std::list<Matrix> chain;
    Matrix A(std::string("A"), std::pair<int, int>(5, 10), 0);
    chain.push_back(A);
    Matrix B(std::string("B"), std::pair<int, int>(10, 7), 0);
    chain.push_back(B);
    Matrix C(std::string("C"), std::pair<int, int>(7, 11), 0);
    chain.push_back(C);
    Matrix D(std::string("D"), std::pair<int, int>(11, 2), 0);
    chain.push_back(D);
    Matrix E(std::string("E"), std::pair<int, int>(2, 5), 0);
    chain.push_back(E);
    std::list<Matrix> ret = optimal_matrix_chain_multiplication(chain);

    print_matrix_chain(ret.begin(), ret.end());

    return 0;
}

Answer 1

Few remarks about the exception handling in your code - struct Matrix_error. Consider the following document - Error and Exception Handling - for a proper design of exception classes in C++:

1. Derive your exception class from std::exception. Except in very rare circumstances where you can't afford the cost of a virtual table, std::exception makes a reasonable exception base class, and when used universally, allows programmers to catch "everything" without resorting to catch(...).

2. Don't embed a std::string object or any other data member or base class whose copy constructor could throw an exception. That could lead directly to std::terminate() at the throw point. Similarly, it's a bad idea to use a base or member whose ordinary constructor(s) might throw, because, though not necessarily fatal to your program

3. There are various ways to avoid copying string objects when exceptions are copied, including embedding a fixed-length buffer in the exception object, or managing strings via reference-counting. However, consider the next point before pursuing either of these approaches.

4. Format the what() message on demand, if you feel you really must format the message. Formatting an exception error message is typically a memory-intensive operation that could potentially throw an exception. This is an operation best delayed until after stack unwinding has occurred, and presumably, released some resources. It's a good idea in this case to protect your what() function with a catch(...) block so that you have a fallback in case the formatting code throws

Answer 2

Andrei knows way more than me, so aside from his advice about using std::exception and not making your own error class, even if that were ok, you're passing the error message in by value, not by reference, which causes an unnecessary copy to be made.

struct Matrix_error
{
    Matrix_error(std::string error)
    {

// you probably would want  
    Matrix_error( std::string const & error)

// and since it's passed to the c'tor, you could use the member initialization list, which // is ever-so-slightly more correct

    Matrix_error( std::string & error) : m_error( error ) {}

// the reason that's considered more correct is that in your code, the default c'tor is 
// called first, then you are assigning it, which is a wasted call to the default c'tor. // If you supply it on the mem initialization list, then the c'tor is called directly with // the argument, so it saves a step. This can add up when initializing objects that are
// more complex than just strings.

// you might even be able to go a step futher, and declare m_error a const string, since // in principle, the error object should never need to *modify* the error message it
// takes, only print it out or log it somewhere. This is more correct because the more you
// use const, the less stuff can get changed, which means in the long run, fewer bugs and
// more correct designs.

Answer 3

I am not as thorough as lint++ but here are some coding issues.

Matrix(std::string name, std::pair<int, int> dim, int mult);

should really be

Matrix(std::string const& name, std::pair<int, int> const& dim, int const mult);

Yes "int const mult" is pedantic but also clearly indicates your intent i.e. to copy the value only.

Unnecessary parentheses bug me. << (*left) should be

<< *left

(*left).getMultiplications()

should be

left->getMultiplications()

Answer 4

The other approach is to make matrix dimensions as a template parameters, so you can make checks at compile time. It will heavily differ from your code, but i'll have some advantage in error checking.