疎行列

疎行列（ほとんどの要素がゼロであるスカスカな行列）は、2次元配列で実装するとメモリの無駄遣いになるので、サイズが大きいなら連想配列で実装したほうが良い。C++でのやっつけな実装例。

#include<stdio.h>
#include<map>

// 疎行列
class SparseMatrix
{
public:
    typedef std::pair<int,int> Index;    // (i,j)の組
    typedef std::map<Index, int> Map;    // (i,j)-> の連想配列
    
    // (i,j)の値を取得する
    int get(int i, int j)
    {
        // (i,j)を連想配列から探す
        Map::iterator it = m_map.find( Index(i,j) );
        if( it == m_map.end() ){
            return 0;            // 見つからなければゼロ
        }else{
            return it-&gt;second;    // 見つかったら対応する k を返す
        }
    }

    // (i,j)の値 k を設定する
    void set(int i, int j, int k)
    {
        m_map[ Index(i,j) ] = k;
    }

    // 行列をゼロクリアする
    void clear(void)
    {
        m_map.clear();
    }

    // ゼロでない (i,j)->k をリスト表示する
    void dump(void)
    {
        printf("Dump:\n");
        Map::iterator it = m_map.begin();
        while( it != m_map.end() )
        {
            int i = it->first.first;
            int j = it->first.second;
            int k = it->second;
            printf("(%d,%d)->%d\n",i,j,k);
            it++;
        }
    }

private:
    Map m_map;    // 連想配列 (i,j)->k
};

// テストプログラム
int main(void)
{
    SparseMatrix A;
    A.clear();
    A.set(1,1,1);
    A.set(10000,0,100);

    printf("A(0,0) = %d\n",A.get(0,0));
    printf("A(1,1) = %d\n",A.get(1,1));

    A.dump();

    char s = getchar();
    return 0;
}