c++ - 查找不在 std::set min-max 中的第一个值

Question

如何找到第一个值 h在 std::set<int> ids 中不这样结果就被限制在[0, *ids.rbegin() + 1]范围。

我看到这是一个相当简单的问题，但我还没有找到任何匹配的问题。基本上我想要 ids 的倒置集以便我可以使用它们。

到目前为止，我有以下内容:

#incldue <set>
std::set<int> ids;
int h = 0;
for(; !ids.empty() && (h <= *ids.rbegin() + 1); ++h) {
    if(!ids.count(h)) {
        break;
    }
}
// h is now smallest value not in ids.

我怀疑这会进一步改进，例如不需要循环？

@edit:阐明集合中有哪些值:在我的用例中，算法生成的值被插入到集合中。我真的应该说 std::set<unsigned int> .我很高兴就这个问题进行了这么多讨论!

Answer 1

因为 std::set 的元素是排序的，你可以使用 std::adjacent_find .

std::adjacent_find(set.begin(), set.end(), [](int a, int b){ return a+1 != b; } );

这将返回第一个元素 a 的迭代器，not 后跟值 a+1。或者 set.end() 如果没有这样的值。

示例用法:

std::set<int> ids { -2, -1, 0, 1, 2, 4, 5, 6 };

// This code assumes a non-empty set, since the range in the question requires same
if ( *ids.begin() > 0 )
{
    // Special case for [0
    std::cout << 0;
}
else
{
    auto res = std::adjacent_find(ids.begin(),
                                  ids.end(),
                                  [](int a, int b){ return a+1 != b; } );
    if ( res == ids.end() )
    {
        // Special case for *ids.rbegin() + 1]
        std::cout << *ids.rbegin() + 1;
    }
    else
    {
        // Print the value that should have followed this one.
        std::cout << *res + 1;
    }
}

输出:

3