3

I made a matrix class and I would like to implement a method for transposition:

template<typename T>
void Matrix<T>::Transpose()
{
    // for square matrices
    if(this->Width() == this->Height())
    {
        for(std::size_t y = 1; y < this->Height(); ++y)
        {
            for(std::size_t x = 0; x < y; ++x)
            {
                // the function operator is used to access the entries of the matrix
                std::swap((*this)(x, y), (*this)(y, x));
            }
        }
    }
    else
    {
        // TODO
    }
}

The question is how to implement the transpose method for non-square matrices without allocating a whole new matrix (the class is used for big dense matrices) but inplace. Is there even a way?

Niall
  • 30,036
  • 10
  • 99
  • 142
Fytch
  • 1,067
  • 1
  • 6
  • 18
  • 1
    The algorithms for in-place transpose of non-square matrices are quite tricky: https://en.wikipedia.org/wiki/In-place_matrix_transposition. Note also that the output matrix will need to have its Width and Height dimensions swapped too, so your class will need to support modification of these. – Paul R Sep 19 '14 at 11:27
  • Related to, possibly a dup: [What is the fastest way to transpose a matrix in C++?](http://stackoverflow.com/q/16737298/1708801) – Shafik Yaghmour Sep 19 '14 at 11:44
  • 1
    How do you store your matrix? – D Drmmr Sep 19 '14 at 14:59
  • @DDrmmr As an 1D `std::vector`. – Fytch Sep 23 '14 at 07:44

1 Answers1

6

The most efficient way to transpose a matrix is not to transpose it at all.

It may be the most efficient to design the matrix class in a way that allows defining submatrices, slices or whatever on the same data buffer by additionally storing row and column step and an offset. Then accessing elements you use these data to calculate the indexes. To transpose you only need to manipulate these step-values.

You may look at Matrix implementation of OpenCV (just for implementation of functionality, not for class design!)

vlad_tepesch
  • 6,681
  • 1
  • 38
  • 80