Find First Two Non-Adjacent Elements in a set Using an STL Algorithm

Question

So I really struggled with this and even now I am not happy with my solution.

I have a set that at least contains 0, and may contain other positive ints. I need to find the first positive number not in the set.

So writing a standard while-loop to accomplish this is easy.

i = foo.begin();
while (i != prev(foo.end()) && *i + 1 == *next(i)){
    ++i;
}
cout << "First number that cannot be formed " << *i + 1 << endl;

But when I try to write an STL algorithm version of the loop I get something that fails like this loop:

auto i = foo.begin();
while (++i != prev(foo.end()) && *prev(i) + 1 == *i);
cout << "First number that cannot be formed " << *prev(i) + 1 << endl;

Both of these loops correctly yield 3 in the case of:

set<int> foo{0, 1, 2, 4};

But the second loop incorrectly yields 3 instead of 4 in this case:

set<int> foo{0, 1, 2, 3};

How can I write this using an STL algorithm and accomplish the behavior of the first loop?

EDIT:

After seeing some of the answers, I'd like to increase the difficulty. What I really want is something that doesn't require temporary variables and can be placed in a cout statement.

Answer 1

The problem with your loop is that you stop one element too early. This works:

while (++i != foo.end() && *prev(i) + 1 == *i);

The difference to the first loop is the condition *prev(i) + 1 == *i) instead of *i + 1 == *next(i); the range you check has to shift accordingly.

You could also use std::adjacent_find:

auto i = std::adjacent_find(begin(s), end(s), [](int i, int j) { return i + 1 != j; });

if(i == s.end()) {
  std::cout << *s.rbegin() + 1 << std::endl;
} else {
  std::cout << *i + 1 << std::endl;
}

Response to the edit: A way to make it prettily inlineable is

  std::cout << std::accumulate(begin(s), end(s), 0,
                               [](int last, int x) {
                                 return last + 1 == x ? x : last;
                               }) + 1 << '\n';

...but this is less efficient because it does not short-circuit when it finds a gap. Another way that does short-circuit is

std::cout << *std::mismatch(begin     (s),
                            prev(end  (s)),
                            next(begin(s)),
                            [](int lhs, int rhs) { 
                              return lhs + 1 == rhs;
                            }).first + 1 << '\n';

Answer 2

Have you tried adjacent_find?

#include <algorithm>
#include <iostream>
#include <set>

int main()
{
    std::set<int> foo{0, 1, 2, 4};
    auto it = std::adjacent_find(begin(foo), end(foo),
         [](auto e1, auto e2){ return (e2 - e1) > 1; });

    // precondition: foo is not empty
    if (it == end(foo)) --it;
    std::cout << *it+1;
}

EDIT: OK, if you consider Boost standard enough, you can do this, which is damn nice:

#include <algorithm>
#include <boost/iterator/counting_iterator.hpp>
#include <set>
#include <iostream>

int main()
{
    std::set<int> foo{0, 1, 2, 4};
    auto it =
        std::mismatch(
           begin(foo), end(foo),
           boost::counting_iterator<int>(*begin(foo))
        );
    std::cout << *it.second;
}

Live example.

EDIT 2: another one I thought of while reading another question:

int i = 0;
std::find_if(begin(foo), end(foo),
    [&i](int e){ return e != i++; });
std::cout << i;

Which is just another way of previus one with mismatch.

Answer 3

You're hitting a fringe case. Your while loop is failing once i == location at the end of the set. In this case it is ending at i == 3. You need to let i walk past the bounds of your array in order to make this work.

You can do this by changing line 2 to :

while (++i **<**= prev(foo.end()) && *prev(i) + 1 == *i);

By making it <=, i will fail once it is past the value at the end of foo.

Here's a few other things to think about: 1) Sets aren't guaranteed to be sorted. 2) What happens in the situation where set foo(0, 1, 1); i.e. duplicates where the one that fails is correct but it is also the one at the end of the set?

You'll need a slightly more complex algorithm to catch all of these cases.