Find all the numbers in the range [a, b] that are not in the given std::set S

Question

Let a and b be integers, a < b. Given an std::set<int> S what is an efficient and elegant (preferably without explicit loops) way to find and store (into a vector) all the numbers from [a, b] that are not in S.

Solution 1:

 vector<int> v;
 for(int i = a; i <= b; ++i)
 {
     if(S.find(i) == S.end())
     {
        v.push_back(i);
     }         
}

Solution 2:

Push all the numbers from a to b into a set and use std::set_difference

Solution1 contains an explicit loop, and solution2 does not seem very efficient (at least in terms of memory). What would you suggest? I am looking for an elegant STL-ish (boost is also acceptible) idiomatic way to do this.

Answer 1

You can do something like your solution #2. But instead of creating an actual container containing the range [a,b], use boost::irange, which is a virtual container for a numeric range. This way you have no explicit loops, it will run in linear time, and not take too much memory.

To make it even faster, make it cover only the relevant part of the set by using lower_bound/upper_bound:

auto abRange = boost::irange(a,b+1);
std::set_difference(abRange.begin(), abRange.end(), 
                    s.lower_bound(a), s.upper_bound(b), 
                    std::back_inserter(resultVector));

Or using Boost.Range's set_difference:

boost::set_difference(boost::irange(a,b+1),
                      std::make_pair(s.lower_bound(a), s.upper_bound(b)),
                      std::back_inserter(resultVector));