マトリックス:対称マトリクスと疎マトリクスの圧縮ストレージ

圧縮メモリはマトリクス格納時に上三角/下三角のデータを格納するだけなので、n(n+1)/2個まで格納する.
対称行列と圧縮メモリの対応関係:下三角メモリi>=j,SymmetricMatrix[i][j]==Array[i*(i+1)/2+j]

#include<iostream>
using namespace std;

template<class T>
class SymmetricMatrix
{
protected:
 T* _array;
 size_t _size;
public:
 SymmetricMatrix(T* array, size_t size)
  :_array(new T[size*(size + 1) / 2])
  , _size(size)
 {
  // 
  for (int i = 0; i < size; ++i)
   for (int j = 0; j < size; ++j)
   {
      if(i >= j)
      _array[i*(i + 1) / 2 + j] = array[i*size + j];
    else
     break;
   }
 }
 void Display()
 {
  size_t index = 0;
  for (int i = 0; i < _size; ++i)
  {
   for (int j = 0; j < _size; ++j)
   {
    if (i >= j)
    {
     cout << _array[i*(i + 1) / 2 + j] << " ";
    }
    else
     cout << _array[j*(j + 1) / 2 + i] << " ";
   }
   cout << endl;
  }
  cout << endl;
 }
};
void Test1()
{
 int Matrix[5][5] = {
   {0,1,2,3,4},
   {1,0,1,2,3},
   {2,1,0,1,2},
   {3,2,1,0,1},
   {4,3,2,1,0}
 };
 SymmetricMatrix<int> sm((int*)Matrix, 5);
 sm.Display();
}
//// 
//// 。 {row,col,value} ， //// ， 。
//#include<iostream>
//#include<vector>
//using namespace std;
//template<class T>
//struct Triple
//{
// size_t _row;
// size_t _col;
// T _value;
//};
//template<class T>
//class SparseMatrix
//{
//public:
// SparseMatrix(size_t row, size_t col, const T& invalid)
//  :_row(row)
//  , _col(col)
//  , _invalid(invalid)
// {}
// SparseMatrix(T* arr, size_t row, size_t col, const T& invalid)
//  :_row(row)
//  , _col(col)
//  , _invalid(invalid)
// {
//  for (int i = 0; i < row; ++i)
//   for (int j = 0; j < col; ++j)
//   {
//    if (arr[i*col + j] != invalid)
//    {
//     Triple<T>  t;
//     t._row = i;
//     t._col = j;
//     t._value = arr[i*col + j];
//     _array.push_back(t);
//    }
//
//   }
// }
// SparseMatrix<T> Transpose()
// {
//  SparseMatrix<T> ret(_col,_row,_invalid);
//  
//  for (int i = 0; i < _col; ++i)
//  {
//   size_t index = 0;
//   while (index < _array.size())
//   {
//    if (_array[index]._col == i)
//    {
//     Triple<T> t;
//     t._row = _array[index]._col;
//     t._col = _array[index]._row;
//     t._value = _array[index]._value;
//     ret._array.push_back(t);
//    }
//    index++;
//   }
//  }
//  return ret;
// }
// SparseMatrix<T> FastTransport()
// {
//  SparseMatrix<T> sm(_col, _row, _invalid);
//  int *rowCounts = new int[_col];
//  int *rowStarts = new int[_col];
//  memset(rowCounts, 0, sizeof(int)*_col);
//  memset(rowStarts, 0, sizeof(int)*_col);
//  size_t index = 0;
//  while (index < _array.size())
//  {
//   rowCounts[_array[index]._col]++;
//   ++index;
//  }
//  rowStarts[0] = 0;
//  for (int i = 1; i < _col; ++i)
//  {
//   rowStarts[i] = rowStarts[i - 1] + rowCounts[i - 1];
//  }
//  int idx = 0;
//  sm._array.resize(_array.size());
//  for (index = 0; index < _array.size();++index)
//  {
//   idx = rowStarts[_array[index]._col];
//      sm._array[idx]._row= _array[index]._col;
//   sm._array[idx]._col = _array[index]._row;
//   sm._array[idx]._value = _array[index]._value;
//   ++rowStarts[_array[index]._col];
//  }
//  return sm;
// }
// void Display()
// {
//  size_t index = 0;
//  for (int i = 0; i < _row; ++i)
//  {
//   for (int j = 0; j < _col; ++j)
//   {
//    if (index < _array.size() && _array[index]._row == i&&_array[index]._col == j)
//    {
//     cout << _array[index++]._value << " ";
//    }
//    else
//     cout << _invalid << " ";
//   }
//   cout << endl;
//  }
//  cout << endl;
// }
//protected:
// vector<Triple<T>> _array;
// size_t _row;
// size_t _col;
// T _invalid;
//};
//
//
//void Test1()
//{
// int Matrix[6][5] = {
//   { 1, 0, 3, 0, 5 },
//   { 0, 0, 0, 0, 0 },
//   { 0, 0, 0, 0, 0 }, 
//   { 1, 0, 3, 0, 5 },
//   { 0, 0, 0, 0, 0 },
//   { 0, 0, 0, 0, 0 },
// };
// SparseMatrix<int>  sm((int*)Matrix, 6, 5, 0);
// sm.Display();
// sm.FastTransport().Display();
//}