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

Question

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

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;

问题是，每次我定义一个集合键值时，我需要为两个键（eg。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= 的问题完美地展示了这种结构如何与 open/close principle 发生冲突。

因此我的建议是将底层数据结构包装在一个 class 中以改进封装（为简单起见，我使用双精度而不是共享指针）：

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;

Online demo

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

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

An efficient approach to use unordered_map for representing a symmetric sparse matrix

c++

algorithm

unordered-map

typedef

matrix