一种使用 unordered_map 表示对称稀疏矩阵的有效方法

Question

我正在使用unordered_map容器来表示对称稀疏矩阵。这是因为我不需要计算所有位置，我可以使用坐标作为快速数据检索的关键。我的地图如下所示：

typedef std::size_t coord1D;
typedef std::pair<coord1D,coord1D> coord2D;
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};
typedef std::unordered_map<coord2D, std::shared_ptr<double>, pair_hash> my_map;

问题是，每次我定义一个设置键值时，我需要为两个键(例如 i-j 和 j-i 对(提供相同的值，因为这表示的矩阵具有三角形性质，因此：

my_map example;
example [std::make_pair(0,1)] = std::make_shared<double> (0.5);
example [std::make_pair(1,0)] = std::make_shared<double> (0.5);

为了避免代码冗余，我正在考虑一个方便的功能(因为operator=在这里不能被覆盖(，但我也想知道是否有更有效的方法来处理这个任务。我认为使用的容器是最好的(因为不需要unordered_multimap(。

Answer 1

在unordered_map的 typedef 上构建矩阵类型似乎不能提供良好的封装。 当然，乍一看，这似乎提供了一个非常精简的解决方案。 但最终，operator=的问题完美地证明了这种结构如何与开/关原则相冲突。

因此，我的建议是将底层数据结构包装在一个类中以改善封装(为简单起见，我使用 double 而不是共享指针(：

using coord1D = std::size_t;    // time to forget about typedef ? 
using coord2D = std::pair<coord1D,coord1D>;
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};
class matrix {
    std::unordered_map<coord2D, double, pair_hash> m; 
public: 
    auto& operator[] (pair<int,int> p) { 
        if (p.first>p.second)
            p = make_pair(p.second, p.first);
        return m[p];
    }
};

在这种情况下，您可以将参数转换为operator[]，以便通过设计使矩阵呈三角形，避免冗余代码和冗余存储。

演示：

matrix m;
m[make_pair(1,5)] = 27.2;
cout << m[make_pair(1,5)]<<" "<<m[make_pair(5,1)]<<endl;

在线演示

当然，更好的方法是定义一个通用矩阵，并将其导出为一个专门的三角矩阵，在那里进行坐标变换。