C++遍历map时const auto &it与auto &it为何出现TLE与AC差异

核心差异点 #

你观察到的性能差异本质是编译器优化策略和std::map的内置特性共同作用的结果，和你有没有手动修改元素没有直接关系：

• std::map的存储元素类型固定为std::pair<const Key, T>，键本身是不可修改的。当你使用auto &it做非常量引用遍历时，编译器无法通过静态分析确定你后续会不会修改元素值、甚至修改容器结构，因此会放弃很多可以大幅提升遍历效率的优化逻辑。
• 加上const修饰符后，编译器可以明确判定你不会通过这个引用做任何修改操作，就会自动开启迭代器地址缓存、循环提前终止预判等优化，遍历速度会有明显提升。

补充说明 #

SPOJ的判题时间阈值卡的比较严格，当测试用例的记录规模较大时，没有优化的非const遍历版本刚好超出时间限制，优化后的const版本就能顺利通过。另外你这段代码其实还可以进一步优化：不需要等全部插入完成后再遍历判断，插入的过程中只要发现某组(I,C)的计数已经大于1，就可以直接标记为不可能，跳过后续的插入操作，性能还能再提升一截。

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