Самый эффективный способ заполнить вектор индексами, соответствующими столбцам матрицы в конструкторе?

Question

У меня есть динамический шаблонный класс Matrix, для которого я хочу создать вектор и заполнить его индексами, которые идут вниз по столбцам, а не по строкам.Как вы, наверное, уже догадались из того, что я только что сказал, я храню фактические данные матрицы в виде строки-строки в std::vector<T>.Вот упрощенная версия моего определения класса Matrix только с соответствующими частями.

template<typename T>
class Matrix {
    public:
        Matrix(std::size_t m, std::size_t n, const T &elem = T());
        Matrix(const std::vector<T> &vec, std::size_t m, std::size_t n); 
        Matrix(std::initializer_list<T> list, std::size_t m, std::size_t n);

    private:
        typedef std::vector<std::size_t> reindex_scheme;

        std::vector<T> _data;
        reindex_scheme _colindices;
        std::size_t _m;
        std::size_t _n;

};

По сути, я хочу, чтобы, когда мне был предоставлен этот фрагмент кода:

std::vector<int> input {1, 2, 4, 6, 5, 4};
Matrix<int> A(input, 2, 3); // creates a 2x3 matrix with entries 1 2 4
                            //                                   6 5 4

для того, чтобы сохранить следующее в _colindices в следующем порядке:

0 3 1 4 2 5

(если вы поймете, что я делаю, я просто беру индекс элемента, если вы пересекаете матрицу следующим образом:

 |   /|   /|
 | /  | /  |
\/   \/   \/

надеюсь, вы сможете разобраться со стрелками)

То, что у меня пока есть для конструкторов, - это «наивный» for метод на основе:

template<typename T>
Matrix<T>::Matrix(std::size_t m, std::size_t n, const T &elem)
    : _data(m * n, elem),
      _colindices(m * n), 
      _m(m),
      _n(n) {
    for (std::size_t i = 0; i < _n; i++)
        for (std::size_t j = 0; j < _m; j++)
            _colindices[i * _m + j] = j * _n + i;
}

template<typename T>
Matrix<T>::Matrix(const std::vector<T> &vec, std::size_t m, std::size_t n)
    : _data(vec),
      _colindices(m * n), 
      _m(m),
      _n(n) {
    for (std::size_t i = 0; i < _n; i++)
        for (std::size_t j = 0; j < _m; j++)
            _colindices[i * _m + j] = j * _n + i;
}

template<typename T>
Matrix<T>::Matrix(std::initializer_list<T> list, std::size_t m, std::size_t n)
    : _data(list),
      _colindices(m * n), 
      _m(m),
      _n(n) {
    for (std::size_t i = 0; i < _n; i++)
        for (std::size_t j = 0; j < _m; j++)
            _colindices[i * _m + j] = j * _n + i;
}

Кроме того, в качестве примечания вы можете увидеть глупое дублирование кода, которое я делаю для трех конструкторов.Если вы знаете, как лучше объединить три в один или, по крайней мере, три в два, пожалуйста, сообщите мне и здесь. (извините, это стало своего рода двойным вопросом)

Это forметод работает, но, очевидно, это O (mn), и мне нравится думать, что есть лучший, более эффективный способ, может быть, с некоторыми std методами?Я думал о чем-то вроде создания вектора с 0 3, а затем итерации по нему, создания нового вектора путем увеличения каждого элемента, может быть, на std::transform или чего-то еще, и добавления этого в конец конечного вектора, пока я не доберусь доконец (если вы понимаете, о чем я говорю).Вроде как

Loop Iteration 1:
0 3
Loop Iteration 2:
0 3 1 4
Loop Iteration 3:
0 3 1 4 2 5

Что ты думаешь?

Answer 1

Мои первые мысли о том, что ваша программа уже давно завершена, а мой ответ слишком поздний.

Но тогда, возможно, другие пользователи SO также захотят услышать о возможных решениях.

Чтение этоговы используете

мажорную строку строки в std :: vector

предлагает идею использовать std::valarray.С std::slice (или другим типом слайсов) вы можете просто работать со всеми видами индексов, которые вы можете себе представить.Индексный оператор [] вместе со срезами будет вычислять значения только тогда, когда они вам нужны.Это очень мощно и быстро.

Стандартный подход C ++ для построения матрицы состоит в использовании std::vector типа std::vector типа.А затем получить доступ к этим данным или выполнить операции с ними.Обратите внимание: A std::vector<std::vector<int>> использует также смежную память.Вы можете просто получить к нему доступ по-другому.Например: строки очень легко доступны.Вы можете просто использовать первое измерение.Для std::vector<std::vector<int>> data; вы можете просто написать data[row] для доступа ко всем столбцам в этой строке.

С столбцами это сложнее.Я думаю, что вы хотите достичь как-то получить доступ к столбцам.В противном случае не было бы необходимости вычислять индексы для столбцов или в порядке столбцов.

Недостатком этого является то, что вы не можете использовать свою матрицу с библиотекой algorithm.Без доступных итераторов, хм, сложно.

Я могу представить вам решение для матрицы, в которой есть итераторы для строк и столбцов.Для этого мы используем вектор ссылок на правильные значения в std::vector<std::vector<int>> data;, организованный по столбцам.Затем мы можем перебирать строки и столбцы и использовать std::algorithm s.

. Для оптимизации скорости можно создать ссылку на столбец, когда это необходимо.Это уменьшило бы сложность в конструкторе.

Для вашего бокового узла: повторный код в конструкторе.Пожалуйста, создайте приватную функцию в своем классе и вызовите ее в конструкторе.

Пожалуйста, посмотрите скелет матрицы с некоторым тестовым кодом (MSVS19):

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <tuple>
#include <sstream>
#include <numeric>


// Unfortunately the std::reference_wrapper does not work as expected.
// So we will build our own one
class IntRef
{
    // Here we will store the reference
    std::tuple<int&> t;
public:
    // Constructor. Take reference and store it in tuple
    IntRef(int&& intV) : t(intV) {}

    // Assignment to the referenced value
    int operator =(const int i) { std::get<0>(t) = i; return i; }

    // Explicit type cast to int&
    operator int& () { return std::get<0>(t); }

    // And, return the reference
    decltype(&std::get<0>(t)) operator&() { return &std::get<0>(t); }
};


// Some definitions to make reading easier
using IntRefV = std::vector<IntRef>;
using MatrixCIterator = std::vector<IntRef>::iterator;
using Columns = std::vector<int>;
using MatrixRIterator = Columns::iterator;


// The matrix
class Matrix
{
public:
    // Constructor defines the matrix size
    Matrix(size_t numberOfRows, size_t numberOfColumns);

    // Iterators for rows are simple, becuase we have vectors of columns. Use unterlying iterator
    MatrixRIterator rowIterBegin(size_t row) { return data[row].begin(); }
    MatrixRIterator rowIterEnd(size_t row) { return data[row].end(); }

    // Column iterator is complicated. Retzurn iterator to vevtor of references to column values
    MatrixCIterator columnIterBegin(size_t column) { return columnReferences[column].begin(); }
    MatrixCIterator columnIterEnd(size_t column) { return columnReferences[column].end(); }

    // Access data of matrix
    std::vector<int>& operator [] (const size_t row) { return data[row]; }

    // And, for debug purposes. Output all data
    friend std::ostream& operator << (std::ostream& os, const Matrix& m) {
        std::for_each(m.data.begin(), m.data.end(), [&os](const Columns & columns) {std::copy(columns.begin(), columns.end(), std::ostream_iterator<int>(os, " ")); std::cout << '\n'; });
        return os;
    }
protected:
    //The matrix, vector of vector of int
    std::vector<Columns> data;

    // The references to columns in data
    std::vector<IntRefV> columnReferences{};
};

// Constructor. Build basic matrix and then store references to columns in data 
Matrix::Matrix(size_t numberOfRows, size_t numberOfColumns) : data(numberOfRows, std::vector<int>(numberOfColumns)), columnReferences(numberOfColumns)
{
    for (size_t column = 0; column < numberOfColumns; ++column)
        for (size_t row = 0; row < numberOfRows; ++row)
            columnReferences[column].emplace_back(IntRef(std::move(data[row][column]))); // Std::move creates a rvalue reference (needed for constructor, nothing will be moved)
}



// Some test data for the istream_iterator
std::istringstream testData("1 2 10");



// Test the matrix
int main()
{
    // Define a matrix with 3 rows and 4 columns
    Matrix matrix(3, 4);
    // Test 1: Fill all values in column 2 with 42
    for (MatrixCIterator ci = matrix.columnIterBegin(2); ci != matrix.columnIterEnd(2); ++ci) {
        *ci = 42;
    }
    std::cout << matrix << "Column 2 filled with 42\n\n";

    // Test 2: Read input from istream and copy put that in column 1
    std::copy_n(std::istream_iterator<int>(testData), 3, matrix.columnIterBegin(1));
    std::cout << matrix << "Column 1 filled with testData '" << testData.str() << "'\n\n";

    // Test 3: Copy column 2 to cout (Print column 2)
    std::copy(matrix.columnIterBegin(2), matrix.columnIterEnd(2), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "This is column 2\n\n";

    // Test 4: Sum up the first 2 values of column 1 and show result
    std::cout << "\nSum of first 2 values of column 1:  " << std::accumulate(matrix.columnIterBegin(1), matrix.columnIterBegin(1) + 2, 0) << "\n\n";

    // Test 5: Fill all values in row 0 with 33
    std::for_each(matrix.rowIterBegin(0), matrix.rowIterEnd(0), [](int& i) { i = 33; });
    std::cout << matrix << "Row 0 filled with 33\n\n";

    return 0;
}

Надеюсь, что это дает представлениео том, как это может работать