C ++ Верхнетреугольный матричный оператор скобок
Я натолкнулся на блокпост с моим конкретным проектом. Я хочу создать матрицу верхнего треугольника (все элементы ниже диагонали равны нулю), которая выделяет только память, необходимую для хранения ненулевых элементов. Проблема, с которой я столкнулся — это индексирование в этой матрице. Я бы предпочел не перепроектировать матрицу, но если это единственное решение, то я могу принять его. Как примечание: Vector — моя собственная реализация, а не stl Vector.
Пока у меня есть класс, объявленный следующим образом:
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,
Оператор скобок также является виртуальной функцией из абстрактного базового класса и должен возвращать вектор&, Кроме того, эта реализация должна использовать оператор скобок, а не оператор function (), чтобы она была совместима с ранее написанным кодом. Я знаю, что было бы проще использовать плотную матрицу, но я ограничен только необходимым использованием памяти.
Моя первая попытка была связана с использованием одного вектора для хранения, похожего на матрицу 1d-массивов. Тем не менее, оператор скобки также представляется невозможным для этой реализации.
Мой вопрос: возможно ли вообще реализовать этот оператор скобок?
Решение
Ну, я не знаю, является ли это приемлемым решением, так как вы не предоставили ничего о 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;
}
}
Другие решения
Профессор изменил спецификации проекта, чтобы учесть перегрузку оператора в скобках. Это лучший метод для решения этой проблемы.