如何用STL查找map中首个键不连续的元素？

你之前尝试的find_first_of并不匹配你的需求——这个函数的作用是在第一个序列中匹配第二个序列的任意元素，和查找相邻元素不连续的场景完全无关。STL里专门有适配这个需求的函数：std::adjacent_find。

核心思路 #

std::map是有序容器，键默认按升序排列，所以我们只需要检查相邻元素的键是否满足“前一个键+1等于后一个键”，adjacent_find会帮我们定位第一个不满足这个条件的相邻对。

代码实现 #

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

// 判断相邻元素的键是否不连续
bool isDiscontinuous(const pair<int, int>& prevElem, const pair<int, int>& currElem) {
    return prevElem.first + 1 != currElem.first;
}

int main() {
    map<int, int> m {
        {1, 1},
        {2, 2},
        {3, 3},
        {5, 5},
        {6, 6},
        {8, 8},
    };

    // 从容器开头找首个不连续的相邻对
    auto discontIter = adjacent_find(m.begin(), m.end(), isDiscontinuous);
    if (discontIter != m.end()) {
        // 不连续的元素是相邻对的后一个元素
        cout << "从开头找的首个不连续键：" << next(discontIter)->first << endl; // 输出5
    }

    // 从指定位置（键为2的元素）开始找
    auto startPos = m.find(2);
    if (startPos != m.end() && next(startPos) != m.end()) {
        auto discontIter2 = adjacent_find(startPos, m.end(), isDiscontinuous);
        if (discontIter2 != m.end()) {
            cout << "从键2开始找的首个不连续键：" << next(discontIter2)->first << endl; // 输出5
        }
    }

    // 从指定位置（键为5的元素）开始找
    auto startPos5 = m.find(5);
    if (startPos5 != m.end() && next(startPos5) != m.end()) {
        auto discontIter3 = adjacent_find(startPos5, m.end(), isDiscontinuous);
        if (discontIter3 != m.end()) {
            cout << "从键5开始找的首个不连续键：" << next(discontIter3)->first << endl; // 输出8
        }
    }

    return 0;
}

关键说明 #

1. 迭代器返回逻辑：std::adjacent_find找到目标相邻对时，返回的是前一个元素的迭代器，需要通过next()获取真正不连续的那个元素。
2. 边界检查：使用前必须判断迭代器是否等于end()，避免越界访问；如果容器内所有键都连续，函数会返回end()。
3. 谓词灵活性：如果你的map是降序排列，只需把谓词改成判断prevElem.first - 1 != currElem.first即可。

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