C++中COO格式稀疏矩阵按行、列索引排序的实现问询

我在程序中使用COO格式存储稀疏矩阵，该格式通过三个独立向量rowindex、colindex和values来表示矩阵。需要实现以下排序规则：

• 优先按rowindex升序排序
• 当rowindex相同时，按colindex升序排序

示例 #

原向量：

rowindex = [1, 2, 2, 1, 0, 2, 0, 1, 0, 2, 1, 2]
colindex = [7, 7, 2, 1, 3, 9, 8, 6, 6, 0, 3, 4]
values = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2]

排序后结果：

rowindex = [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
colindex = [3, 6, 8, 1, 3, 6, 7, 0, 2, 4, 7, 9]
values = [0.5, 0.9, 0.7, 0.4, 1.1, 0.8, 0.1, 1.0, 0.3, 1.2, 0.2, 0.6]

需求约束 #

必须满足以下三个条件：

• 使用C++内置的std::sort函数
• 不使用额外内存（如额外向量），因矩阵规模极大几乎占满内存
• 无需将矩阵转换为结构体数组（已知该方式可直接使用sort()）

我找到的多向量排序方案仅支持单个向量排序，无法满足同rowindex下按colindex排序的要求。

实现方案 #

可以通过自定义迭代器和交换逻辑实现，完全满足所有约束条件：

核心思路 #

1. 自定义一个随机访问迭代器，作为三个COO向量的位置代理，仅存储索引和向量引用，无额外数据存储
2. 重载迭代器的比较运算符，先对比rowindex值，再对比colindex值，实现需求的排序规则
3. 重载std::swap，针对该迭代器类型同步交换三个向量对应索引的元素
4. 直接使用std::sort对迭代器范围排序，即可完成三个向量的同步排序

代码实现 #

#include <algorithm>
#include <vector>

// 自定义COO迭代器，绑定三个向量的索引位置
struct COOIterator {
    using difference_type = std::ptrdiff_t;
    using value_type = void;
    using pointer = void;
    using reference = void;
    using iterator_category = std::random_access_iterator_tag;

    size_t idx;
    std::vector<int>& row;
    std::vector<int>& col;
    std::vector<double>& val;

    COOIterator(size_t i, std::vector<int>& r, std::vector<int>& c, std::vector<double>& v)
        : idx(i), row(r), col(c), val(v) {}

    // 随机访问迭代器必备运算符重载
    COOIterator& operator++() { idx++; return *this; }
    COOIterator operator++(int) { auto tmp = *this; idx++; return tmp; }
    COOIterator& operator--() { idx--; return *this; }
    COOIterator operator--(int) { auto tmp = *this; idx--; return tmp; }
    COOIterator& operator+=(difference_type n) { idx += n; return *this; }
    COOIterator operator+(difference_type n) const { return COOIterator(idx + n, row, col, val); }
    COOIterator& operator-=(difference_type n) { idx -= n; return *this; }
    COOIterator operator-(difference_type n) const { return COOIterator(idx - n, row, col, val); }
    difference_type operator-(const COOIterator& other) const { return idx - other.idx; }
    bool operator==(const COOIterator& other) const { return idx == other.idx; }
    bool operator!=(const COOIterator& other) const { return idx != other.idx; }
    
    // 核心比较逻辑：先按rowindex排序，再按colindex排序
    bool operator<(const COOIterator& other) const {
        if (row[idx] != other.row[other.idx]) {
            return row[idx] < other.row[other.idx];
        }
        return col[idx] < other.col[other.idx];
    }
    bool operator>(const COOIterator& other) const { return other < *this; }
    bool operator<=(const COOIterator& other) const { return !(*this > other); }
    bool operator>=(const COOIterator& other) const { return !(*this < other); }
};

// 重载swap，同步交换三个向量对应位置的元素
namespace std {
    template<>
    void swap(COOIterator a, COOIterator b) {
        std::swap(a.row[a.idx], b.row[b.idx]);
        std::swap(a.col[a.idx], b.col[b.idx]);
        std::swap(a.val[a.idx], b.val[b.idx]);
    }
}

// 使用示例
int main() {
    std::vector<int> rowindex = {1, 2, 2, 1, 0, 2, 0, 1, 0, 2, 1, 2};
    std::vector<int> colindex = {7, 7, 2, 1, 3, 9, 8, 6, 6, 0, 3, 4};
    std::vector<double> values = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.2};

    // 调用std::sort完成排序
    std::sort(COOIterator(0, rowindex, colindex, values),
              COOIterator(rowindex.size(), rowindex, colindex, values));

    // 验证排序结果
    // ...
    return 0;
}

方案说明 #

• 完全满足约束：使用C++内置std::sort，仅创建两个轻量迭代器（内存开销可忽略），无需转换结构体数组
• 所有操作直接作用于原向量，无额外内存分配
• 排序逻辑严格符合需求：优先按rowindex升序，同rowindex时按colindex升序

内容的提问来源于stack exchange，提问作者Ioannis E. Venetis