如何对存储std::pair<int,int>的Eigen::Matrix排序并去重索引

针对你使用Eigen存储的未排序索引矩阵，以下是排序、去重的具体实现步骤，也可以连贯完成排序+去重：

核心思路 #

Eigen矩阵是二维结构，先将所有索引提取到一维容器（如std::vector）中处理，再转回Eigen矩阵。排序后使用std::unique去重（该函数仅对有序序列有效，因此必须先排序）。

具体代码实现 #

1. 将Eigen矩阵元素提取到vector #

先把二维矩阵里的所有<行,列>索引对转存到vector，方便后续排序：

#include <vector>
#include <algorithm>
#include <Eigen/Core>

// 假设unsorted_indices是已定义的Eigen矩阵
std::vector<std::pair<int, int>> indices_vec;
indices_vec.reserve(unsorted_indices.size()); // 预分配空间提升效率

// 行优先遍历矩阵所有元素（也可改为列优先，不影响最终排序结果）
for (int row = 0; row < unsorted_indices.rows(); ++row) {
    for (int col = 0; col < unsorted_indices.cols(); ++col) {
        indices_vec.push_back(unsorted_indices(row, col));
    }
}

2. 排序索引 #

使用std::sort排序，默认规则是先比较行索引，行索引相同再比较列索引（符合稀疏矩阵行优先的常见需求）：

std::sort(indices_vec.begin(), indices_vec.end());

如果需要列优先排序（先列后行），可以自定义排序规则：

std::sort(indices_vec.begin(), indices_vec.end(), 
    [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
        if (a.second != b.second) {
            return a.second < b.second; // 先比较列索引
        }
        return a.first < b.first; // 列索引相同再比行索引
    });

3. 去重 #

排序后用std::unique标记重复元素，再通过erase删除：

// unique会把重复元素移到容器末尾，返回第一个重复元素的迭代器
auto duplicate_start = std::unique(indices_vec.begin(), indices_vec.end());
// 删除从duplicate_start到末尾的所有重复元素
indices_vec.erase(duplicate_start, indices_vec.end());

4. 转回Eigen矩阵 #

将去重后的vector转回Eigen一维矩阵（通常用列向量存储索引更方便）：

// 创建动态行数、1列的Eigen矩阵
Eigen::Matrix<std::pair<int, int>, Eigen::Dynamic, 1> sorted_unique_indices(indices_vec.size());
for (int i = 0; i < indices_vec.size(); ++i) {
    sorted_unique_indices(i) = indices_vec[i];
}

能否同时实现排序与去重？ #

可以连贯执行排序+去重，本质是先排序让重复元素相邻，再用std::unique去重——这是效率较高的实现方式（时间复杂度主要由排序决定，为O(n log n)）。如果不排序直接去重，需要用哈希表（如std::unordered_set）存储已出现的索引，但需要自定义pair的哈希函数，实现复杂度更高，且对于大规模数据，效率未必优于排序+去重。

内容的提问来源于stack exchange，提问作者jomegaA