上周写周报的时候遇到一个挺典型的排序问题有一组成绩数据要按分数从高到低输出排名但输出结果里必须带上选手原来的编号。我第一反应直接std::sort一把梭排完发现编号全乱了整个人愣在原地。后来才意识到排序会改变元素位置而我们需要的是排序后还原原始下标。这个问题看着简单但一旦数据里有重复值还要保证输出的原数据位置不重复就得把std::unique和平行数组结合起来才能干净利落地解决。这篇就把整个思路、代码细节和踩坑过程完整拆开讲一遍给正被排序后找原位置折磨的朋友一个可直接抄作业的参考。1. 这个需求到底在解决什么问题先说清楚需求本身。假设你手里有一个原始数组比如一组比赛成绩{3, 1, 4, 1, 5, 9, 2, 6, 5}现在要求按成绩从大到小输出并且输出时每组数据后面要标注它在原数组里的位置也就是下标。这个需求看起来人畜无害但真正动手写代码的时候会发现一个尴尬的事实std::sort排序过程中会移动元素排序完成后你只拿到了值有序的数组但完全不知道这个值原来在哪个位置。如果你只是要一个排好序的成绩单那没问题但如果是要做排名表格、要关联编号或者后续要用这个位置去索引其他数据那排序完了位置就彻底丢了。更麻烦的是这个需求里还有一句原数据位置不重复。什么叫位置不重复有两种理解理解一每个唯一的值只输出一次它的位置。比如成绩 5 出现了两次下标 4 和下标 8但我们只输出其中一个位置代表这个成绩所在的地方。这种诉求常见于统计有哪些不同的分数以及每个分数首次出现的位置。理解二输出的位置列表里不能有相同的下标。这个其实是排序后的天然要求——排序会改变顺序但每个元素的位置信息排列起来不应该有重复否则说明逻辑错了。从标题看重点落在std::unique上所以更贴近理解一先把数组从大到小排序再用std::unique去重同时还能知道每个去重后的值在原数组中的位置。平行数组在这里扮演的角色就是值排序时把原位置跟着值一起搬动这样才能保证unique之后依然拿得到正确的位置信息。很多人一开始卡住是因为把这个问题想成了排序 去重两个独立步骤。实际上难点不在排序也不在去重而在如何在排序和去重过程中始终绑定原始位置。一旦想通了这一点方案就很清晰了。2. 平行数组让数据值和位置一起排序要解决排序后还能找到原位置的问题最直接也最常用的思路就是平行数组parallel arrays。所谓平行数组本质上是用一份额外的数据来记录当前元素和原始位置的对应关系。当主数据在排序时发生移动位置数据跟着同步移动这样排序完成之后你依然能拿到每个值对应的原始下标。2.1 索引数组法最轻量的实现假设原始数据存在data里我们不直接对data排序而是另外创建一个idx数组里面存的是原始下标0, 1, 2, ...。然后对这个idx数组排序排序的比较器不比较idx本身而是去比较data[idx[i]]的大小。代码长这样#include algorithm #include iostream #include vector int main() { std::vectorint data {3, 1, 4, 1, 5, 9, 2, 6, 5}; std::vectorint idx(data.size()); for (size_t i 0; i data.size(); i) { idx[i] static_castint(i); } // 对 idx 排序比较的是 data 中对应位置的值 std::sort(idx.begin(), idx.end(), [](int a, int b) { return data[a] data[b]; // 从大到小 }); std::cout 排序后的原位置: ; for (int i : idx) { std::cout i ; } std::cout std::endl; std::cout 对应值: ; for (int i : idx) { std::cout data[i] ; } std::cout std::endl; return 0; }运行结果排序后的原位置: 5 7 4 8 2 0 6 1 3 对应值: 9 6 5 5 4 3 2 1 1注意看idx排序后的第一个元素是 5意味着原数组第 5 个位置的值 9 排在第一位。第二个元素是 7也就是原数组第 7 个位置的值 6。整个过程中data数组本身没有动过位置信息全部通过idx的下标间接访问。这个方案的优点很明显不需要复制原始数据只操作一个整型索引数组内存开销小适合大对象或者大数组的场景。缺点也很直接lambda 里通过data[a]访问值时容易让人产生混淆——尤其是当你习惯了直接对data排序时会下意识写成return a b;那排的就是下标本身了整个结果就全错了。这个点我后面会专门展开讲。2.2 结构体绑定法工程上更推荐索引数组方案虽然轻量但可读性弱一些。工程上更常见的做法是定义一个包含值和原位置两个字段的结构体然后把结构体数组交给排序算法。#include algorithm #include iostream #include vector struct Item { int value; int pos; // 原始位置 }; int main() { std::vectorint data {3, 1, 4, 1, 5, 9, 2, 6, 5}; std::vectorItem items; items.reserve(data.size()); for (size_t i 0; i data.size(); i) { items.push_back({data[i], static_castint(i)}); } // 从大到小排序先比较值值相等再比较位置保证稳定输出 std::sort(items.begin(), items.end(), [](const Item a, const Item b) { if (a.value ! b.value) { return a.value b.value; } return a.pos b.pos; }); for (const auto it : items) { std::cout 值 it.value 原位置 it.pos std::endl; } return 0; }输出值9 原位置5 值6 原位置7 值5 原位置4 值5 原位置8 值4 原位置2 值3 原位置0 值2 原位置6 值1 原位置1 值1 原位置3这种写法最大的好处是直观值在哪位置就跟在哪数据结构本身表达了绑定语义排序逻辑也清楚。实际业务代码里很多团队就喜欢这种方式因为后面维护的人一看Item就知道每个元素承载了两个信息。代价是如果你原始数组里存的是超大对象比如几百字节的自定义类型把整个对象拷进Item会带来额外的拷贝开销。这时候可以退回到索引数组方案或者用std::reference_wrapper/ 指针。但一般场景下结构体绑定法完全够用。2.3 std::pair 的单行写法如果你不想为了一个小场景定义一个结构体std::pair是天然的平行数组容器。pair的排序规则是先看first再比较second正好符合值优先、位置次之的需求。#include algorithm #include iostream #include utility #include vector int main() { std::vectorint data {3, 1, 4, 1, 5, 9, 2, 6, 5}; std::vectorstd::pairint, int vp; // (值, 原位置) for (size_t i 0; i data.size(); i) { vp.emplace_back(data[i], static_castint(i)); } std::sort(vp.begin(), vp.end(), [](const auto a, const auto b) { return a.first b.first; // 按值从大到小 }); for (const auto [v, p] : vp) { std::cout v - p std::endl; } return 0; }注意std::pair的默认operator是先 first 后 second但你现在要的是从大到小所以还是得写 lambda。如果不写 lambda那就std::sort之后再用std::greater()但那样second也会被降序值相等时位置就变成从大到小了输出的确定性稍差一些。所以还是建议写 lambda 自定义。三种写法没有绝对的好坏我的习惯是数据结构简单用小规模场景直接std::pair如果后续要在多个函数里传递、或者需要加更多字段比如排名、原始数据之外的相关属性提前定义结构体更省心如果原始数组是只读的大型容器尤其是存着字符串、图片路径这类重对象索引数组更合适。3. std::unique 的去重逻辑与边界处理排序解决了接下来就是去重。标题里点名了std::unique这里必须说透它的工作原理和使用陷阱。3.1 unique 只处理相邻重复std::unique的全名你应该见过templateclass ForwardIt ForwardIt unique(ForwardIt first, ForwardIt last);。它做的事是移除掉连续且相等的元素只保留每组相等元素中的第一个然后返回一个迭代器指向去重后新逻辑末尾的下一个位置。关键在于连续两个字。如果数组是{1, 2, 2, 3, 3, 1}直接调用unique会把中间的2, 2去重成23, 3去重成3但开头和结尾的两个1不会合并因为它们在物理上不相邻。这就是为什么std::unique之前必须先排序——排序让所有相等的元素站到一起unique才真正能达到全局去重的效果。放到这个场景里我们排序后得到的idx数组是这样的5 7 4 8 2 0 6 1 3对应的值9 6 5 5 4 3 2 1 1可以看到两个 5 相邻、两个 1 相邻。这时unique就能把它们各自压缩成一个。3.2 去重后的 size 调整与 resize 陷阱std::unique有一个特别容易让新手懵的行为它不会真的删除容器里的元素只是把重复的逻辑末尾移动了。换句话说调用完unique之后容器里那些重复元素的旧值还在但已经处于逻辑有效范围之外。所以要拿到真正干净去重后的容器必须配合erase使用标准写法是auto it std::unique(idx.begin(), idx.end()); idx.erase(it, idx.end());这就是常说的erase-remove 惯用法的 unique 变体。如果你忘了erase你会发现idx.size()根本没变小打印出来还和原来一样长但前面 N 个元素确实是去重后的结果。表面上看排序输出了重复位置实际上是你没把逻辑末尾之后的多余残留清掉。另外一个容易犯错的地方是我们这里不是直接对idx去重而是要对data[idx[i]]去重。也就是说两个位置哪怕idx[i]不同只要它们对应的data值相等就应该算重复只保留一个。这种情况下std::unique默认的operator完全没用必须给它传自定义的二元谓词auto it std::unique(idx.begin(), idx.end(), [](int a, int b) { return data[a] data[b]; }); idx.erase(it, idx.end());这个自定义谓词的逻辑是如果data[a]和data[b]相等就认为这两个元素重复保留a丢弃b。由于排序已经把所有相同值的元素排在一起了这里能正确把所有等值位置压缩成一个。去重后idx里每个元素就对应一个唯一值的原始位置正好满足原数据位置不重复的需求。3.3 自定义去重规则的注意事项在使用自定义unique谓词时有几个细节值得注意第一谓词必须满足等价关系。unique底层是相邻比较如果谓词返回true就认为相等。但如果你传入的谓词是不对称的比如data[a] data[b]结果是未定义的可能得到完全错误的位置列表。所以自定义谓词一定要设计成我判断的是这两个值是否相等而不是比较大小。第二分组去重保留的是每组第一个。在我们这个场景里如果两个位置的值相同unique保留的是排序后靠前的那个。由于排序时对相同值我们通常按位置升序排列也就是位置小的排在前面那unique之后保留的就是第一次出现最小下标的位置。如果你希望保留的规则不同比如保留最后一次出现的位置就需要在比较器中提前调整顺序让希望被保留的那个元素排在前面。第三unique返回值要在 erase 之前存好。如果你写成idx.erase(std::unique(...), idx.end());虽然也是合法的但可读性稍差。更关键的是unique返回的迭代器在erase之前是有效的但如果你在unique之后、erase之前又往容器里插入或删除了其他元素这个迭代器可能失效导致未定义行为。工程上建议把这两步分开写。4. 从大到小排列时的自定义比较器设计排序方向看似一句话的事但真正写代码时比较器的设计藏着很多决定结果正确性的细节尤其是和数据去重逻辑混在一起时更要谨慎。4.1 默认排序方向与比较器写法std::sort默认使用operator也就是升序排列。要实现从大到小通常有三种办法传std::greaterT()std::sort(v.begin(), v.end(), std::greaterint());传 lambdastd::sort(v.begin(), v.end(), [](int a, int b) { return a b; });反转迭代器不推荐std::sort(v.rbegin(), v.rend()); // 实际是升序但因为是反向遍历结果变成降序对我们的场景来说idx里的元素是下标不能直接用std::greaterint()因为那样比较的是下标而不是data的值。所以要写 lambda并且 lambda 里要去解引用原始数据数组std::sort(idx.begin(), idx.end(), [](int a, int b) { return data[a] data[b]; });4.2 比较器中的相等情况处理这里有个很多人容易忽略的问题如果data[a] data[b]时上面这个 lambda 会返回falsestd::sort认为两者等价它们的相对顺序是不确定的。为什么不确定会有问题因为后面unique去重时保留的是每组等价元素中的第一个。如果两个相同值的元素在排序结果中顺序不稳定那保留的位置就会时而是下标小的时而是下标大的导致输出结果不确定。这在单次运行里看不出问题但换一个编译器版本、换一份数据、甚至换一个平台结果可能就变了。要保证输出确定性比较器里应该处理相等情况值相等时再按位置升序排这样unique之后保留下来的必然是最先出现的那个位置。std::sort(idx.begin(), idx.end(), [](int a, int b) { if (data[a] ! data[b]) { return data[a] data[b]; // 主要排序键值从大到小 } return a b; // 次要排序键位置从小到大保证确定性 });4.3 稳定排序对位置输出的影响你可能听说过std::stable_sort它保证相等元素的相对顺序不变。那能不能用stable_sort替代sort来解决问题可以但要注意语义差异。stable_sort保留的是元素在排序前的相对顺序。拿idx初始数组来说它本来就是0, 1, 2, ...升序的用stable_sort按值降序排值相同的元素会保持原来的位置升序关系但如果idx初始数组不是这个顺序比如你之前打乱过那stable_sort保留的就是打乱后的顺序不一定是按位置升序。所以为了可预测性最好在比较器里显式声明值相等时按位置升序而不是依赖stable_sort的保序行为。性能上std::stable_sort的空间复杂度是 O(n)在内存受限或数据量大的场景下会有额外开销。能用sort解决的问题不一定需要stable_sort。我们这种需求比较器里加一个次要排序键用普通sort就能完全控制输出顺序没必要上stable_sort。只有当你希望排序后原数组中本来在前的仍然在前、本来在后的仍然在后这种语义时才真正需要它。5. 完整可运行的示例代码与输出前面的理论讲了这么多最终还是要落到能跑的代码上。这一节给一个完整的、可以直接复制粘贴编译运行的示例包含平行数组排序、std::unique自定义谓词去重、以及输出验证。5.1 示例场景带重复值的数组输出排序后的原位置完整程序如下#include algorithm #include iostream #include vector int main() { // 原始数据包含重复值 std::vectorint data {3, 1, 4, 1, 5, 9, 2, 6, 5}; // 创建索引数组平行数组的核心 std::vectorint idx(data.size()); for (int i 0; i static_castint(data.size()); i) { idx[i] i; } // 从大到小排序先按值降序值相等时按原位置升序 std::sort(idx.begin(), idx.end(), [](int a, int b) { if (data[a] ! data[b]) { return data[a] data[b]; } return a b; }); std::cout 排序后的位置序列去重前:; for (int p : idx) { std::cout p; } std::cout std::endl; std::cout 对应的值序列去重前:; for (int p : idx) { std::cout data[p]; } std::cout std::endl; // 用 std::unique 对 idx 去重data 值相等视为重复位置 auto new_end std::unique(idx.begin(), idx.end(), [](int a, int b) { return data[a] data[b]; }); idx.erase(new_end, idx.end()); std::cout \n去重后结果每个唯一值只保留一个原位置:\n; std::cout 值 原位置\n; for (int p : idx) { std::cout data[p] p std::endl; } return 0; }编译运行假设存为unique_pos.cppg -stdc17 -o unique_pos unique_pos.cpp ./unique_pos输出排序后的位置序列去重前: 5 7 4 8 2 0 6 1 3 对应的值序列去重前: 9 6 5 5 4 3 2 1 1 去重后结果每个唯一值只保留一个原位置: 值 原位置 9 5 6 7 5 4 4 2 3 0 2 6 1 1验证一下data[5] 9最大data[7] 6次大data[4] 5和data[8] 5相等只保留下标 4最后data[1] 1和data[3] 1相等只保留下标 1。完全符合从大到小 原数据位置不重复的要求。5.2 多组测试数据验证这个例子能处理多种情况我建议你自己多换几组数据测试比如测试 1全部元素相同data {7, 7, 7, 7}排序后idx {0, 1, 2, 3}值相等按位置升序。unique之后只剩{0}输出值 原位置 7 0结果合理所有值都一样去重后只保留第一个位置。测试 2全部元素不同data {3, 2, 1}排序后idx {0, 1, 2}。unique谓词比较data值没有相等的所以idx不变。输出值 原位置 3 0 2 1 1 2测试 3包含负数data {-5, 3, -5, 0}排序后从大到小idx {1, 3, 0, 2}对应值{3, 0, -5, -5}。unique后值 原位置 3 1 0 3 -5 0负数场景下照样工作。唯一需要留意的是比较器里的data[a] data[b]对自定义类型可能不适用那就要在类型里重载operator或者写合适的比较逻辑。6. 实际工程应用和踩坑经验代码写得顺手之后我越看越觉得这个组合技在真实项目里出现频率很高而且每次都有人踩到类似的坑。这一节聊聊我的工程观察和个人经验。6.1 可以立即用上的场景排行榜和比赛排名。最典型。一组选手成绩按分数降序排每个成绩后面要挂选手ID。如果只存了成绩数组排序之后选手ID关联不上整个排名表就废了。用平行数组把选手ID绑在下标上排序后直接通过idx取选手ID零成本。图像处理里的非极大值抑制NMS。目标检测场景下先按置信度对候选框从高到低排序再逐个判断是否抑制。候选框的原始索引在排序后必须保留否则没法回溯到原始检测结果。这个场景虽然通常用 Python/Numpy 实现但底层逻辑完全一致——按值排序索引数组再遍历索引处理。数据分析和报表生成。比如统计一段文本里各个单词出现的次数然后按次数降序输出单词 首次出现位置。先统计频率数组再对频率做排序 unique输出每个单词的首次出现位置平行数组加 unique 的组合正是标准解法。数据库排序后需要回到原始记录。虽然数据库里有ORDER BY但你拿到 C 里处理的数据如果是从接口直接拉来的没有数据库排序能力那就还是得自己排。需要把记录的下标跟着值一起走才能回到原始记录里取其他字段。6.2 我在实际使用中遇到的坑第一个坑前面提到过就是比较器写错。我见过最多的错误写法是这样std::sort(idx.begin(), idx.end(), [](int a, int b) { return a b; // 排的是下标不是 data 的值 });如果你忘了捕获data编译器可能会报data未定义但如果你在 lambda 外定义了一个全局data这个问题就是静默的——排序结果是下标从大到小而不是值从大到小。排查起来特别费劲因为程序不报错只是结果不对。我的建议是写完 lambda 之后先在纸上模拟一遍确认你比较的是元素值而不是平行数组本身。第二个坑是unique和erase分开写的问题。我在早期代码里试过一次只写std::unique不erase结果打印idx时发现最后面多了几个重复的旧值一看就是没删干净。后来养成了习惯unique之后一定配erase而且用auto it std::unique(...);先接住返回值再erase(it, idx.end())不要为了省一行代码把两件事挤在一起写否则出了问题不好定位。第三个坑是值相等但位置不重复的语义混淆。有同事拿着这个需求直接把data排序 unique 了然后打印data里每个元素的下标发现全是乱序。那是必然的——你对data本身做 unique元素移动之后下标早就不是原始下标了。正确的做法是始终操作平行数组idxdata只用来提供比较依据永远不要动它。这个主数组只读、辅助数组排序的心智模型能帮你避免绝大多数逻辑错误。6.3 性能考量与替代方案数据量小的时候随便怎么排都行。但如果你处理的是百万级数据std::sort的时间复杂度是 O(n log n)索引数组方案里多一次data[a]的间接访问在缓存命中率上会略逊于直接排结构体但差不了多少。真正要留意的是做unique时自定义谓词访问data的随机性——因为idx排序后已经按值排列了data[idx[i]]的访问模式基本是连续的缓存友好度还不错问题不大。如果你的数据量极大而且不仅要输出每个唯一值的第一个位置还要输出每个唯一值的所有位置列表那这个方案就不够用了得考虑std::unordered_map做分组聚合或者std::map自动按键排序。反之如果只是要去重后的排序值列表那直接对data排序 默认unique就够了根本不用平行数组。方案选型的关键在于你是否需要原始位置这个信息需要才上平行数组不需要别硬上否则就是给自己埋坑。另外一个容易被忽略的点是内存。std::stable_sort需要额外 O(n) 空间std::sort是原地排序。对于超大数组如果你用了stable_sort又叠加平行数组的内存开销可能会直接触发内存不足。我在一次处理近千万级浮点数据时就遇到过这个问题后来换成std::sort加显式次级比较键内存瞬间降下来了输出结果完全一致。所以默认能用sort就不要上stable_sort除非你真的需要稳定性的语义。最后再分享一个我自己实际工作里觉得实用的小技巧如果你处理的数据量不是特别大又怕排序后丢位置可以用std::mapint, std::vectorint把值映射到所有出现的位置列表。直接遍历原始数组填充 mapmap 本身按键升序排列再倒序遍历就能实现从大到小。但 map 的节点开销比 vector 大不少适合数据量小、代码量优先的场景。数据量大、追求性能时还是这篇文章里的平行数组 std::unique组合最稳。说到底排序后找到原位置这个问题核心不是你会不会sort而是你有没有建立数据值和位置信息绑定移动的思维模型。有了这个模型std::unique去重、从大到小输出、保留首次出现位置这些细节就都只是在这个模型上打补丁而已。希望这篇文章能帮你把这个模型彻底建立起来下次再遇到类似需求不用再挠头。