时间戳

首页 > 解决方案 > 查找不在 std::set 中的第一个值最小-最大

c++ - 查找不在 std::set 中的第一个值最小-最大

问题描述

如何找到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>。我很高兴就这个问题进行了如此多的讨论！

标签： c++algorithmset

解决方案

由于 astd::set的元素已排序，因此您可以使用std::adjacent_find.

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

这将返回一个指向第一个元素 的迭代器，该元素a后面没有值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

推荐阅读