8

设a和b为整数，a < b。给定std::set<int> S什么是一种高效且优雅（最好没有显式循环）的方法来查找和存储（到 a 中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：

将所有数字从ato推b入 aset并使用std::set_difference

解决方案 1 包含一个显式循环，解决方案 2 似乎效率不高（至少在内存方面）。你有什么建议？我正在寻找一种优雅的 STL-ish（提升也是可以接受的）惯用方式来做到这一点。

4

4 回答 4

8

您可以执行类似于您的解决方案 #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));
于 2012-05-17T12:45:57.403 回答
2

中的“集合”set_intersection并不意味着std::set——它只是意味着一个逻辑集合；一组东西。如果两个集合都已排序，您可以简单地set_intersection将两个集合放入第三个容器中。

vector<int> common;
set_intersection(v.begin(), v.end(), s.begin(), s.end(), back_inserter(common));

编辑：

这是一个完整的示例，说明了上述内容。这使用 C++11 lambdas，但如果您没有 C++11 或不能使用 lambdas，您可以使用仿函数代替它们。请注意缺少显式循环。

#include <set>
#include <vector>
#include <algorithm>
#include <iterator>
#include <functional>
#include <iostream>
using namespace std;

static const int numbers[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181};
static const size_t num_numbers = sizeof(numbers)/sizeof(numbers[0]);

int main()
{
    /*** GET THE SET ****/
    set<int> s(begin(numbers), end(numbers));
    //copy(&numbers[0], &numbers[num_numbers], inserter(s, s.begin()));

    /*** GET THE NUMBERS TO LOOK FOR **/
    int first = 5, last = 10;
    vector<int> targets;
    generate_n(back_inserter(targets), last-first, [&first]() -> int {
        return first++;
    });

    /*** FIND THE INTERSECTION ***/
    vector<int> common;
    set_intersection(s.begin(), s.end(), targets.begin(), targets.end(), back_inserter(common));

    /*** DUMP RESULTS ***/
    cout << "Intersecton of:\n\t";
    copy(s.begin(), s.end(), ostream_iterator<int>(cout,"\t"));
    cout << "\nwith:\n\t";
    copy(targets.begin(), targets.end(), ostream_iterator<int>(cout,"\t"));
    cout << "\n= = = = = = = =\n\t";
    copy(common.begin(), common.end(), ostream_iterator<int>(cout,"\t"));
    cout << "\n";

}

输出是：

Intersecton of:
        0       1       2       3       5       8       13      21      34
55      89      144     233     377     610     987     1597    2584    4181

with:
        5       6       7       8       9
= = = = = = = =
        5       8
于 2012-05-17T12:42:38.353 回答
2

好吧，以下内容避免了循环，但我不确定这是您所追求的：

void inSet(int i, int b, vector<int>& v, set<int>& S)
{
   if(S.find(i) == S.end())
        v.push_back(i);

   if(i<b)
        inSet(i+1,b,v,S);
}

// ... snip
vector<int> v;
inSet(a,b,v,S);

此外，在您的解决方案 2 中，是否没有将所有整数 [a,b] 放入 std::set 的循环？

于 2012-05-17T12:43:30.940 回答
1

S.lower_bound(a)您可以从to迭代S.lower_bound(b)并收集所有未找到的整数：

auto end = S.lower_bound(b);
int seen = a;

for (auto it = S.lower_bound(a); it < end; ++it) {
   for (int i = seen+1; i < *it; ++i)
      v.push_back(i);
   seen = *it;
}

它包含一个显式循环，但不知何故，您必须查看[a,b].

于 2012-05-17T12:41:08.263 回答