vector与unordered_set性能异常：特定数据致vector耗时激增

• 核心原因大概率是排序算法的最坏时间复杂度触发：如果你的vector版本统计逻辑是先对vector排序再遍历统计频率（比如调用了std::sort），那么当倒数第二个元素为-6时，刚好命中了排序算法的最坏情况。
  • 标准库的std::sort一般是introsort（快速排序+堆排序+插入排序的混合实现），当数据整体接近有序，但存在一个位置特殊的极端值时，可能会让快速排序阶段的划分操作严重失衡，导致时间复杂度从平均O(nlogn)暴跌到O(n²)。而unordered_set基于哈希表实现，插入和查找的平均时间复杂度是O(1)，不受数据顺序影响，所以能稳定快速完成统计。
• 为什么修改-6为其他值或移除它就恢复正常？因为这个特定位置的-6刚好破坏了数据的有序性，且刚好触发了排序算法的退化条件；换成其他值后，数据的无序程度不会导致划分失衡，移除后数据回到接近有序的状态，introsort会自动切换到堆排序来避免O(n²)的低效情况。

验证方法 #

• 检查vector版本代码是否包含排序步骤，若有，尝试替换为std::stable_sort或手动控制pivot的排序实现，对比性能变化。
• 打印原数据和排序过程中的中间数据分布，确认-6的位置是否导致了排序时的极端划分结果。

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