找到[a,b]范围内不在给定std :: set S中的所有数字

Question

设a和b是整数,a < b.给定一个std::set<int> S什么是有效的和优雅的(最好是没有明确的循环)的方式来查找和存储(成vector)都从数字[a, b]中不是S.

解决方案1:

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

解决方案2:

从推动所有的数字a来b成set和使用std::set_difference

Solution1包含一个显式循环,而solution2似乎效率不高(至少在内存方面).你会建议什么？我正在寻找一种优雅的STL-ish(提升也是可以接受的)惯用的方式来做到这一点.

Answer 1

你可以做类似你的解决方案#2.但是,不是创建包含范围的实际容器,而是[a,b]使用boost::irange,这是数值范围的虚容器.这样你没有显式循环,它将以线性时间运行,而不会占用太多内存.

为了使其更快,请使用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));

或使用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));