Как поворачивать вектор векторов

Ответ 1

Я думаю, самое простое решение - просто написать простую функцию transpose с двумя циклами в ней:

std::vector<std::vector<int> > transpose(const std::vector<std::vector<int> > data) {
    // this assumes that all inner vectors have the same size and
    // allocates space for the complete result in advance
    std::vector<std::vector<int> > result(data[0].size(),
                                          std::vector<int>(data.size()));
    for (std::vector<int>::size_type i = 0; i < data[0].size(); i++) 
        for (std::vector<int>::size_type j = 0; j < data.size(); j++) {
            result[i][j] = data[j][i];
        }
    return result;
}

Возвращаемое значение должно быть легко оптимизировано. Я не думаю, что это будет проще или эффективнее с использованием любой стандартной функции, но я могу ошибаться.

Альтернативным подходом было бы хранить все данные в одной квартире vector, а затем вычислять позицию элемента i, j с помощью i*row_length + j или что-то в этом роде. Таким образом, перенос не требует копирования данных, а просто меняет расчет индексов.

Ответ 2

Посмотрите на Boost MultiArray. Вы можете создать под-представления ваших данных. Там также vnl_matrix, который имеет метод транспонирования.

Ответ 3

Я хотел бы представить обертку, которая преобразует строки → Col и Col → строки. Это избавит вас от необходимости копировать все данные.

#include <iostream>
#include <vector>

template<typename T>
class TwoDPivotWrapper
{
    public:
        // These two typedef were done with std::vector
        // in mind. But with a small amount of effort I am
        // sure they can be generalized. They are solely to define
        // value_type (the data stored in the 2-D array).
        typedef typename T::value_type          OneDType;
        typedef typename OneDType::value_type   value_type;

        // A constructor that wraps a 2-D structure.
        TwoDPivotWrapper(T& o)
            : object(o)
        {}

        // A helper class used to store the row after the first array accesses.
        class Row
        {
            friend class TwoDPivotWrapper;
            Row(TwoDPivotWrapper& w, size_t r)
                : wrapper(w)
                , row(r)
            {}

            TwoDPivotWrapper&    wrapper;  
            size_t               row;

            public:
                value_type operator[](size_t col)
                {                    
                    return wrapper.get(row,col);
                }
        };

        // The operator [] returns a Row object that overloads
        // the operator[] for the next dimension.
        Row operator[](size_t row)              {return Row(*this, row);}

        // Generic get function used to access elements.
        // Notice we swap the row/col around when accessing
        // the underlying object.
        value_type get(size_t row, size_t col)  {return object[col][row];}

    private:
        T&  object;
};

Типичное использование:

int main()
{
    typedef std::vector<std::vector<int> >      TwoDVector;

    TwoDVector  data(3,std::vector<int>(2,0));

    data[0][0]  = 1; data[0][1]  = 2;
    data[1][0]  = 3; data[1][1]  = 4;
    data[2][0]  = 5; data[2][1]  = 6;

    TwoDPivotWrapper<TwoDVector>               wrapper(data);
    std::cout << wrapper[0][0] << wrapper[0][1] << wrapper[0][2] << "\n";
    std::cout << wrapper[1][0] << wrapper[1][1] << wrapper[1][2] << "\n";
}

Ответ 4

Если вы собираетесь делать много линейной алгебры в С++, вы должны проверить Boost.uBlas.

#include <boost/numeric/ublas/matrix.hpp>

template <class M>
void printMatrix(const M& m)
{
    for (size_t i=0; i<m.size1(); ++i)
    {
        for (size_t j=0; j<m.size2(); ++j)
            std::cout << m(i,j) << " ";
        std::cout << std::endl;
    }
}

int main()
{
    namespace ublas = boost::numeric::ublas;
    typedef ublas::matrix<double> Matrix;
    Matrix A(3, 2);

    // Fill matrix A with incrementing values
    double counter = 0.0;
    for (size_t i=0; i<A.size1(); ++i)
        for (size_t j=0; j<A.size2(); ++j)
            A(i,j) = ++counter;

    printMatrix(A);
    std::cout << std::endl;

    // Transpose A and store it in B
    Matrix B = ublas::trans(A);
    printMatrix(B);

    return 0;
}

Ответ 5

Нужно ли быть вектором векторов?

Если нет, то вы, вероятно, можете реализовать оболочку над регулярным вектором элементов столбцов *. столбцов.

Что-то вроде:

class Vector
{
public:
    int operator[]( int index )
    {
        return 1;
    }
    friend class Wrapper;
private:
    Vector( std::vector<int> & vector, int index, int numElements );

    std::vector<int> v_;
    int index_;
    int numElements_;
};

class Wrapper
{
public:
    Vector operator[](int index)
    {
        return Vector( v_, index, numColumns_ );
    }

    Wrapper( int numRows, int numColumns);
    void setNumRows( int numRows );
    void setNumColumns( int numColumns );
private:
    std::vector<int> v_;
    int numRows_;
    int numColumns_;
};

и в основном:

Wrapper w;

int i = w[1][1];

EDIT:

Класс Vector будет представлять данные строки или столбца. Для этого необходимы параметры, линеаризованная матрица, матричная геометрия (количество строк и столбцов) и какая строка/столбец она представляет.

Попробуйте это с помощью карандаша и бумаги: 1. Запишите элементы матрицы 3x4 в матричной форме

11 12 13 14 21 22 23 24 31 32 33 34

• записать их линеаризованным образом:

11 12 13 14 21 22 23 24 31 32 33 34

Существует простая связь между индексами элементов из формы матрицы и его индексом в линеаризованной форме, которая зависит от геометрической матрицы.

• если вы хотите, чтобы вектор "содержал" элементы 21 22 23 24 (или 12 22 32), тогда вам нужно реализовать некоторую логику в вашем операторе [] (индекс int), который будет определять индекс в базовом векторе элемент из Vector [index].

Скажите, что ваш Вектор должен ссылаться на второй столбец из матрицы (т.е. 12 22 32). Затем: - первый элемент в векторе (т.е. Вектор [1]) является вторым элементом в линеаризованной матрице - второй элемент в векторе, 22, является 6-м элементом из лежащего в основе вектора - третий элемент в векторе, 32, является 10-м элементом v_

Теперь, с карандашом и бумагой, сделайте то же самое для третьего столбца матрицы (элементы 13 23 33). Посмотрите, заметите ли вы какое-либо сходство между индексами в базовом векторе для второго столбца (которые были 2, 6 и 10) и индексы, которые вы найдете для третьего столбца.