C++ unordered_map正确遍历方式及TLE报错原因解析

题目链接：Leetcode medium- single number II

解题思路在纸面梳理完成后，遍历实现环节出现了问题。

可正常通过的代码版本 #

该版本可以完美通过所有测试用例：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> hash;
        for (int i=0; i<nums.size(); i++){
            hash[nums[i]]++;
        }
        int x;
        for (auto i:hash){
            if (i.second==1){
                x=i.first;
            }
        }
        return x;
    }
};

触发时间超限（TLE）的初始版本 #

最初编写的版本提交后触发TLE错误，代码如下：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> hash;
        for (int i=0; i<nums.size(); i++){
            hash[nums[i]]++;
        }
        int x;
        for (int i=0; i<hash.size(); i++){
            if (hash[i]==1){
                x= i;
            }
        }
        return x;
    }
};

两种写法都实现了遍历unordered_map的逻辑，基础测试用例下都能正常运行，但范围for循环版本可以顺利提交通过，索引遍历版本运行异常。针对这个现象有两个疑问：

1. 第二版索引遍历的代码存在什么问题？是性能不满足要求，还是存在语法层面的使用错误？
2. unordered_map有没有标准的正确遍历方式？第二种索引遍历的写法是不是错误用法？

问题解答 #

1. 索引遍历版本的核心问题 #

该写法同时存在语法层面的典型误用，以及直接引发TLE的严重性能问题：

• unordered_map属于关联容器，其重载的[]运算符不是顺序容器的按位置索引逻辑，作用是查找传入参数对应键的值，若该键不存在则自动插入一个默认构造的键值对（值为类型默认值，int类型即0）。
• 循环for (int i=0; i<hash.size(); i++)执行时，每次调用hash[i]都会将当前循环变量i作为键查询哈希表：若i原本不在表中，会直接插入新的键值对<i, 0>，导致hash.size()动态增大，循环终止条件i < hash.size()永远无法满足，循环退化为死循环，自然触发时间超限。
• 即便部分小范围测试用例碰巧没有触发死循环，该写法的逻辑本身也是错误的：遍历的目标是哈希表中存储的原有键，而该写法实际遍历的是从0开始的连续整数，和表中原有键没有对应关系，运行结果正确性完全依赖随机概率。

2. unordered_map的标准遍历方式 #

unordered_map不支持整数下标按存储位置遍历，使用递增整数i调用[]运算符遍历的写法属于完全错误的用法，合法的标准遍历方式有以下三种：

• 范围for循环（即提交通过的写法，简洁易读，日常开发首选）：

  for (auto& item : hash) {
      // item.first 为键，item.second 为对应值
  }
  

• 迭代器遍历（兼容所有C++版本的通用写法）：

  // C++11及以上可直接用auto推导迭代器类型
  for (auto it = hash.begin(); it != hash.end(); ++it) {
      // it->first 为键，it->second 为对应值
  }
  

• C++17及以上版本支持结构化绑定的范围for，可读性最优：

  for (auto& [key, val] : hash) {
      // 可直接使用key、val两个变量访问键和值
  }
  

内容的提问来源于stack exchange，提问作者Aditya Roy Chowdhury