关于C++ STL set中find函数!= end()判断条件的技术疑问
作为C++ STL新手,我对以下检测k范围内重复元素的代码存在疑问:
代码示例:bool checkDuplicatesWithinK(int arr[], int n, int k) { set<int> myset; for (int i = 0; i < n; i++) { if (myset.find(arr[i]) != myset.end()) return true; myset.insert(arr[i]); if (i >= k) myset.erase(arr[i-k]); } return false; }我理解
myset.find(arr[i])用于检查元素是否存在于set中,但不明白为何要使用myset.find(arr[i]) != myset.end()这样的不等于条件进行判断。
这其实是C++ STL容器的通用约定,我给你讲得明明白白:
首先得搞懂
std::set::find()的返回规则:当你用它查找某个元素时,如果元素存在,它会返回一个指向该元素的有效迭代器;如果元素不存在,它就会返回set.end()——这个end()返回的是「尾后迭代器」,它不指向容器里的任何实际元素,只是用来标记容器的末尾边界。那反过来想:如果
find(arr[i])的结果不等于end(),就说明它找到了一个有效的元素迭代器,也就意味着当前元素arr[i]已经在我们维护的set里了,这不就是我们要检测的「k范围内重复」情况吗?这时候直接返回true就完全符合代码逻辑。
打个生活化的比方:你在抽屉里找一把钥匙,如果找到了就直接拿出来(对应返回指向元素的迭代器);如果翻遍抽屉都没找到,就拿一个“空盒子”来表示没找到(对应end())。那判断“有没有找到钥匙”,就是看你手里拿的是不是那个“空盒子”——不是的话,肯定就是找到了钥匙呀。
再结合这段代码的整体逻辑:我们用set维护了一个最多包含最近k个元素的“滑动窗口”,每次遍历新元素时,先检查它是否在这个窗口里;如果是,说明k范围内有重复,直接返回true;如果不是,就把它加入窗口,同时如果窗口大小超过k了,就把最靠前的那个元素删掉,保证窗口始终是最近的k个元素。
这样是不是就彻底明白这个判断条件的意义啦?
内容的提问来源于stack exchange,提问作者Abhi

