Оператор скобки верхней треугольной матрицы C++

Я наткнулся на блокпост с одним моим проектом. Я хочу создать матрицу верхнего треугольника (все элементы ниже диагонали равны нулю), которая выделяет только память, необходимую для хранения ненулевых элементов. У меня проблема с индексацией в эту матрицу. Я бы предпочел не переделывать матрицу, но если это единственное решение, то я могу его принять. В качестве примечания: Vector — это моя собственная реализация, а не вектор stl.

Пока у меня есть класс, объявленный следующим образом:

template <class T>
class UMatrix : public AbstractMatrix<T>
{
  private:
    Vector<T>* m_data;
    int m_size;
  public:
    //lots of member functions
};

Конструктор матрицы верхнего треугольника:

template <class T>
UMatrix<T>(const int size)
{
  m_size = size;

  if(size < 1)
    throw(RangeErr(size));

  m_data = new Vector<T> [size];
  for(int i = 0; i < size; i++)
  {
    Vector<T> init(i + 1);
    m_data[i] = init;
  }
}

И код, с которым у меня проблемы:

template <class T>
Vector<T>& operator[] (const int index)
{
  if(m_data != NULL && index >= 0 && index < m_rows)
  {
    // Insert dark magic here
  }
  else
  {
    throw(RangeErr(index));
  }
}

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

Я пытаюсь реализовать оператор скобки таким образом, чтобы UMatrix[a][b] обращался к строке a, столбцу b истинной верхней треугольной матрицы. Это означает, что UMatrix[a][b] == 0 при a > b.

Оператор скобок также является виртуальной функцией из абстрактного базового класса и должен возвращать вектор Vector&. Кроме того, эта реализация должна использовать оператор скобки, а не оператор function(), чтобы она была совместима с ранее написанным кодом. Я знаю, что было бы проще использовать плотную матрицу, но я ограничен только необходимым использованием памяти.

Моя первая попытка заключалась в использовании одного вектора для хранения, похожего на матрицу массива 1d. Однако оператор скобки, по-видимому, также невозможно написать для этой реализации.

Мой вопрос: возможно ли реализовать этот оператор скобок?


c++ operator-keyword matrix square-bracket
person Daniel Grooms    schedule 01.04.2015    source источник
comment
new Vector обычно ошибается. Почему бы просто не иметь векторный объект? Чтобы сделать 2d оператор [], вы должны использовать прокси-объект. Проще добавить operator(), который принимает любое количество параметров.   -  person Neil Kirk    schedule 01.04.2015

Ответы (2)


arrow_upward
0
arrow_downward

Что ж, я не знаю, приемлемо ли это решение, поскольку вы ничего не предоставили о классе Vector. Вы можете создать еще один класс, назовем его SparseVector<U>, где у вас будет такой код

virtual U& operator[](int i) {
    if(m_data != nullptr) {
        if(m_nnzb <= i && i <= m_nnze) {
            return m_data[i - m_nnzb];
        }
    }
    throw std::runtime_error("bad index: in SparseVector::operator[]");
}

Вот идея этой реализации. Это вектор размера m_size, в котором мы храним только ненулевые элементы в диапазоне от m_nnzb до m_nnze. И мы используем этот класс для оператора индекса в матричном классе. Вот полный код с небольшим примером.

#include <iostream>
#include <exception>
#include <stdexcept>

/* vector interface */
template<typename T>
class IVector {
public:
    virtual T& operator[](int i) = 0;
};

/* matrix interface */
template<typename T>
class IMatrix {
public:
    virtual IVector<T>& operator[](int i) = 0;
};

/* implementation for upper triangular matrix */
template<typename T>
class UpperMatrix : public IMatrix<T> {
public:
    /* implementation for sparse vector */
    template<typename U>
    class SparseVector : public IVector<U> {
    public:
        SparseVector() {
            m_size = m_nnzb = m_nnze = 0;
            m_data = nullptr;
        }
        SparseVector(int size, int b, int e) {
            m_size = size;
            m_nnzb = b;
            m_nnze = e;
            m_data = new U[e - b];
        }
        SparseVector(const SparseVector<U>& other) {
            m_size = other.m_size;
            m_nnzb = other.m_nnzb;
            m_nnze = other.m_nnze;
            m_data = new U[m_nnze - m_nnzb];
            for(int i = 0; i < m_nnze - m_nnzb; ++i) {
                m_data[i] = other.m_data[i];
            }
        }
        virtual U& operator[](int i) {
            if(m_data != nullptr) {
                if(m_nnzb <= i && i <= m_nnze) {
                    return m_data[i - m_nnzb];
                }
            }
            throw std::runtime_error("bad index: in SparseVector::operator[]");
        }
    protected:
        int m_size;
        int m_nnzb;
        int m_nnze;
        U*  m_data;
    };
    UpperMatrix(int n) {
        m_size = n;
        m_data = new SparseVector<T>[n];
        for(int i = 0; i < n; ++i) {
            m_data[i] = SparseVector<T>(n, i, n);
        }
    }
    virtual IVector<T>& operator[](int i) {
        if(i < m_size && m_data != nullptr) {
            return m_data[i];
        }
        throw std::runtime_error("bad index in UpperMatrix::operator[]");
    }
protected:
    int              m_size;
    SparseVector<T>* m_data;
};

int main(int argc, char** argv) {
    UpperMatrix<int> m1(3);
    /* correct index */
    for(int i = 0; i < 3; ++i) {
        for(int j = i; j < 3; ++j) {
            m1[i][j] = i + j;
        }
    }
    for(int i = 0; i < 3; ++i) {
        for(int j = i; j < 3; ++j) {
            std::cout << m1[i][j] << " ";
        }
        std::cout << std::endl;
    }
    /* incorrect index */
    try {
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                m1[i][j] = i + j;
            }
        }
    } catch(const std::exception& ex) {
        std::cout << "error occured: " << ex.what() << std::endl;
    }
}
person NikolayK    schedule 01.04.2015
comment
Проблема с этим подходом даже в названии: я не должен использовать память для хранения чего-либо, кроме ненулевых значений. Однако я думаю, что решил свою проблему, используя класс обратного вектора, который наследуется от вектора. Единственное отличие состоит в том, что оператор квадратных скобок возвращает m_data[m_size - index] вместо m_data[index]. - person Daniel Grooms; 01.04.2015
comment
@DanielGrooms И проблема всего в двух целых числах? - person NikolayK; 01.04.2015
comment
Представьте себе это: Matrix<int> large(10000);. Это проблема с разреженным хранилищем памяти. - person Daniel Grooms; 01.04.2015
comment
@DanielGrooms 1) Мне не нужно ничего представлять, но вам нужно рассчитать: допустим, у нас есть верхняя треугольная матрица размера n = 1000, поэтому есть 500000 ненулевых значений (1000 * 1000/2) и хранить это нам нужно дополнительно 2000 целых чисел. Но они занимают менее 1% всего хранилища (2000 / 502000 = 0,39%)! И вы думаете, что это большое дело? 2) Ваш вопрос был в том, возможно ли вообще реализовать этот оператор скобок? Я предоставил одно решение, я не говорил, что других нет. Я показал вам, что вам нужно создать еще один класс Vector, в том-то и дело, но вы этого тоже не видите. - person NikolayK; 02.04.2015

arrow_upward
-1
arrow_downward

Профессор изменил спецификации проекта, чтобы разрешить перегрузку оператора скобок. Это лучший метод, доступный для решения этой проблемы.

person Daniel Grooms    schedule 14.04.2015